邻接矩阵

让我们来看看如何实现数据结构来表示图。我们将使用以下示例图：

表示顶点

在讨论图时，我们通常将顶点视为集合 $V$。在上述示例图中，顶点集合为
$V = \{a, b, c, d\}$。

但在代码中处理图时，更方便的做法是为节点分配递增的整数ID，以便能高效地存储相关信息，例如使用类似C++ vector的数组结构。

在我们的示例图中，可以将节点名称映射为整数ID如下：

• $a \to 0$
• $b \to 1$
• $c \to 2$
• $d \to 3$

转换后的图如下：

如果一个图有 $n = |V|$ 个节点，则节点ID为整数 $0, 1, \ldots, n-1$。这意味着我们实际上只需要一个数字 $n$ 就能表示所有节点集合。

我们所有的图算法都将基于这些整数节点ID工作。如果应用程序仍需要原始节点名称（如 $a, b, c, d$），可以将其保存以供将来参考。

1vector<string> nodeNames = {"a", "b", "c", "d"};
2map<string, int> nameToId = {{"a", 0}, {"b", 1}, {"c", 2}, {"d", 3}};

邻接矩阵

现在我们已经处理了节点，接下来看看表示边的数据结构。表示边的两种常见方式是：邻接矩阵 和 邻接表。回忆一下，两个顶点若由一条边连接，则称为相邻。在本课中，我们将探讨邻接矩阵这种数据结构。

邻接矩阵是一个 $n \times n$ 的方阵 $A$，其元素为二进制值（0 或 1）。当节点 $i$ 和 $j$ 之间存在边时，矩阵中的第 $i$ 行第 $j$ 列元素 $A[i, j]$ 为 1，否则为 0。

由于我们的节点用从 0 开始的整数表示，因此矩阵也是 0 索引的：$A[0, 0]$ 是左上角元素，$A[n-1, n-1]$ 是右下角元素。

让我们再次查看上面的示例图。

它的邻接矩阵为：

$$\begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}$$

例如，$A[0, 1]$ 的值为 1，因为图中存在从节点 0 到节点 1 的边；而 $A[3, 2]$ 的值为 0，因为图中没有从节点 3 到节点 2 的边。

由于我们只考虑无自环的简单图，矩阵的主对角线始终为零。

在无向图中，邻接矩阵总是对称的： $A[i,j] = A[j, i] \quad \text{对所有} \quad 0 \leq i \leq n-1, 0 \leq j \leq n-1$

这是由边集的对称性决定的。

实现邻接矩阵

在代码中，邻接矩阵可以使用 vectors 的嵌套结构进行朴素实现。

1#include <vector>
2#include <iostream>
3using namespace std;
4
5int main() {
6    int n = 4;
7    vector<vector<int>> adjacencyMatrix(n, vector<int>(n, 0)); // 初始化为零
8
9    // 使用 (源节点, 目标节点) 对的向量循环添加边
10    vector<pair<int, int>> edges {{0, 1}, {1, 0}, {1, 2}, {1, 3}, {2, 0}, {2, 3}};
11    for (auto [u, v] : edges) {
12        adjacencyMatrix[u][v] = 1;
13    }
14    cout << "从 0 到 1 的边: " << adjacencyMatrix[0][1] << endl;
15    cout << "从 0 到 3 没有边: " << adjacencyMatrix[0][3] << endl;
16}

这种实现还可以进行一些优化：

• 不使用嵌套的 vector<vector<int>>，而是使用一个长度为 $n \times n$ 的单一 vector，其中 $A[i, j]$ 存储在索引 $n \times i + j$ 处。
• 不使用 vector<int>，而是使用 vector<bool>，每个元素仅占一位。

采用这些优化时，最好编写一个包装类来处理索引，并隐藏内部的 vector<bool>，因为其不满足 STL 容器接口规范。

1#include <vector>
2#include <iostream>
3using namespace std;
4
5class AdjacencyMatrix {
6private:
7    vector<bool> adj;
8    int n;
9public:
10  AdjacencyMatrix(int _n) 
11      : n {_n} 
12      , adj {vector<bool>(_n*_n, 0)}
13  {}
14  void addEdge(int source, int target) {
15      this->adj[this->n * source + target] = true;
16  }
17  void removeEdge(int source, int target) {
18      this->adj[this->n * source + target] = false;
19  }
20  bool getEdge(int source, int target) {
21      return this->adj[this->n * source + target];
22  }
23};
24
25int main() {
26    int n = 4;
27    AdjacencyMatrix adjacencyMatrix(n); // 创建空矩阵
28
29    // 使用 (源节点, 目标节点) 对的向量循环添加边
30    vector<pair<int, int>> edges {{0, 1}, {1, 0}, {1, 2}, {1, 3}, {2, 0}, {2, 3}};
31    for (auto [u, v] : edges) {
32        adjacencyMatrix.addEdge(u, v);
33    }
34    cout << boolalpha; // 以 true / false 形式输出布尔值
35    cout << "从 0 到 1 的边: " << adjacencyMatrix.getEdge(0, 1) << endl;
36    cout << "从 0 到 3 没有边: " << adjacencyMatrix.getEdge(0, 3) << endl;
37    
38}

在上述代码片段中，我们实现了一个 AdjacencyMatrix 类，采用了上述优化。该类的接口包括 getEdge、addEdge 和 removeEdge 函数，用于检查和修改边。邻接矩阵的实际表示（作为 vector<bool>）是类内部的实现细节，对外部用户隐藏。