java - 图关联列表实现

Question

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

Incidence list

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

鉴于我的图是一个有向图，我从这个描述中有几点不是很清楚:

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

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

如有任何指点，我们将不胜感激。

Answer 1

我知道我可能提出了一个死里逃生的老问题，但我觉得发表评论是合适的。

您可以创建关联列表图结构，也可以针对二合字母对其进行调整。

考虑一个 LinkedList<Vertex>对象和一个 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将被定向，而无向边将由指向相反方向的两条边组成。根据您的结构需要做出的考虑。