Graph

图专题复习笔记#

0. 总览#

图专题在这门课里主要按以下顺序展开：

1. Graph definitions：图、无向图、有向图、路径、连通性、度、DAG。
2. Representation of graphs：邻接矩阵、邻接表、逆邻接表、邻接多重表、带权边。
3. Topological Sort：AOV network、拓扑序、用入度为 0 的点生成拓扑序、判环。
4. Shortest Path Algorithms：无权最短路、Dijkstra、负边权图、DAG 最短路。
5. AOE / CPM：项目调度、EC/LC、slack time、critical path。
6. All-pairs shortest path：把单源最短路跑 $|V|$ 次，或使用 $O(|V|^3)$ 的全源算法。

复习时抓住一句话：图算法通常都在围绕“点、边、路径约束、访问顺序、松弛更新”这几个动作做文章。

1. Graph Definitions#

1.1 图的定义#

课程 PPT 的定义：

其中：

• $G$ 表示 graph。
• $V = V(G)$ 是有限非空顶点集合。
• $E = E(G)$ 是有限边集合。

两类基本图：

本课程的限制：

1. Self loop is illegal：不考虑自环。
2. Multigraph is not considered：不考虑重边。

Complete graph 是边数达到最大值的图：

• 无向完全图最多有 $\frac{n(n-1)}{2}$ 条边。
• 有向完全图如果不允许自环，最多有 $n(n-1)$ 条有向边。

1.2 相邻与关联#

无向图中：

• $v_i$ and $v_j$ are adjacent：$v_i$ 和 $v_j$ 相邻。
• $(v_i, v_j)$ is incident on $v_i$ and $v_j$：这条边关联到两个端点。

有向图中：

• $\langle v_i, v_j \rangle$ 表示从 $v_i$ 指向 $v_j$。
• $v_i$ is adjacent to $v_j$。
• $v_j$ is adjacent from $v_i$。
• $\langle v_i, v_j \rangle$ is incident on $v_i$ and $v_j$。

这几个英文短语容易在题目里出现，重点是区分 to 和 from 的方向。

1.3 子图、路径、环#

Subgraph：

含义：

Path from $v_p$ to $v_q$：

要求路径上相邻的顶点之间有对应的边：

• 无向图中是 $(v_p, v_{i1}), (v_{i1}, v_{i2}), \dots, (v_{in}, v_q) \in E(G)$。
• 有向图中是 $\langle v_p, v_{i1} \rangle, \dots, \langle v_{in}, v_q \rangle \in E(G)$，方向必须一致。

几个重要定义：

1.4 连通性#

无向图中：

• $v_i$ and $v_j$ are connected：从 $v_i$ 到 $v_j$ 有路径，因此从 $v_j$ 到 $v_i$ 也有路径。
• An undirected graph $G$ is connected：任意两个不同顶点之间都 connected。
• Connected component：无向图中的 maximal connected subgraph。

树也可以从图的角度定义：

A tree is a graph that is connected and acyclic.

也就是：连通且无环。

有向图中：

• Strongly connected directed graph：任意两个顶点 $v_i, v_j$ 之间，都同时存在 $v_i \to v_j$ 和 $v_j \to v_i$ 的有向路径。
• Weakly connected：如果忽略边方向后图是连通的，则称弱连通。
• Strongly connected component：maximal subgraph that is strongly connected。

1.5 度#

无向图：

有向图：

• in-degree：进入该顶点的边数。
• out-degree：从该顶点出去的边数。
• degree 通常可看作 in-degree + out-degree。

给定 $n$ 个顶点、$e$ 条边：

这两个式子很常用于检查计数题。

2. Representation of Graphs#

2.1 Adjacency Matrix#

邻接矩阵对 $G(V,E)$ 的 $n$ 个顶点建立：

adj_mat[n][n]

无权图中常用：

带权图中常用：

如果两点之间没有边，通常可设为 $0$、$\infty$ 或某个 sentinel，具体取决于算法。

特点：

2.2 Adjacency Lists#

邻接表的思想：

Replace each row by a linked list.

也就是每个顶点有一个表头，后面挂它的邻接点。

无向图中，每条边 $(i,j)$ 会出现两次：

• 一次出现在 graph[i] 的链表里。
• 一次出现在 graph[j] 的链表里。

PPT 给出的空间估计：

