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。

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