一、图的相关概念

图 $G$ 是一个二元组 $G=(V,E)$。其中 $V$ 是非空集，称为点集，$V$ 中的每个元素称为顶点或节点。$E$ 为各节点之间边的集合，称为边集。图 $G$ 的点数 $|V|$ 称作 $G$ 的阶。

当 $V$ 和 $E$ 都是有限集合时，称 $G$ 为有限图。当 $V$ 或 $E$ 是无限集合时，称 $G$ 为无限图。

根据边是否有向可将图分为：无向图、有向图和混合图：

• 无向图：$E$ 中的每个元素都是一个无序二元组 $(u,v)$，称作无向边，其中 $u,v\in V$。记 $e=(u,v)$，则 $u$ 和 $v$ 称为 $e$ 的端点；
• 有向图：$E$ 中的每个元素都是一个有序二元组 $(u,v)$，有时也写作 $u\to v$，称作有向边或弧。记 $e=(u,v)$，称 $u$ 为 $e$ 的起点，$v$ 为 $e$ 的终点，起点和终点也称为 $e$ 的端点；
• 混合图：$E$ 中既有有向边，又有无向边。

若 $G$ 的每条边都被赋予一个数作为该边的权，则称 $G$ 为赋权图。如果这些权都是正实数，则称 $G$ 为正权图。

1.1 简单图

自环： 对 $E$ 中的边 $e=(u,v)$，若 $u=v$，则称 $e$ 是一个自环。

重边： 若存在 $e_1,e_2\in E$ 使得 $e_1=e_2$，则称它们是（一组）重边。

简单图： 若一个图中没有自环和重边，则它被称为简单图。

多重图： 图中存在自环或重边。

📝 在无向图中 $(u,v)$ 和 $(v,u)$ 算一组重边，但在有向图中不算。

1.2 邻域

在无向图 $G=(V,E)$ 中，若对 $u,v\in V$，存在边 $(u,v)$，则称 $u$ 和 $v$ 是相邻的。

一个顶点 $v\in V$ 的邻域是所有与之相邻的顶点所构成的集合，记作 $N(v)$。一个点集 $S$ 的邻域定义如下：

$$N(S)=\bigcup _{v\in S}N(v)$$

1.3 度数

与一个顶点 $v$ 关联的边的条数称作该顶点的度，记作 $d(v)$。

对于无向简单图，有 $d(v)=|N(v)|$。根据 $d(v)$ 的取值可对图中的顶点进行分类：