For undirected G:
S = n heads + 2e nodes = (n + 2e) ptrs + 2e ints

要点：

• 每个链表中结点的顺序不影响图的含义。
• 无向图中，Degree(i) 等于 graph[i] 链表中的结点个数。
• 扫描整个边集的时间是：

这也是 BFS、DFS、拓扑排序、稀疏图最短路经常能做到 $O(|V|+|E|)$ 的原因。

2.3 有向图中的入度#

有向图的邻接表天然容易得到 out-degree，但如果要频繁求 in-degree，就需要额外处理。

PPT 给出两种方法：

1. Add inverse adjacency lists：增加逆邻接表。
2. Multilist representation for adj_mat[i][j]：使用多重链表结构，让边结点能同时挂在 tail 行和 head 列上。

逆邻接表的含义：

• 普通邻接表按 outgoing edge 存。
• 逆邻接表按 incoming edge 存。
• 如果拓扑排序中要快速维护入度，一般可以直接用 Indegree[] 数组，而不一定真的建逆邻接表。

2.4 Adjacency Multilists#

无向图的邻接表里，每条边要建两个结点。邻接多重表的想法是：

Combine the two nodes into one.

一个边结点同时服务于两个端点，典型字段：

struct EdgeNode {
    Vertex v1;
    Vertex v2;
    int mark;
    struct EdgeNode *next_v1;
    struct EdgeNode *next_v2;
};

理解重点：

• \(v_{1}\) 和 \(v_{2}\) 是边的两个端点。
• \(next_{v_{1}}\) 挂在 $v_1$ 的链上。
• \(next_{v_{2}}\) 挂在 $v_2$ 的链上。
• mark 常用于遍历时避免同一条边被处理两次。

这种结构比普通邻接表更复杂，考试里更常考“为什么这样能避免一条无向边存两个结点”。

2.5 Weighted Edges#

带权边的表示：

• 邻接矩阵：\(adj_{mat}[i][j] = weight\)。
• 邻接表 / 邻接多重表：在边结点中增加 weight 字段。

后面的最短路算法都依赖这个 weight 或 cost。

3. Topological Sort#

3.1 AOV Network#

AOV Network：

A digraph $G$ in which $V(G)$ represents activities and $E(G)$ represents precedence relations.

例子：课程先修关系。

如果有边：

含义是 $C_1$ 是 $C_3$ 的先修课。

术语：

3.2 Partial Order 与 DAG#

PPT 中 partial order 的性质：

1. Transitive：如果 $i \to k$ 且 $k \to j$，则 $i \to j$。
2. Irreflexive：$i \to i$ 不可能。

Feasible AOV network must be a DAG。

原因：

• 如果有环，就意味着某个任务最终依赖自己。
• 如果一个任务必须在自己开始前完成，项目不可行。

3.3 Topological Order#

PPT 定义：

A topological order is a linear ordering of the vertices of a graph such that, for any two vertices $i, j$, if $i$ is a predecessor of $j$ in the network then $i$ precedes $j$ in the linear ordering.

中文理解：

• 把 DAG 的顶点排成一条线。
• 所有依赖关系都必须从前指向后。
• 拓扑序不一定唯一。

目标：

1. Test an AOV for feasibility。
2. Generate a topological order if possible。

3.4 朴素拓扑排序#

PPT 的朴素版本：

void Topsort(Graph G)
{
    int Counter;
    Vertex V, W;

    for (Counter = 0; Counter < NumVertex; Counter++) {
        V = FindNewVertexOfDegreeZero();
        if (V == NotAVertex) {
            Error("Graph has a cycle");
            break;
        }
        TopNum[V] = Counter; /* or output V */
        for (each W adjacent to V)
            Indegree[W]--;
    }
}

关键点：

• 每次找一个当前入度为 0 且还没编号的顶点。
• 输出它或给它分配拓扑编号。
• 删除它的出边，表现为让后继的入度减 1。
• 如果找不到入度为 0 的点，但还有顶点没处理，说明有环。

如果 FindNewVertexOfDegreeZero() 每次都扫描所有顶点，则总时间：

3.5 用队列或栈改进#

PPT 的改进：

Keep all the unassigned vertices of degree 0 in a special box (queue or stack).

队列版本：

