4

我正在考虑图形数据结构的实现，并正在查看“事件列表”表示。这里有一个简短的描述：

发病清单

所以图中的每个顶点都存储了一个它所发生的边的列表。

鉴于我的图是有向图，从这个描述中我对以下几点不是很清楚：

  1. 图本身是否也存储所有边的列表？
  2. 顶点只存储传出边，还是传入和传出？
  3. 如果两者都有，它们是否在单独的列表中？

我对其他图表示（邻接表、邻接矩阵、边表、关联矩阵）非常熟悉，所以这不是关于图实现的问题，只是这个特定的问题。

任何指针将不胜感激。

4

3 回答 3

2

我知道我可能会从死者那里提出一个老问题，但我觉得发表评论是合适的。

您可以制作关联列表图结构，也可以针对有向图调整它。

考虑一个LinkedList<Vertex>对象和一个LinkedList<Edge>对象。这将允许您遍历所有边和所有顶点，但不包含有关所有内容如何连接的信息。

假设我们添加了几个LinkedList<Connection>对象。事实上，每个Vertex. AConnection只是一个Edge和一个Vertex相遇的地方。因此，anEdge将有两个Connection对象（对于无向图），并且 aVertex将有一个LinkedList<Connection>对象，表示与Edge连接到它的每个对象的连接。这实质上是一个发病率列表。

如果您删除其中一些Connection对象，您可以修改它以表示有向图。更具体地说，您必须选择没有这些引用的位置。如果您不想看到来自 a 的 a （对于上面的示例，N2 将有一个空的），您可以选择Connection从关联中删除 a 。您可以改为选择将引用设为可选（对于上面的示例，E1 将有一个指向 N2 和一个LinkedList<Connection>EdgeVertexLinkedList<Connection>EdgeConnectionConnectionnull，允许从 E1 遍历到 N2，但不能返回到 N1。您选择如何实现这一点完全取决于您。一个更直观 - 边缘是定向的，因此删除边缘上的连接以指示它们走哪条路似乎是合乎逻辑的。另一个可能一开始看起来有点复杂，但会阻止你在进行广度优先和深度优先搜索时不必要地跳到无处可去的边缘。

点形式：

  1. 在我的发生率列表的实现中，我有。你需要为你的实施？

  2. 严格来说，您可以通过仅存储传出边来获得。然而，回溯算法可能会受益于能够沿着他们经过的参考进行回溯。当然，您可以通过某种历史来实现这一点，所以这可能不是一个考虑因素。

  3. 如果你两者都做，你可能需要一些方法来区分它是传入还是传出。无论是通过LinkedList<Connection>在 Vertex 上拥有两个对象，还是通过在boolean pointingToVertex上拥有一个基元Connection，或其他方式。也许您Edge会被定向，而无向边将由指向相反方向的两条边组成。根据您的结构的需要进行考虑。

于 2010-12-20T13:56:04.840 回答
2

我通过以下方式实现了一个关联列表，没有发现无向图有任何问题。我也实现了几个图拓扑算法。

HashMap<VertexT, HashSet<EdgeT>> incidenceMap;

使用集合映射保证顶点查找的 O(1) 和边插入和删除的摊销 O(1) 复杂度。保留边的关联列表而不是相邻的顶点列表只是携带边本身的某些特定信息的一种方式。这对于抽象算法也很有用，例如，当您将权重与边缘相关联时。

编辑：

我已经更新了维基百科上关于“发病率列表”主题的讨论。

于 2011-01-08T14:11:18.917 回答
0

经过进一步研究和思考，我得出的结论是不存在发生率列表图数据结构。我认为维基百科的文章是作者头脑中一些混乱的产物。感谢所有阅读此问题并花费任何时间的人。

阿尔芒

于 2010-10-12T11:53:20.770 回答