图的定义与拓扑排序

这一节整理图（Graph）的基本概念、常见存储结构，以及 AOV 网络中的拓扑排序。

1. 图的基本定义

一个图通常记为：

G(V, E)

其中：

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

按照边是否有方向，图可以分成两类：

无向图（Undirected Graph）：边没有方向，(vi, vj) 和 (vj, vi) 表示同一条边。
有向图（Directed Graph / Digraph）：边有方向，<vi, vj> 表示从 vi 指向 vj，其中 vi 是 tail，vj 是 head。

本课程讨论的图默认有两个限制：

不允许自环（self loop）。
不考虑重边图（multigraph）。

2. 完全图

完全图是指在限制条件下，边数达到最大值的图。

如果顶点数为 n：

无向完全图的边数为：

\[ C_n^2 = \frac{n(n-1)}{2} \]

有向完全图的边数为：

\[ P_n^2 = n(n-1) \]

这里有向完全图里 <vi, vj> 和 <vj, vi> 是两条不同的有向边，所以边数是无向完全图的两倍。

3. 相邻与关联

在无向图中，如果有边 (vi, vj)：

vi 和 vj 是相邻的（adjacent）。
(vi, vj) 关联（incident on）vi 和 vj。

在有向图中，如果有边 <vi, vj>：

vi is adjacent to vj。
vj is adjacent from vi。
<vi, vj> 关联 vi 和 vj。

4. 子图、路径与连通性

子图 G' ⊂ G 满足：

V(G') ⊆ V(G) && E(G') ⊆ E(G)

路径是图中从一个顶点到另一个顶点的一串顶点序列。
从 vp 到 vq 的路径可以写成：

{ vp, vi1, vi2, ..., vin, vq }

并且相邻顶点之间对应的边必须属于 E(G)。

5. 树、DAG 与强连通

几个重要定义：

树：连通且无环的图。
DAG：Directed Acyclic Graph，即有向无环图。
强连通有向图：对任意两个顶点 vi 和 vj，既存在从 vi 到 vj 的有向路径，也存在从 vj 到 vi 的有向路径。
弱连通有向图：忽略边的方向后，图是连通的。
强连通分量：极大的强连通子图。

6. 度、入度与出度

无向图中，一个顶点的度（degree）是与它关联的边数。

有向图中要区分：

入度（in-degree）：指向该顶点的边数。
出度（out-degree）：从该顶点指出去的边数。
度：入度与出度之和。

例如一个顶点 v 若有 3 条边指向它，1 条边从它指出，则：

in-degree(v) = 3
out-degree(v) = 1
degree(v) = 4

对于有 n 个顶点、e 条边的无向图，所有顶点度数之和等于边数的两倍：

\[ e = \frac{1}{2}\sum_{i=0}^{n-1} d_i \]

其中 di = degree(vi)。

7. 图的存储：邻接矩阵

对于有 n 个顶点的图，可以用 n × n 的邻接矩阵表示：

adj_mat[i][j] = 1, if (vi, vj) or <vi, vj> belongs to E(G)
adj_mat[i][j] = 0, otherwise

如果图是无向图，邻接矩阵是对称矩阵。

邻接矩阵的特点

优点：

判断两点之间是否有边很快：O(1)。
实现简单，适合稠密图。

缺点：

空间复杂度为 O(n^2)。
如果图很稀疏，矩阵中大部分位置都是 0，会浪费空间。
要遍历所有边时，通常需要扫描矩阵，时间为 O(n^2)。

无向图中，顶点 i 的度为：

\[ degree(i) = \sum_{j=0}^{n-1} adj\_mat[i][j] \]

有向图中，如果要得到总度数，需要把出边和入边都算上：

\[ degree(i) = \sum_{j=0}^{n-1} adj\_mat[i][j] + \sum_{j=0}^{n-1} adj\_mat[j][i] \]

无向图矩阵压缩

因为无向图的邻接矩阵对称，可以只存储一半矩阵。
如果把下三角部分按行存成一维数组：

adj_mat[n(n+1)/2] = { a11, a21, a22, ..., an1, ..., ann }

那么 aij 的一维下标可以通过下面的式子计算：

i * (i - 1) / 2 + j

这里的下标公式取决于具体是从 0 开始还是从 1 开始，写代码时要统一约定。

8. 图的存储：邻接表

邻接表的思路是：把邻接矩阵的每一行替换成一个链表。

例如邻接矩阵：

0 1 0
1 0 1
0 0 0

可以表示成：

graph[0]: 1
graph[1]: 0 -> 2
graph[2]:

每个链表中结点的顺序不重要。

邻接表的特点

对于无向图：

每个顶点需要一个表头。
每条无向边会在两个顶点的链表中各出现一次。
空间约为 n 个表头加 2e 个边结点。

如果用指针和整数估算空间，课件中写作：

S = n heads + 2e nodes = (n + 2e) ptrs + 2e ints

邻接表适合稀疏图。
遍历所有边的时间复杂度为：

O(n + e)

在无向图中：

Degree(i) = graph[i] 中的结点数

9. 有向图中的入度处理

对于有向图，普通邻接表很容易得到某个顶点的出边，但不方便直接得到入度。

常见方法有两种。

方法一：逆邻接表

额外维护一组 inverse adjacency lists。
如果原图中有边 <i, j>，则：

在 graph[i] 中记录 j。
在 inv[j] 中记录 i。

这样可以快速得到某个点有哪些前驱结点，也方便统计入度。

方法二：十字链表 / 多重链表

对有向边 <i, j> 建一个边结点，同时把它挂在：

以 i 为 tail 的行链表中。
以 j 为 head 的列链表中。

