我正在考虑图形数据结构实现，并正在查看“发生率列表”表示。这里有一个简单的描述：
发生率列表 http://en.wikipedia.org/wiki/Incidence_list
因此图中的每个顶点都存储它所关联的边的列表。
鉴于我的图是有向图，从这个描述中我不太清楚以下几点：
- 图本身是否也存储所有边的列表？
- 顶点只存储出边，还是入出边？
- 如果两者都有，它们是否在单独的列表中？
我非常熟悉其他图表示形式（邻接列表、邻接矩阵、边列表、关联矩阵），所以这不是一个关于一般图实现的问题，只是这个特定的问题。
任何指示将不胜感激。
我知道我可能提出了一个死人的老问题，但我觉得发表评论是合适的。
您可以创建关联列表图结构，也可以将其调整为有向图。
考虑一个LinkedList<Vertex>对象和一个LinkedList<Edge>目的。这将允许您迭代所有边和所有顶点，但不包含有关所有内容如何连接的信息。
假设我们添加几个LinkedList<Connection>对象。事实上，每人一份Vertex. A Connection就是一个Edge and a Vertex见面。因此Edge将有两个Connection对象（对于无向图），以及Vertex会有一个LinkedList<Connection>对象，代表与每个的连接Edge与它相连的。这本质上是一个事件列表。
如果删除其中一些，您可以修改它以表示有向图Connection对象。更具体地说，您必须选择在哪里不包含这些参考文献。您可以选择删除Connection从相关的LinkedList<Connection>如果您不想看到Edge from a Vertex（对于上面的示例，N2 将有一个空LinkedList<Connection>）。您可以选择将参考文献设为可选Edge（对于上面的示例，E1 将有一个Connection指向 N2 和 1Connectionnull，允许从 E1 遍历到 N2，但不允许返回到 N1。您选择如何实现这一点完全取决于您。一种更直观 - 边是有方向的，因此删除边上的连接来决定它们的走向似乎是合乎逻辑的。另一个乍一看可能有点复杂，但会阻止您在进行广度优先和深度优先搜索时不必要地跳到无处可去的边缘。
以点形式表示：
在我实施的事件列表中，我有。您的实施需要这样做吗？
严格来说，您可以通过仅存储传出边缘来获得。然而，回溯算法可能会受益于能够沿着它们所经过的引用进行回溯。当然，您可以通过某种历史记录来实现这一点，因此可能不需要太多考虑。
如果您两者都做，您可能需要某种方法来区分它是传入还是传出。无论是拥有两个LinkedList<Connection>顶点上的对象，或者通过具有boolean pointingToVertex原始的Connection， 管他呢。也许你的Edge将是有向的，无向的边将由two边缘指向相反的方向。根据您的结构的需要进行考虑。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
