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

Question

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

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

谢谢!

Answer 1

嗯，这来自于一种设计理念。每当你有多对多关系时，你都会引入一个经纪人来保持这种关系。这打破了这种关系，使管理代码和编写数据结构变得更加容易。

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

但是，如果我们对数据结构进行建模，使每个顶点都可以独立更改，并且顶点中的任何更改都不需要其他顶点发生变化，那么我们的工作就会变得更简单。我们可以有一个 manager 或 broker 来管理每个顶点之间的关系，而不是每个顶点都管理它。这个关系管理器就是邻接表/邻接矩阵。