图关联列表实现

Question

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

事件列表

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

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

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

为空，允许从 E1 遍历到 N2，但不能返回到 N1。您选择如何实现这一点完全取决于您。一个更直观 - 边是有方向的，因此删除边上的连接来决定它们的走向似乎是合乎逻辑的。另一种乍一看可能有点复杂，但是在进行广度优先和深度优先搜索时，将阻止您不必要地跳到无处可去的边缘。

点形式：

1. 在我实施事件列表时，我有。您的实施需要这样做吗？

2. 严格来说，您可以通过仅存储传出边缘来获得。然而，回溯算法可能会受益于能够沿着它们所经过的引用进行回溯。当然，您可以通过某种历史记录来实现这一点，因此可能不需要太多考虑。

3. 如果您两者都做，您可能需要某种方法来区分是传入还是传出。无论是在顶点上有两个

   LinkedList<Connection>

   对象，还是在

   boolean pointingToVertex

   上有一个

   Connection

   基元，或者其他什么。也许你的

   Edge

   是有向的，无向边将由指向相反方向的 two 边组成。根据您的结构的需要进行考虑。

Answer 2

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

HashMap<VertexT, HashSet<EdgeT>> incidenceMap;

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

编辑：

我已经更新了维基百科上“发生率列表”主题的talks。

Answer 3

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

阿尔芒

Answer 4

关联表是邻接表的别称。

1. 您可以也可以不将边单独存储在图表本身中。这是你的选择。通常，如果使用 Java 引用链接边列表中的边，则不需要单独存储边。但您可能更喜欢使用边索引而不是 Java 引用来集中存储边和链接边。这种方式对于将图序列化到外部存储更加自然，因为边索引将按原样编写，而 Java 引用需要首先转换为索引。

class Graph {
    // vertex[i] points to a list of arcs from vertex i
    private Arc[] vertex; 

    private static final class Arc {
        // whatever data you need to attach to the arc
        private int data;
        // a reference to the next arc in the vertex arc list
        private Arc next;
    }
}

class Graph {
    // an array of all arcs
    private Arc[] arcs;
    // the same as before, but instead of references we use indices in the arcs array
    private int[] vertex;

    private static final class Arc {
        private int data;
        private int next;
    }
}

2. 如你所愿。对于典型的图算法来说，存储就足够了 传出边缘。

3. 是的。