图发生列表实现

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

Incidence list

所以每个顶点在图中存储这些边后，它是事件的列表。

鉴于我的图是一个有向图，我不是从这个描述很清楚的一对夫妇点：

是否图形本身还可以存储所有边缘的名单？
顶点只存储传出边缘，还是传入和传出？
如果两者都在单独的列表中？

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

任何指针将不胜感激。

来源

2010-10-11 Armand A

已经研究并想过这个问题进一步，我得出的结论是没有发生率表图形数据strucure。我认为维基百科的文章是作者脑海中一些混淆的产物。感谢大家阅读这个问题，并花时间在这个问题上。

阿尔芒

来源

2010-10-12 11:53:20

我知道我可能提高从死里复活一个老问题，但我觉得它适合发表意见。

您可以使发病率表图结构，你也可以调整它有向图。

考虑一个LinkedList<Vertex>对象和LinkedList<Edge>对象。这可以让你迭代所有的边和所有的顶点，但不包含任何有关连接的信息。

说我们添加的话，几个LinkedList<Connection>对象。实际上，每个Vertex。 A Connection就是Edge和Vertex相符的地方。因此，一个Edge将有两个Connection对象（对于无向图），和一个Vertex将具有一个LinkedList<Connection>对象，表示到连接到它的每一个Edge连接。这本质上是一个发病名单。

您可以修改这表示有向图，如果你删除其中的一些Connection对象。更具体地说，你必须选择哪里没有这些引用。您可以选择从相关LinkedList<Connection>删除Connection如果你不希望能够看到一个Edge从Vertex（上面的例子中，N2将有一个空LinkedList<Connection>）。你可能会转而选择使引用可选的Edge（对于上面的例子中，E1将不得不在N2一个Connection指向和一个Connection空，允许从E1遍历N2，但未恢复到N1。您的选择如何实现这完全取决于你，其中一个更直观 - 边缘是直接的，所以删除边缘上的连接来决定它们走哪条路似乎是合乎逻辑的。另一个看起来可能看起来更复杂一些，但会阻止你不必要地跳到无处不在的边缘上，在进行广度优先和深度优先搜索时无处可去。

以点形式：

在我的一个发名单的实现，我有。你需要为你的实施？
严格地说，你可以通过只存储传出边缘来获得。但是，回溯算法可能会受益于能够沿着他们旅行的参考回溯。当然，你可以用某种历史来实现这一点，所以它可能不是一个考虑因素。
如果你们两个都做，你可能需要一些方法来区分它是传入还是传出。无论是在顶点上有两个LinkedList<Connection>对象，还是在Connection上有boolean pointingToVertex原语，或者其他什么。也许你的Edge将被定向，并且无向边将由两个边指向相反的方向。需要考虑的因素取决于你的结构的需求。

来源

2010-12-20 13:56:04 JBirch

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

HashMap<VertexT, HashSet<EdgeT>> incidenceMap;

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

编辑：

我已经更新了维基百科的talks为“发病名单”主题。

来源

2011-01-08 14:11:18 ceztko

图发生列表实现

回答

相关问题