$$d(v)=\{\begin{array}{ll}0,& v是孤立点\\ 1,& v是叶节点/悬挂点\\ 2k,& v是偶点\\ 2k+1,& v是奇点\\ |V|-1,& v是支配点\end{array}$$

📝 自环 $(v,v)$ 将对 $d(v)$ 产生 $2$ 的贡献。

对于图 $G$，所有节点的度数的最小值称为 $G$ 的最小度，记作 $\delta (G)$；最大值称为最大度，记作 $\Delta (G)$。即：$\delta (G)={\min }_{v\in G}d(v)$，$\Delta (G)={\max }_{v\in G}d(v)$。若 $\delta (G)=\Delta (G)=k$，即图中每个顶点的度数都是一个固定的常数 $k$，则称 $G$ 为 $k-$正则图。

握手定理（图论基本定理）：对任何无向图，由于每条边都会贡献两个度，所以 ${\sum }_{v\in V}d(v)=2|E|$。

下面考虑有向图。以一个顶点 $v$ 为起点的边的条数称为该顶点的出度，记作 $d^{+}(v)$。以一个顶点 $v$ 为终点的边的条数称为该节点的入度，记作 $d^{-}(v)$。显然 $d^{+}(v)+d^{-}(v)=d(v)$。

由于每条边都会贡献一个出度和一个入度，所以

$$\sum _{v\in V}{d}^{+}(v)=\sum _{v\in V}{d}^{-}(v)=|E|$$

1.4 路径

途径：途径是连接一连串顶点的边的序列，可以为有限或无限长度。形式化地说，一条有限途径 $w$ 是一个边的序列 $e_1,e_2,\cdots ,e_k$，使得存在一个顶点序列 $v_0,v_1,\cdots ,v_k$ 满足 $e_i=(v_{i-1},v_i)$。这样的途径可以简写为 $v_0\to v_1\to v_2\to \cdots \to v_k$。通常来说，边的数量 $k$ 被称作这条途径的长度（如果边是带权的，长度通常指途径上的边权之和）。

迹：对于一条途径 $w$，若 $e_1,e_2,\cdots ,e_k$ 两两互不相同，则称 $w$ 是一条迹。

路径：对于一条迹 $w$，若其连接的点的序列中点两两不同，则称 $w$ 是一条路径。

📝 以上三者的区别在于：途径的边和顶点都可以重复；迹的边不能重复，但顶点可以重复；路径的边和顶点都不能重复。

回路：对于一条迹 $w$，若 $v_0=v_k$，则称 $w$ 是一条回路。

环/圈：对于一条回路 $w$，若 $v_0=v_k$ 是点序列中唯一重复出现的点对，则称 $w$ 是一个环。

⚠️ 关于路径的定义在不同地方可能有所不同，如，「路径」可能指本文中的「途径」，「环」可能指本文中的「回路」。

1.5 连通

1.5.1 无向图

对于一张无向图 $G=(V,E)$，对于 $u,v\in V$，若存在一条途径使得 $v_0=u,v_k=v$，则称 $u$ 和 $v$ 是连通的。由定义，任意一个顶点和自身连通，任意一条边的两个端点连通。

若无向图 $G$ 满足其中任意两个顶点均连通，则称 $G$ 是连通图，$G$ 的这一性质称作连通性。

若 $H$ 是 $G$ 的一个连通子图，且不存在 $F$ 满足 $H⊊F\subseteq G$ 且 $F$ 为连通图，则称 $H$ 是 $G$ 的一个连通块/连通分量。

1.5.2 有向图

对于一张有向图 $G=(V,E)$，对于 $u,v\in V$，若存在一条途径使得 $v_0=u,v_k=v$，则称 $u$ 可达 $v$。由定义，任意一个顶点可达自身，任意一条边的起点可达终点。

若有向图 $G$ 满足其中任意两个顶点互相可达，则称 $G$ 是强连通的。若有向图 $G$ 的边替换为无向边后可以得到一张连通图，则称原来这张有向图是弱连通的。

类似可得强连通分量和弱连通分量的定义。

二、图的存储

图的输入格式通常为：

💾 第一行包含两个整数，分别是 $n$ 和 $m$，代表 $|V|$ 和 $|E|$。接下来 $m$ 行，每行包含三个整数，分别是 $a$，$b$ 和 $c$，代表起点，终点和边权。

2.1 直接存边

使用一个 vector 来存边，数组中的每个元素都包含了一条边的起点与终点（带边权的图还包含边权）。

struct Edge {
    int a, b, c;
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<Edge> edges(m);  // 也可以先声明为全局变量，然后通过resize调整
    for (int i = 0; i < m; i++)
        cin >> edges[i].a >> edges[i].b >> edges[i].c;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

复杂度分析：

• 查询是否存在某条边：$O(m)$；
• 遍历一个点的所有出边：$O(m)$；
• 遍历整张图：$O(nm)$；
• 空间复杂度：$O(m)$。

应用：

• 直接存边的遍历效率低下，一般不用于遍历图。

2.2 邻接矩阵

使用一个二维数组 adj 来存边，其中 adj[u][v] = 1 表示存在 $u$ 到 $v$ 的边，adj[u][v] = 0 表示不存在。如果是带边权的图，可以在 adj[u][v] 中存储 $u$ 到 $v$ 的边权。

int g[N][N];

int main() {
    int n, m;
    cin >> n >> m;
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = c;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

复杂度分析：

• 查询是否存在某条边：$O(1)$；
• 遍历一个点的所有出边：$O(n)$；
• 遍历整张图：$O(n^2)$；
• 空间复杂度：$O(n^2)$。

应用：

• 邻接矩阵只适用于没有重边的情况；
• 邻接矩阵在稀疏图上的效率很低，所以一般只会在稠密图上使用邻接矩阵。

2.3 邻接表

使用一个支持动态增加元素的数据结构构成的数组，如 vector<int> adj[N] 来存边，其中 adj[u] 存储的是点 $u$ 的所有出边的相关信息（终点、边权等）。

vector<pair<int, int>> adj[N];

int main() {
    int n, m;
    cin >> n >> m;
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].emplace_back(b, c);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

邻接表有很多种实现方式，我们还可以单独定义一个结构体或者开两个 vector<int> 型数组分别用来存储终点和边权。

复杂度分析：

• 查询是否存在 $u$ 到 $v$ 的边：$O(d^{+}(u))$；
• 遍历点 $u$ 的所有出边：$O(d^{+}(u))$；
• 遍历整张图：$O(n+m)$；
• 空间复杂度：$O(m)$。

应用：

• 存各种图都很适合，除非有特殊需求；
• 尤其适用于需要对一个点的所有出边进行排序的场合。排序之后，查边的复杂度降至 $O(\log d^{+}(u))$。

2.4 链式前向星

之前的邻接表是基于 vector 来实现的，如果把 vector 换成用数组实现的链表，效率将会提高很多，而这样实现的邻接表又被称为链式前向星。

📝 链式前向星和哈希表中的拉链法非常相似。

int h[N], e[N], ne[N], idx;  // e相当于val，ne相当于nxt，具体请参考上方的超链接
int w[N];  // 用来存储每条边的权重

// 向图中添加a到b的有向边，权重为c
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int main() {
    memset(h, -1, sizeof(h));  // 使用链式前向星必须进行初始化

    int n, m;
    cin >> n >> m;
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

复杂度分析：

因其本质仍是邻接表，所以复杂度和2.3节中的相同。

应用：

• 存各种图都很适合，但不能快速查询一条边是否存在，也不能方便地对一个点的出边进行排序；
• 优点是边是带编号的，有时会非常有用。

三、图的遍历

接下来提到的图均使用链式前向星来存储。

3.1 图的深度优先遍历

深度优先遍历也叫深度优先搜索（Depth First Search），遍历是手段，搜索是目的，通过遍历所有可能的情况以达到搜索的目的，因此「遍历」和「搜索」可以看作是两个的等价概念。

「一条路走到底，不撞南墙不回头」是对DFS的最直观描述。DFS最显著的特征在于其递归调用自身。DFS会对其访问过的点打上访问标记，在遍历图时跳过已打过标记的点，以确保每个点仅访问一次。

DFS实现：

// 从节点u开始进行深度优先搜索
void dfs(int u) {
    st[u] = true;  // 给u打上已访问的标记
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (!st[v]) dfs(v);
    }
}
1
2
3
4
5
6
7
8

DFS的时间复杂度为 $O(n+m)$，空间复杂度为 $O(n)$。

3.2 图的广度优先遍历

广度优先遍历（Breadth First Search）每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。这样做的结果是，BFS算法找到的路径是从起点开始的最短合法路径。

算法过程可以看做是图上火苗传播的过程：最开始只有起点着火了，在每一时刻，有火的节点都向它相邻的所有节点传播火苗。

BFS实现：

// 从节点u开始进行广度优先搜索
void bfs(int u) {
    queue<int> q;
    st[u] = true, q.push(u);
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        for (int i = h[t]; ~i; i = ne[i]) {
            int v = e[i];
            if (!st[v]) st[v] = true, q.push(v);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

在BFS的过程中，也可以记录一些额外的信息。例如，我们可以开一个 d 数组用于记录起点到某个节点的最短距离，再开一个 p 数组记录是从哪个节点走到当前节点的。

void bfs(int u) {
    queue<int> q;
    st[u] = true, q.push(u);
    d[u] = 0, p[u] = -1;  // 假设节点的编号均为正整数
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        for (int i = h[t]; ~i; i = ne[i]) {
            int v = e[i];
            if (!st[v]) {
                st[v] = true, q.push(v);
                d[v] = d[t] + 1, p[v] = t;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

假设路径终点是 x，那么从 u 到 x 的最短路径长度就是 d[x]，相应地，我们可以根据 p 数组还原出这条路径：

vector<int> restore(int x) {
    vector<int> path;
    for (int v = x; ~v; v = p[v])
        path.push_back(v);
    reverse(path.begin(), path.end());
    return path;
}
1
2
3
4
5
6
7

BFS的时空复杂度与DFS相同。

3.3 其他存图方式的BFS/DFS实现

3.3.1 直接存边

BFS：

void bfs(int u) {
    queue<int> q;
    st[u] = true, q.push(u);
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        for (auto &[a, b, c]: edges)
            if (a == t && !st[b])
                st[b] = true, q.push(b);
    }
}
1
2
3
4
5
6
7
8
9
10
11

DFS：

void dfs(int u) {
    st[u] = true;
    for (auto &[a, b, c]: edges)
        if (a == u && !st[b]) dfs(b);
}
1
2
3
4
5

3.3.2 邻接矩阵

假设图中节点的编号从 $1$ 开始。

BFS：

void bfs(int u) {
    queue<int> q;
    st[u] = true, q.push(u);
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        for (int j = 1; j <= n; j++) {
            if (g[t][j] && !st[j])
                st[j] = true, q.push(j);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

DFS：

void dfs(int u) {
    st[u] = true;
    for (int j = 1; j <= n; j++)
        if (g[u][j] && !st[j])
            dfs(j);
}
1
2
3
4
5
6

3.3.3 邻接表

BFS：

void bfs(int u) {
    queue<int> q;
    st[u] = true, q.push(u);
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        for (auto &[b, c]: adj[t])
            if (!st[b]) st[b] = true, q.push(b);
    }
}
1
2
3
4
5
6
7
8
9
10

DFS：

void dfs(int u) {
    st[u] = true;
    for (auto &[b, c]: adj[u]) {
        if (!st[b]) dfs(b);
    }
}
1
2
3
4
5
6

---

References

[1] https://oi-wiki.org/graph/