我刚刚开始学习图，让我感到困惑的是为什么我们需要使用外部数据结构(如矩阵或列表(来存储图的哪些顶点连接到其他顶点。
为什么每个顶点不能只保留对其连接的顶点的引用，就像节点在决策树中所做的那样？对我来说，这似乎更直观。
谢谢！
嗯，这来自设计理念。每当你有多对多的关系时，你都会引入一个经纪人来维持这种关系。这会破坏这种关系，使管理代码和编写数据结构变得更加容易。
例如，如果我们将所有顶点(称为列表 B(信息保留到连接到List B的顶点(称为 A(，则列表 B 的任何顶点中的任何更改都需要传播到 A。如果我们删除一些边缘，我们需要在 A 中更新它。这可能会变得非常混乱。这也违反了单一责任原则。现在我的顶点可以从 2 个轴修改 - 如果它自己修改或它的任何连接被修改。
但是，如果我们对数据结构进行建模，使得每个顶点都可以独立更改，并且顶点中的任何更改都不需要更改其他顶点，这将使我们的生活更简单。我们可以有一个manager或broker来管理每个顶点之间的关系，而不是每个顶点来管理它。此关系管理器是邻接列表/邻接矩阵。
邻接矩阵或邻接列表不是强制性的。还有其他选择。如果您使用的是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 个列表将显示与节点 i 连接的节点。