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

Question

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

为什么不能像决策树中的节点一样，每个顶点都持有指向其相邻顶点的引用？在我看来，这似乎更加直观。

谢谢！

- joshuaronis

---

这是一个很好的问题。如果您的问题允许，将邻接关系隐藏在节点内部是没有问题的。然而，许多图形操作需要所有顶点或所有边缘。"外部"表示简化了所有这些操作。另一个原因是，如果节点不包含数据，则根本不需要显式节点。在这种情况下，您可以使用连续的整数来隐式表示节点。它们索引邻接列表的数组。最后需要注意的是，当边缘被标记时，通常不希望为每个节点创建邻接列表。您需要从标签到下一个顶点的映射。 - Gene

最后，当边缘被标记时，从标签到下一个顶点的映射比简单列表更好。确切的结构取决于您要解决的问题。高度专业化的图形表示的一个很酷的例子（通常作为内部实现，正如您所问的）是半边数据结构，用于有效地表示计算几何算法中的多面体。半边数据结构 - Gene

Answer 1

这来自于一种设计哲学。每当你有一个多对多的关系时，你引入一个代理来维护这个关系。这会打破关系并使代码管理和编写数据结构更容易。

例如，如果我们将所有顶点（称为列表B）的信息保存到与列表B相连的顶点A中，那么列表B中任何顶点的更改都需要传播到A。如果我们删除某些边缘，则需要在A中更新它。这可能变得非常混乱。这也违反了单一职责原则。现在我的顶点可以从两个方面进行修改——如果它自己修改或任何连接被修改。

然而，如果我们对数据结构进行建模，使每个顶点可以独立更改，并且不需要其他顶点发生变化，那么我们的生活就会变得更简单。我们可以有一个管理关系的代理或经纪人，而不是每个顶点都管理它。这个关系管理器就是邻接表/邻接矩阵。

- Avishek Bhattacharya

Answer 2

邻接矩阵或邻接表并非必须。还有其他选择。如果您使用C ++，请使用vector和map。如果顶点/节点从0-N编号，则不需要map，而是可以使用vector。 例如：

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 相连的节点。

- Adnatull Al Masum