两三个星期没有发布新文章了，今天再来讲一个新的数据结构：图。
见名知意，图论 (Graph Theory) 就是研究 图 (Graph) 的数学理论和方法。图是一种抽象的数据结构，由 节点 (Node) 和 连接这些节点的 边 (Edge) 组成。图论在计算机科学、网络分析、物流、社会网络分析等领域有广泛的应用。
如下，这就是一个图，可以看到这个图有 \(5\) 个顶点，分别编号为 \(\{0, 1, 2, 3, 4\}\)。同时这个图有 \(4\) 条边，例如，在顶点 \(2\) 和 顶点 \(4\) 之间存在着一条边。
在详细讲解图论和有关图论算法之前，先来了解一下在图论中的一些基本表述和规范。
如下图，就是一个有向的简单图（通常来说，在有向图中边的方向用箭头来表示）：
如下图，就是一个无向的多重图，其中存在两条边可以从顶点 \(5\) 到顶点 \(2\)：
与此同时，为了方便起见，对于无向图的处理，我们只需要在两个顶点之间建立两个方向相反的无向边就可以表示一个无向图，具体如下：
在计算机中，图可以通过许多方式来构建和表示。总的可以分成图的邻接矩阵和邻接表两种方法（关于链式前向星本文不过多展开叙述，有兴趣的可以自行查阅相关文档）。
图的邻接矩阵 (Adjacency Matrix)
若一个图中有 \(N\) 个顶点，那么我们就可以用一个 \(N \times N\) 的矩阵来表示这个图。我们一般定义，若矩阵的元素 \(A_{i, j} \neq -\infty\) 表示从节点 \(i\) 到 \(j\) 有一条有向边，其中边的权值为 \(A_{i, j}\)。
假设存在一个有 \(3\) 个顶点的图，并且有三条有向边 \(E = \{(1, 2), (2, 3), (3, 2)\}\)，那么就可以用邻接矩阵表示为：
画成可视化的图就长这个样子：
在 C++ 中，我们可以简单地用一个二维数组来表示：
// 定义一个矩阵。
int map[50][50];
// 将所有的边初始化为负无穷大。
for (int i=1; i<=50; i++)
for (int j=1; j<=50; j++)
map[i][j] = -0x7f7f7f7f;
// 建边，其中所有的边权为1。
map[1][2] = map[2][3] = map[3][2] = 1;
图的邻接表 (Adjacency List)
邻接表本质上就是用链表表示图。数组的每个元素表示一个顶点，元素的值是一个链表，链表中存储该顶点的所有邻接顶点。假设存在一个有 \(4\) 个顶点的图，并且有四条有向边 \(E = \{(1, 2), (2, 3), (3, 2), (3, 4)\}\)，那么就可以用邻接表表示为：
画成可视化的图就长这个样子：
在 C++ 中，我们可以使用 STL模板库 中的 vector 来实现：
#include <vector>
vector<int> G[50]; // 建图。
G[1].push_back(2);
G[2].push_back(3);
G[3].push_back(2);
G[3].push_back(4);
一般情况下，推荐使用邻接表的方式来存图，因为使用邻接矩阵比较浪费空间。在顶点数量非常多但边非常少的图中，\(N^2\) 的时空复杂度会导致 MLE 或 TLE 等问题。
对于下面这个无向图不连通图，顶点 \(1\) 的度数为 \(1\)；顶点 \(2\) 的度数为 \(2\)；顶点 \(3\) 的度数为 \(1\)；顶点 \(4\) 的度数为 \(0\)。同时，由于 \(4\) 号顶点没有度数，所以该顶点没有办法到达任何一个其他的顶点，所以这个图是一个不连通图：
如下图，就是一个有向不强连通图。其中，顶点 \(1\) 的入度为 \(0\)，出度为 \(2\)；顶点 \(2\) 的入度为 \(1\)，出度也为 \(1\)；顶点 \(3\) 的入度为 \(2\)，但出度为 \(0\)。由于顶点 \(1\) 和顶点 \(2\) 可以走到顶点 \(3\)，但顶点 \(3\) 没有办法走到顶点 \(1\) 或顶点 \(2\)，因此下面的图不是一个强连通图：
对于下图来说，\(1\to 2\to 3\to 4\) 是一条从顶点 \(1\) 到顶点 \(4\)的路径。\(2\to 3\to 4 \to 2\to 3\) 就不是一个路径，因为相同的边 \((2, 3)\) 被多次走到了。\(1\to 2\to 3\to 1\) 就是一个回路，因为这个路径的起点和终点相同：
图通常采用 深度优先搜索/ 广度优先搜索 这两个算法来遍历。其中深度优先算法是最常见的遍历算法。
对于一个用 邻接矩阵 保存的图，其深度优先搜索遍历的 C++ 代码如下：
int vis[105], map[105][105];
void dfs(int node){
if (vis[node]) return ;
vis[node] = 1;
cout << node << endl;
for (int i=1; i<=n; i++)
if (map[node][i] != -0x7f7f7f7f)
dfs(i);
return ;
}
// 函数调用：dfs(1); 表示从1号顶点开始遍历。
对于一个用 邻接表 保存的图，其深度优先搜索遍历的 C++ 代码如下：
#include <vector>
vector<int> G[105];
int vis[105];
void dfs(int node){
if (vis[node]) return ;
vis[node] = 1;
cout << node << endl;
for (int to : G[node])
dfs(to);
return ;
}
// 函数调用：dfs(1); 表示从1号顶点开始遍历。
广度优先搜索的方式也类似：
#include <queue>
vector<int> G[105];
int vis[105];
void bfs(int node){
queue<int> que;
que.push(node);
while(!que.empty()){
int t = que.front();
cout << t << endl;
que.pop();
for (int to : G[node]){
if (!vis[to]) {
vis[to] = 1;
que.push(to);
}
}
}
return ;
}
// 函数调用：bfs(1); 表示从1号顶点开始遍历。
对于判断无向图的连通性，我们只需要从任意一个点开始跑一遍深搜或者广搜就行了。如果所有顶点的 vis 都被标记了，则证明图是联通的，否则图就是不连通的。
模板题目，从每一个顶点开始用深搜遍历一遍就可以了。但从每一个点考虑能走到的最大点比较麻烦，一个更优的解决办法是反向建边，从最大的点开始遍历，这样子就可以一次性计算出多个结果。
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N = 10005;
int n, m, ans, vis[N];
vector<int> G[N];
void dfs(int node, int d){
if (vis[node]) return ;
vis[node] = d;
ans = max(node, ans);
for (int to : G[node])
dfs(to, d);
return ;
}
int main(){
cin >> n >> m;
for (int i=0, u, v; i<m; i++){
cin >> u >> v;
G[v].push_back(u); // 反向建边。
}
for (int i=n; i>=1; i--) dfs(i, i);
for (int i=1; i<=n; i++)
cout << vis[i] << ' ';
return 0;
}
也是一道模板题目，正常遍历即可。
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 100005;
int n, m;
int vis1[MAXN], vis2[MAXN];
queue<int> que;
vector<int> G[MAXN];
void dfs(int node, int current){
vis1[node] = 1;
cout << node << ' ';
if (current == n) return ;
for (int i=0; i<G[node].size(); i++){
if (vis1[G[node][i]]) continue;
dfs(G[node][i], current+1);
}
return ;
}
void dfs(int node){
vis2[node] = 1;
que.push(node);
while(que.size()){
int t = que.front();
cout << t << " ";
for (int i=0; i<G[t].size(); i++){
if (vis2[G[t][i]]) continue;
vis2[G[t][i]] = 1;
que.push(G[t][i]);
}
que.pop();
}
return ;
}
int main(){
cin >> n >> m;
for (int i=0; i<m; i++){
int t1, t2;
cin >> t1 >> t2;
G[t1].push_back(t2);
}
for (int i=1; i<=n; i++)
sort(G[i].begin(), G[i].end());
dfs(1, 0), cout << endl, dfs(1);
return 0;
}
更多关于图论的算法，请持续关注后续更新。