为什么使用邻接矩阵或邻接列表？

Question

我刚开始学习图，有些东西让我感到困惑，那就是为什么我们需要使用外部数据结构(如矩阵或列表)来存储图的哪些顶点与其他顶点相连接。

为什么每个顶点不能只保存对其连接的顶点的引用，就像节点在决策树中所做的那样？在我看来，这似乎更直观。

谢谢!

Answer 1

这是一种设计哲学。每当你有很多到许多关系，你介绍一个经纪人来保持这种关系。这破坏了关系，使管理代码和编写数据结构变得更容易。

例如，如果我们将所有的顶点(称为列表B)信息保存到连接到List B的顶点(称为A)，则列表B中任何一个顶点的任何更改都需要传播到A。如果我们删除了某些边缘，我们需要更新A中的内容，这可能会变得非常混乱。这也违反了单一责任原则。现在我的顶点可以从两个轴上修改--如果它自己修改或者修改它的任何连接。

然而，如果我们对数据结构建模，使每个顶点可以独立地变化，而顶点中的任何变化都不需要改变其他顶点，这就使我们的生活变得更简单了。我们可以有一个manager或broker来管理每个顶点之间的关系，而不是管理每个顶点。该关系管理器是邻接表/邻接矩阵。

Answer 2

邻接矩阵或邻接列表不是强制性的。还有其他的选择。如果您使用的是C++，那么使用向量和地图。如果顶点/节点编号为0-N，则不需要映射，而是向量。例如：

vector < vector < int > > graph; // while vertex/node are numbered from 0-N.
map < int, vector<int> > graph; // when vertex/node can be any number

graph[i].push_back(x); // insertion of node x in i'th list. 

遍历i‘’th列表将显示与节点i连接的节点。