图表发生率列表实现

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

发病率清单

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

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

  1. 图表本身是否也存储了所有边的列表？
  2. 顶点只存储传出边缘，还是传入和传出？
  3. 如果两者都是，他们是在单独的名单？

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

任何指针都将非常感激。

我知道我可能会从死里复活一个旧问题，但我觉得评论是合适的。

您可以创建一个事件列表图结构，也可以调整它以用于有向图。

考虑LinkedList对象和LinkedList对象。 这将允许您遍历所有边和所有顶点，但不包含有关所有连接方式的信息。

假设我们添加了几个LinkedList对象。 实际上，每个Vertex都有一个。 Connection只是Edge和Vertex相遇的地方。 因此， Edge将具有两个Connection对象（对于无向图）， Vertex将具有一个LinkedList对象，表示与连接到它的每个Edge的连接。 实质上，这是一个发病率清单。

如果删除其中一些Connection对象，则可以对其进行修改以表示有向图。 更具体地说，您必须选择没有这些参考的地方。 如果您不希望从Vertex看到Edge ，则可以选择从关联的LinkedList删除Connection （对于上面的示例，N2将具有空的LinkedList ）。 您可以选择在Edge上使引用可选（对于上面的示例，E1将有一个Connection指向N2并且一个Connection null，允许从E1到N2的遍历，但不能返回到N1。您选择如何实现这完全取决于你。一个更直观 – 边缘是直接的，所以删除Edges上的连接以指示它们走向哪个方面似乎是合乎逻辑的。另一个看起来有点复杂，但是会阻止你不必要地跳到在首先进行广度和第一次深度搜索时，边缘无处可去。

以点forms：

  1. 在我的发病率列表的实现中，我有。 你需要实施吗？

  2. 严格地说，您可以通过仅存储传出边缘来获得。 但是，回溯算法可能会受益于能够沿着它们行进的引用回溯。 当然，你可以用某种历史来实现这一点，所以它可能不是很重要。

  3. 如果你同时做到这两点，你可能需要一些方法来区分它是传入还是传出。 是通过在Vertex上有两个LinkedList对象，还是在Connection上有一个boolean pointingToVertex原语，或者其他什么。 也许你的Edge会被定向，而无向边缘将由两条指向相反方向的边缘构成。 根据您的结构需求进行考虑。

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

 HashMap> incidenceMap;

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

编辑：

我已经在维基百科上更新了关于“发生率列表”主题的会谈 。

进一步研究和思考后，我得出的结论是没有一个发生率列表图数据结构。 我认为维基百科的文章是作者心中的一些混淆的产物。 感谢所有阅读此问题并花费任何时间的人。

阿尔芒

Interesting Posts