void Topsort(Graph G)
{
    Queue Q;
    int Counter = 0;
    Vertex V, W;

    Q = CreateQueue(NumVertex);
    MakeEmpty(Q);

    for (each vertex V)
        if (Indegree[V] == 0)
            Enqueue(V, Q);

    while (!IsEmpty(Q)) {
        V = Dequeue(Q);
        TopNum[V] = ++Counter; /* assign next */
        for (each W adjacent to V)
            if (--Indegree[W] == 0)
                Enqueue(W, Q);
    }

    if (Counter != NumVertex)
        Error("Graph has a cycle");

    DisposeQueue(Q);
}

复杂度：

原因：

• 每个顶点入队、出队至多一次。
• 每条边在更新后继入度时被检查一次。

复习提醒：

• 用 queue 和 stack 都可以生成拓扑序，只是得到的具体顺序可能不同。
• 如果题目问“拓扑序是否唯一”，要看每一步是否都只有一个入度为 0 的候选点。

4. Shortest Path Algorithms#

4.1 最短路问题定义#

给定有向图：

以及边的代价函数：

路径 $P$ 的长度，也叫 weighted path length，是路径上所有边权的和：

Single-Source Shortest-Path Problem：

Given as input a weighted graph $G=(V,E)$ and a distinguished vertex $s$, find the shortest weighted path from $s$ to every other vertex in $G$.

注意：

• 如果存在 negative-cost cycle，最短路可能没有定义，因为可以不断绕圈让路径长度越来越小。
• 如果没有 negative-cost cycle，通常把从 $s$ 到 $s$ 的最短路定义为 0。

4.2 最短路表 Table#

PPT 中最短路算法常用一个表：

Path 字段用于最后打印路径：从目标点不断沿 Path 回溯到源点，再反向输出。

4.3 Unweighted Shortest Paths#

无权最短路可以看作所有边权都为 1。

核心思想：

Breadth-first search.

BFS 按距离层次扩展：

• 距离 0：源点。
• 距离 1：源点直接邻接点。
• 距离 2：从距离 1 顶点继续扩展得到的未访问点。
• 依此类推。

朴素版本按 CurrDist 一层层扫描所有顶点：

void Unweighted(Table T)
{
    int CurrDist;
    Vertex V, W;

    for (CurrDist = 0; CurrDist < NumVertex; CurrDist++) {
        for (each vertex V)
            if (!T[V].Known && T[V].Dist == CurrDist) {
                T[V].Known = true;
                for (each W adjacent to V)
                    if (T[W].Dist == Infinity) {
                        T[W].Dist = CurrDist + 1;
                        T[W].Path = V;
                    }
            }
    }
}

最坏情况：

改进版本使用队列：

void Unweighted(Table T)
{
    Queue Q;
    Vertex V, W;

    Q = CreateQueue(NumVertex);
    MakeEmpty(Q);
    Enqueue(S, Q);

    while (!IsEmpty(Q)) {
        V = Dequeue(Q);
        T[V].Known = true; /* not really necessary */

        for (each W adjacent to V)
            if (T[W].Dist == Infinity) {
                T[W].Dist = T[V].Dist + 1;
                T[W].Path = V;
                Enqueue(W, Q);
            }
    }

    DisposeQueue(Q);
}

复杂度：

关键判断：

• 只有 \(Dist == Infinity\) 的点才第一次入队。
• 第一次到达某个点时，已经是无权图中的最短距离。

4.4 Dijkstra's Algorithm#

Dijkstra 用于 weighted shortest paths，但要求边权非负。

PPT 中的集合：

对任意 $u \notin S$，定义：

如果路径按非递减顺序生成，则：

1. 已确认的最短路只经过 $S$ 中的顶点。
2. 每次选择满足 distance[u] 最小的未知顶点 $u$，这一步是 greedy method。
3. 加入新顶点 $u_1$ 后，其他未知顶点 $u_2$ 的距离可能变小；如果变小，则新路径经过 $u_1$：

这一步就是 relaxation。

PPT 伪代码：

void Dijkstra(Table T)
{
    Vertex V, W;

    for (;;) {
        V = smallest unknown distance vertex;
        if (V == NotAVertex)
            break;

        T[V].Known = true;

        for (each W adjacent to V)
            if (!T[W].Known)
                if (T[V].Dist + Cvw < T[W].Dist) {
                    Decrease(T[W].Dist to T[V].Dist + Cvw);
                    T[W].Path = V;
                }
    }
}

