图形列表实现

Question

我正在考虑图形数据结构实现，并正在研究“发病率列表”表示。这里有简短的描述：

发病率清单

因此，图中的每个顶点都存储了被事件的边缘的列表。

鉴于我的图是一个有向图，因此我从几个点上的描述中不太清楚：

1. 该图本身还存储所有边缘的列表吗？
2. 顶点仅存储外向的边缘，还是传入和外向？
3. 如果两者都在单独的列表中？

我非常熟悉其他图表表示（邻接列表，邻接矩阵，边缘列表，发病率矩阵），因此，这不是关于图形实现的问题，而只是这个特定的问题。

任何指针都将不胜感激。

Answer 1

在进行了进一步研究并考虑到它之后，我得出的结论是，没有发病率列表图数据结构。我认为Wikipedia文章是作者脑海中一些混乱的产物。感谢所有阅读此问题并花费任何时间的人。

阿曼德

Answer 2

我知道我也许是从死者那里提出一个古老的问题，但我觉得发表评论是适当的。

您可以制作一个发射率列表结构，也可以对Digraphs进行调整。

考虑 LinkedList<Vertex> 对象和a LinkedList<Edge> 目的。这将使您在所有边缘和所有顶点上迭代，但不包含有关所有内容如何连接的信息。

说我们补充说，有几个 LinkedList<Connection> 对象。实际上，每个 Vertex. 。一种 Connection 只是在哪里 Edge 和 Vertex 见面。因此 Edge 将有两个 Connection 对象（对于无向图）和一个 Vertex 将有一个 LinkedList<Connection> 对象，表示与每个的连接 Edge 那与之相关。从本质上讲，这是一个发病率清单。

如果删除其中一些 Connection 对象。更具体地说，您必须选择在哪里没有这些参考。您可能会选择删除 Connection从关联 LinkedList<Connection> 如果您不想看到 Edge 来自 Vertex （在上面的示例中，n2将有一个空的 LinkedList<Connection>）。您可以选择在 Edge（上面的示例，E1将有一个 Connection 指向N2和一个 Connection null，允许从E1到N2的遍历，但不能回到N1。您选择如何实施此功能将完全取决于您。一个更直观的是 - 边缘是定向的，因此删除边缘上的连接以决定它们的走向似乎是合乎逻辑的。刚开始时，另一个似乎似乎更为复杂，但是会阻止您不必要地跳到首先进行广度和深度搜索时无处可寻的边缘。

点形式：

1. 在我的发病率清单的实现中。您需要实施吗？

2. 严格来说，您可以通过仅存储传出的边缘来获得。但是，回溯算法可能会受益于能够沿着他们传播的参考文献回溯。当然，您可以通过某种历史进行实施，因此可能并不是什么考虑。

3. 如果两者都这样做，则可能需要某种方法来区分它是传入还是外向。是否有两个 LinkedList<Connection> 顶点上的对象或通过 boolean pointingToVertex 原始 Connection, ， 管他呢。也许你 Edge 将被定向，而无向的边缘将由 二 边缘指向相反的方式。根据您的结构需求进行的考虑。

Answer 3

我通过以下方式实现了发病率列表，找不到任何问题 无向图. 。我也实现了几种图形拓扑算法。

HashMap<VertexT, HashSet<EdgeT>> incidenceMap;

使用集合的地图保证o（1）查找顶点和摊销的O（1）复杂性，用于边缘插入和删除。保留边缘的发病率列表，而不是相邻的顶点列表只是一种携带边缘本身的特定信息的方式。例如，当您将重量与边缘关联时，这也对抽象算法也很有用。

编辑：

我已经更新了 会谈 在Wikipedia的“发病率列表”主题上。