c - C编程语言图结构

Question

我在构建图形结构时遇到了一些麻烦。我知道如何建立一个简单的链表，而且也是加倍的。但我想在这个网站（图片输出）http://www.cs.sunysb.edu/~algorith/files/graph-data-structures.shtml中构建一个图形结构

Answer 1

您有三种常见的解决方案：

• 一个邻接矩阵（在其中存储一个矩阵，N*N其中 N 是顶点数，matrix[x][y]如果x有边到y，则存储一个值，否则为 0
• 一个边列表，您只需在其中保留一长串边，这样如果这对夫妇(x,y)在列表中，则从 x 到 y 有一条边
• 一个邻接列表，其中有一个顶点列表，每个顶点x都有一个边列表，指向 x 有边的节点。

每种不同的方法都是好是坏

• 需要空间
• 与特定操作相关的计算复杂度高于其他

因此，根据您需要对图表执行的操作，您可以选择其中任何一个。如果您想了解上述可能实现的具体特征，请查看我对另一个 SO 问题的回答。