c++ - C++：Graph ADT 是否应该有一个顶点列表和一个边列表，或者只是带有指向其他顶点的指针的顶点？

Question

我正在尝试用 C++ 实现一个图形，我不确定是否有一种“正确”的方式来解决这个问题。我的每个顶点是否应该包含它指向的顶点列表，或者图形对象是否应该包含顶点列表和边列表。

Answer 1

这取决于您正在处理的图表类型，如果您的图表是加权的，您不能只拥有一个指针列表，因为您将无法为此连接分配权重。在这种情况下，我建议每个节点都包含一个连接到它的边列表。如果图不是有向的，那么对于任何顶点 i 和 j，您可以保存指向同一边 {i, j} 的指针，如果它是有向的，则边 {i, j} 和 {j, i} 是两个不同的对象.

另一种方法是保存一个表示所有顶点之间连接的 NxN 矩阵。如果图没有加权，则如果顶点 i 到顶点 j 之间存在边，则每个单元格 [i, j] 将为 1。如果图是加权的，则单元格 [i, j] 将包含顶点 i 到顶点 j 之间的距离，如果边不存在，则为无穷大或 -1。

如果您的图是完整的（每个顶点都连接到所有其他顶点），我强烈建议使用矩阵技术，因为它很容易实现，让您可以直接访问任何相关值，并且不占用额外的内存或运行时间（例如，当您想要遍历连接到某个顶点的所有边时），因为任何顶点都将包含与所有其他顶点的连接列表。

Answer 2

这取决于您访问图形数据。您可以如下定义二维向量：

vector< vector<int> > nodes;

其中节点 ID 为 0 到 number_of_nodes -1；节点 6 将存储在节点 [6] 中，然后继续。