图的关联表实现

Question

我正在考虑图数据结构的实现，并正在研究“关联表”表示法。这里有一个简短的描述：

关联表

因此，图中的每个顶点都存储了它所关联的边的列表。

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

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

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

任何指针都将不胜感激。

- Armand A

Answer 1

我知道我可能在重提一个老问题，但我觉得评论是适当的。

您可以创建一个关联表图结构，并且还可以为有向图进行调整。

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

因此，我们添加了几个LinkedList<Connection>对象。实际上，每个Vertex都有一个。一个Connection只是一个Edge和一个Vertex相遇的地方。因此，一个Edge将具有两个Connection对象（对于无向图），而一个Vertex将具有一个LinkedList<Connection>对象，表示与其相连的每个Edge的连接。这本质上是一个关联列表。

如果要表示有向图，则可以修改此内容以删除其中一些Connection对象。更具体地说，您将不得不选择在哪里没有这些引用。如果您不想从Vertex中看到一个Edge（对于上面的示例，N2将有一个空的LinkedList<Connection>），则可以选择从相关的LinkedList<Connection>中删除Connection。您还可以选择在Edge上使引用可选（对于上面的示例，E1将有一个指向N2的Connection和一个空的Connection，允许从E1到N2进行遍历，但不能返回到N1。如何实现这取决于您。其中一种更直观-边缘是定向的，因此删除边缘上的连接以指示其走向似乎是合乎逻辑的。另一个可能一开始看起来有点复杂，但在进行广度优先和深度优先搜索时，它将阻止您不必要地跳到没有出路的边缘。

以点形式：

1. 在我的关联表实现中，我有...你需要在你的实现中吗？

2. 严格来说，你只需要存储出边就可以了。然而，回溯算法可能会受益于能够回溯沿着它们走过的引用。当然，你可以通过某种形式的历史记录来实现这一点，所以这可能不是什么大问题。

3. 如果你两者都做，你可能需要一些方法来区分是入边还是出边。无论是在顶点上有两个LinkedList<Connection>对象，还是在Connection上有一个boolean pointingToVertex原语，或者其他方式。也许你的Edge是有向的，而无向边由相反方向指向的两条边组成。根据你的结构的需求进行考虑。

- JBirch

Answer 2

我按照以下方式实现了一个关联表，并且在无向图中没有发现任何问题。我还实现了几种图形拓扑算法。

HashMap<VertexT, HashSet<EdgeT>> incidenceMap;

使用集合地图可以保证在顶点查找时的O（1）复杂度，并且在插入和删除边缘时具有平摊的O（1）复杂度。保留边缘的关联列表而不是顶点的相邻列表只是一种携带边缘本身特定信息的方式。当您将权重与边缘相关联时，这对于抽象算法也很有用。

编辑：

我已经在维基百科上更新了“关联列表”主题的talks。

- ceztko

Answer 3

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

阿曼德

- Armand A