注意：

• Dijkstra 不适用于有负边权的图。
• 只要存在负边，贪心选择“当前最小未知距离点”就可能过早确认错误答案。

4.5 Dijkstra 的两种实现#

Implementation 1：直接扫描表找最小未知距离顶点。

V = smallest unknown distance vertex; /* simply scan the table */

复杂度：

适合 dense graph。

Implementation 2：用 priority queue 保存距离。

V = DeleteMin(PQ);

更新距离时：

Decrease(T[W].Dist to T[V].Dist + Cvw);

如果支持 DecreaseKey：

如果不实现 DecreaseKey，可以把更新后的 $W$ 重新插入优先队列：

• 需要一直 DeleteMin，直到弹出一个 unknown vertex。
• 时间仍可写作 $O(|E|\log |V|)$。
• 但可能需要 $|E|$ 次 DeleteMin 和 $|E|$ 空间。

适合 sparse graph。

4.6 Graphs with Negative Edge Costs#

PPT 特别提醒：不能简单地给所有边加同一个常数来消除负边。

原因：

• 不同路径经过的边数可能不同。
• 每条边都加 $\Delta$ 后，边数多的路径会被额外增加更多。
• 原本的最短路顺序可能被改变。

负边权版本的队列松弛算法：

void WeightedNegative(Table T)
{
    Queue Q;
    Vertex V, W;

    Q = CreateQueue(NumVertex);
    MakeEmpty(Q);
    Enqueue(S, Q);

    while (!IsEmpty(Q)) {
        V = Dequeue(Q);

        for (each W adjacent to V)
            if (T[V].Dist + Cvw < T[W].Dist) {
                T[W].Dist = T[V].Dist + Cvw;
                T[W].Path = V;
                if (W is not already in Q)
                    Enqueue(W, Q);
            }
    }

    DisposeQueue(Q);
}

要点：

• 每次发现更短路径就继续把顶点放入队列。
• 如果有 negative-cost cycle，会造成 indefinite loop。
• 每条边不再只处理一次。
• PPT 给出的复杂度：

4.7 Acyclic Graphs#

如果图是 DAG，可以按拓扑序处理顶点。

PPT 的理由：

If the graph is acyclic, vertices may be selected in topological order since when a vertex is selected, its distance can no longer be lowered without any incoming edges from unknown nodes.

复杂度：

且不需要 priority queue。

理解方法：

1. 先做拓扑排序。
2. 按拓扑序依次对每个顶点的出边做 relaxation。
3. 因为所有可能进入当前顶点的前驱都已经处理过，所以当前距离不会再被后面的点降低。

5. AOE Networks and CPM#

5.1 AOE Network#

AOE 是 Activity On Edge。

PPT 中的应用：

scheduling a project

在 AOE 网络中：

• 边 $a_i = \langle v, w \rangle$ 表示一个 activity。
• 顶点 $v_j$ 通常表示事件或阶段完成点。
• 边权表示 activity 的 lasting time。
• dummy activity 可用权重 0 的边表示，只表达依赖关系，不消耗时间。

与 AOV 的区别：

5.2 EC 与 LC#

PPT 记号：

EC[j] / LC[j] ::= earliest / latest completion time for node vj

EC 的计算：

• 从起点开始。
• 对任意 activity $a_i = \langle v,w\rangle$，设持续时间为 $duration(v,w)$。
• 更新：

LC 的计算：

• 从终点开始反向计算。
• 通常先令终点的 $LC$ 等于项目最早完成时间。
• 对任意 activity $a_i = \langle v,w\rangle$：

5.3 Slack Time 与 Critical Path#

对 activity $\langle v,w\rangle$，slack time 表示这条活动最多可以延迟多久而不影响整个项目完成时间。

常用公式：

Critical Path：

path consisting entirely of zero-slack edges.

也就是全部由 slack time 为 0 的活动组成的路径。

复习要点：

• 关键路径上的活动不能延迟。
• 项目的最短完成时间等于终点的 $EC$。
• 可能有多条 critical path。
• AOE/CPM 的计算本质上仍然是 DAG 上的动态规划。

6. All-Pairs Shortest Path Problem#

问题：

For all pairs of $v_i$ and $v_j$ $(i \ne j)$, find the shortest path between.

