我刚刚开始学习图,令我困惑的是为什么我们需要使用外部数据结构(如矩阵或列表)来存储图的哪些顶点与其他顶点相连顶点。
为什么每个顶点不能只保存对其连接的顶点的引用,就像节点在决策树中所做的那样?对我来说,这似乎更直观。
谢谢!
最佳答案
嗯,这来自于一种设计理念。每当你有多对多关系时,你都会引入一个经纪人来保持这种关系。这打破了这种关系,使管理代码和编写数据结构变得更加容易。
例如,如果我们将所有顶点(称为 List B)信息保存到连接到 List B
的顶点(称为 A),List 的任何顶点的任何更改B 需要传播到 A。如果我们删除了一些边,我们需要在 A 中更新它。这会变得非常困惑。这也违反了单一职责原则。现在我的顶点可以从 2 个轴修改 - 如果它自己修改或者它的任何连接被修改。
但是,如果我们对数据结构进行建模,使每个顶点都可以独立更改,并且顶点中的任何更改都不需要其他顶点发生变化,那么我们的工作就会变得更简单。我们可以有一个 manager
或 broker
来管理每个顶点之间的关系,而不是每个顶点都管理它。这个关系管理器就是邻接表/邻接矩阵。
关于graph - 为什么使用邻接矩阵或邻接表?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59450195/