这种结构可以同时沿出边方向和入边方向遍历。

10. 无向图的多重链表

无向图的邻接表中，一条边 (i, j) 通常会存两次：

graph[i]: j
graph[j]: i

多重链表的想法是把这两个边结点合并成一个边结点，并让它同时出现在两个顶点的边表中。

边结点通常包含：

mark：标记这条边是否已经被检查过。
v1、v2：边的两个端点。
next_v1、next_v2：分别指向这条边在两个端点链表中的下一条边。

这种表示比普通邻接表更复杂，但在某些算法中很有用，特别是需要“标记边，然后快速找到下一条边”的场景。

如果图带权：

邻接矩阵中可以让 adj_mat[i][j] = weight。
邻接表或多重链表中可以给边结点增加 weight 字段。

11. AOV 网络

AOV Network 是一种有向图：

V(G) 表示活动（activities）。
E(G) 表示活动之间的先后关系（precedence relations）。

例如在课程先修关系中：

C1 -> C3

表示 C1 是 C3 的先修课程。

12. 偏序关系

先后关系如果同时满足下面两个性质，就是偏序关系：

传递性（transitive）：如果 i -> k 且 k -> j，则 i -> j。
反自反性（irreflexive）：不允许 i -> i。

课件中特别强调：如果项目是可行的，先后关系必须是反自反的。
如果出现 i 是 i 的前驱，就意味着活动 i 必须在自己开始前完成，这是不可能的，也说明图中存在环。

13. 拓扑序

拓扑序（topological order）是对图中顶点的一种线性排序，使得：

如果 i 是 j 的前驱，那么在线性序列中 i 必须出现在 j 之前。

拓扑序通常用于：

课程先修关系安排
项目任务排期
编译依赖分析
判断一个 AOV 网络是否可行

注意：一个网络的拓扑序不一定唯一。
只要满足所有前驱都排在后继之前，就都是合法的拓扑序。

14. 课程先修关系例子

课件中的课程依赖可以整理如下：

课程	名称	先修课程
C1	Programming I	None
C2	Discrete Mathematics	None
C3	Data Structure	C1, C2
C4	Calculus I	None
C5	Calculus II	C4
C6	Linear Algebra	C5
C7	Analysis of Algorithms	C3, C6
C8	Assembly Language	C3
C9	Operating Systems	C7, C8
C10	Programming Languages	C7
C11	Compiler Design	C10
C12	Artificial Intelligence	C7
C13	Computational Theory	C7
C14	Parallel Algorithms	C13
C15	Numerical Analysis	C6

一种合法的拓扑序是：

C1, C2, C4, C3, C5, C6, C7, C15, C8, C10, C9, C12, C13, C11, C14

这个序列中，每门课都排在所有依赖它的课程之前。

15. 朴素拓扑排序

拓扑排序的基本思路：

找到一个入度为 0 的、还没有被编号的顶点。
输出它，或者给它分配下一个拓扑编号。
删除它的所有出边，相当于把它所有邻接点的入度减 1。
重复以上过程。
如果找不到入度为 0 的顶点，但还有顶点没有输出，说明图中有环。

课件中的伪代码：

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

    for (Counter = 0; Counter < NumVertex; Counter++) {
        V = FindNewVertexOfDegreeZero();  /* O(|V|) */

        if (V == NotAVertex) {
            Error("Graph has a cycle");
            break;
        }

        TopNum[V] = Counter;  /* or output V */

        for (each W adjacent to V) {
            Indegree[W]--;
        }
    }
}

因为每一轮都要重新找一个入度为 0 的顶点，查找本身是 O(|V|)，总复杂度为：

T = O(|V|^2)

16. 改进拓扑排序

改进方法：用一个特殊容器保存所有当前入度为 0 的未编号顶点。
这个容器可以是队列，也可以是栈。

用队列时，流程如下：

先扫描所有顶点，把初始入度为 0 的顶点全部入队。
每次从队列中取出一个顶点 V。
输出 V 或给 V 分配拓扑编号。
遍历 V 的所有邻接点 W，执行 --Indegree[W]。
如果某个 W 的入度变成 0，就把它加入队列。
最后如果输出顶点数小于总顶点数，说明图中有环。

课件中的伪代码：

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);
}

每个顶点最多入队、出队一次，每条边最多被检查一次，所以复杂度为：

T = O(|V| + |E|)

17. 拓扑排序的重点

考试或写代码时可以抓住下面几个点：

拓扑排序只适用于有向无环图。
AOV 网络可行，当且仅当图中没有环。
入度为 0 的顶点表示当前没有未完成的前驱活动。
每次输出一个入度为 0 的顶点，并“删除”它的出边。
如果所有顶点都能输出，得到一个拓扑序。
如果输出过程中队列提前为空，但仍有顶点没有输出，说明存在环。
拓扑序可能不唯一，队列、栈或不同的扫描顺序都可能得到不同结果。

18. 一页速记

概念	关键点
图	`G(V, E)`，顶点有限非空，边有限
无向图	`(vi, vj) = (vj, vi)`
有向图	`<vi, vj>` 有 tail 和 head
完全无向图边数	`n(n-1)/2`
完全有向图边数	`n(n-1)`
树	连通且无环
DAG	有向无环图
强连通	任意两点之间双向可达
邻接矩阵	查边快，空间 `O(n^2)`
邻接表	适合稀疏图，遍历边 `O(n+e)`
AOV 网络	顶点表示活动，边表示先后关系
拓扑序	前驱必须排在后继之前
朴素拓扑排序	`O(\|V\|^2)`
队列优化拓扑排序	`O(\|V\| + \|E\|)`
有环判断	输出顶点数小于 `NumVertex`