PPT 给出两类方法：

Method 1：Use single-source algorithm for $|V|$ times。

如果使用类似 Dijkstra 的表扫描版本：

PPT 注记：

works fast on sparse graph.

Method 2：Chapter 10 中的 $O(|V|^3)$ algorithm。

这类算法通常适合 dense graphs，因为结构更紧凑，不需要对每个源点重复维护一套图搜索过程。

7. 本地代码例子：Hamilton Cycle 检查#

仓库中的本地图相关代码：

w8_graph/hamilton.c

它做的是 Hamiltonian cycle 的合法性检查。

代码中的图表示：

int graph[MAXN + 1][MAXN + 1];

即邻接矩阵。

读入无向边时：

graph[v1][v2] = 1;
graph[v2][v1] = 1;

一个序列是 Hamiltonian cycle，需要满足：

1. 序列长度必须是 $n+1$。
2. 最后一个顶点必须等于第一个顶点，表示回到起点。
3. 除了最后重复起点外，前 $n$ 个顶点不能重复。
4. 序列中每一对相邻顶点之间都必须有边。

对应实现逻辑：

int is_hamilton(sequence seq)
{
    if (seq.num != n + 1 || seq.arr[seq.num - 1] != seq.arr[0])
        return 0;

    int vertex[MAXN + 1] = {0};

    for (int i = 0; i < seq.num - 1; i++) {
        if (vertex[seq.arr[i]] == 1)
            return 0;
        vertex[seq.arr[i]]++;

        if (graph[seq.arr[i]][seq.arr[i + 1]] == 0)
            return 0;
    }

    return 1;
}

复杂度：

• 检查长度和首尾：$O(1)$。
• 扫描序列：$O(n)$。
• 邻接矩阵查边：每次 $O(1)$。
• 总复杂度：$O(n)$。

写类似题时的常见坑：

• 忘记要求长度为 $n+1$。
• 只检查了点不重复，没检查每条边是否存在。
• 忘记最后一个点必须回到起点。
• 把 Hamiltonian path 和 Hamiltonian cycle 混淆。

8. 复杂度速查#

9. 做题时的判断路线#

9.1 先看图的类型#

拿到题先判断：

1. 无向图还是有向图？
2. 有没有权重？
3. 权重是否可能为负？
4. 有没有环？
5. 图是稠密还是稀疏？
6. 要求一个源点到所有点，还是所有点对之间？

这些判断基本决定算法选择。

9.2 算法选择#

9.3 判环与不可行#

拓扑排序中：

• 如果最终 \(Counter == NumVertex\)，说明处理了所有顶点，图是 DAG。
• 如果 \(Counter \ne NumVertex\)，说明有环，AOV network 不可行。

最短路中：

• Dijkstra 遇到负边不可靠。
• 负边权图如果有 negative-cost cycle，则最短路可能不存在。
• DAG 最短路不怕负边，因为没有环，不可能反复降低。

9.4 路径恢复#

最短路题常要求输出路径。

通用做法：

1. 每次松弛成功时：

Path[W] = V;

1. 输出目标点 \(T\) 的路径时，从 \(T\) 开始不断回溯：

T -> Path[T] -> Path[Path[T]] -> ... -> S

1. 最后反向输出。

注意：

• 如果 \(Dist[T] == Infinity\)，说明不可达。
• 如果题目要求多个最短路径中的某种特定顺序，要看邻接表顺序或 tie-breaking 规则。

10. 易错点汇总#

1. 无向图一条边会贡献两个度数；有向图入度总和和出度总和都等于边数。
2. 邻接矩阵适合查边，邻接表适合扫边。
3. 拓扑排序只适用于 DAG；有环就没有拓扑序。
4. 拓扑序不唯一，queue 和 stack 可能得到不同合法答案。
5. BFS 的无权最短路成立，是因为所有边权都等价于 1。
6. Dijkstra 的前提是边权非负。
7. 给所有边加同一个常数不能解决负边问题。
8. DAG 最短路可以有负边，因为拓扑序保证不会反复回到前面的点。
9. AOV 是 activity on vertex，AOE 是 activity on edge。
10. Critical path 由 zero-slack edges 组成，不一定只有一条。
11. Hamiltonian cycle 要访问每个顶点一次并回到起点，不等于普通 cycle。