【王道考研·数据结构】第六章 图（整章完整版）

引言

第六章是数据结构里最核心的章节之一，因为它把线性关系和层次关系进一步扩展到了更一般的网状关系。图是一种比树更普遍的结构，可以用来描述城市交通、社交网络、网页链接、工程任务等各种复杂关系。

本章可以整理成四条主线：

  1. 图的基本概念与存储结构（邻接矩阵、邻接表、十字链表、邻接多重表）
  2. 图的遍历（BFS、DFS）
  3. 最小生成树与最短路径（Prim、Kruskal、Dijkstra、Floyd）
  4. 拓扑排序与关键路径（AOV、AOE网络）

本篇会把第六章所有 PPT 内容合并成一篇完整文章，并且把 PPT 中只给结论、图示但没有讲透的地方一并补全。

图像化理解（Mermaid）

一句话：先学图怎么存，再学图上怎么跑算法。

一、图的基本概念

1. 图的定义

图 G 由两个集合 V 和 E 组成，记作 G = (V, E)：

  • V：顶点集（Vertex），非空有限集合
  • E：边集（Edge），有限集合
1
2
V(G) = {v1, v2, v3, v4}
E(G) = {(v1,v2), (v1,v3), (v2,v4), (v3,v4)}
1
2
3
4
5
v1 -------- v2
|  \       /
|   \    /
|    \ /
v3----v4

2. 有向图与无向图

无向图

  • 边用无序对 (v, w) 表示
  • (v, w) 和 (w, v) 是同一条边
  • 无向图边数上界：n(n-1)/2

有向图

  • 边用有序对 <v, w> 表示
  • <v, w> 表示从 v 指向 w 的弧
  • 有向图边数上界：n(n-1)
1
2
3
4
无向图              有向图
    v1                 v1 → v2
   /  \               ↗  ↘
  v3---v2             v3 ← v4

3. 顶点的度

无向图

  • 度：与该顶点相连的边的数目
    -握手定理：所有顶点的度之和 = 2 × 边数

有向图

  • 出度：从该顶点出发的弧的数目
  • 入度：指向该顶点的弧的数目
  • 度 = 出度 + 入度
  • 握手定理：所有顶点的出度之和 = 所有顶点的入度之和 = 边数

4. 简单图与多重图

  • 简单图：不存在重复边，不存在自环
  • 多重图：存在重复边

考研中默认讨论的都是简单图。

5. 路径、回路、环

  • 路径：从一个顶点到另一个顶点所经过的顶点序列
  • 路径长度：路径上边的数目
  • 回路（环）：起点和终点相同的路径
  • 简单路径：顶点不重复的路径
  • 简单回路：顶点不重复的回路

6. 连通图与强连通图

无向图

  • 连通：两个顶点之间存在路径
  • 连通图：任意两个顶点都连通的图
  • 连通分量：无向图中的极大连通子图

有向图

  • 强连通：两个顶点之间存在双向路径
  • 强连通图：任意两个顶点都强连通
  • 强连通分量：有向图中的极大强连通子图
1
2
3
4
连通图示例：           非连通图示例：
  v1 --- v2             v1 --- v2
  |      |               |      
  v3 --- v4             v3     v4 (v3和v4不连通)

7. 生成树与生成森林

  • 生成树：连通图的极小连通子图（包含所有顶点、n-1条边）
  • 生成森林：非连通图各连通分量的生成树组成

8. 权值与网

  • 权值：边上带的数值（距离、成本等）
  • 网：带权的图（有权图）

二、图的存储结构

1. 邻接矩阵法

存储方式

用一个 n×n 的二维数组存储：

1
2
3
4
5
6
7
    | 0  1  2  3  (列号)
----|---------------
 0  | 0  1  1  0
 1  | 1  0  0  1
 2  | 1  0  0  1
 3  | 0  1  1  0
(行号)
  • A[i][j] = 1（或权值）：表示顶点 i 到 j 有边
  • A[i][j] = 0（或∞）：表示无边

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#define MaxVertexNum 100
#define INF 65535

typedef struct {
    char Vex[MaxVertexNum];      // 顶点表
    int Edge[MaxVertexNum][MaxVertexNum];  // 邻接矩阵
    int vexnum, arcnum;           // 顶点数和边数
} MGraph;

// 无向网（带权）的创建
void CreateMGraph(MGraph &G) {
    scanf("%d%d", &G.vexnum, &G.arcnum);
    
    // 初始化顶点
    for (int i = 0; i < G.vexnum; i++) {
        scanf("%c", &G.Vex[i]);  // 读取顶点信息
    }
    
    // 初始化邻接矩阵（无边用INF表示）
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            G.Edge[i][j] = (i == j) ? 0 : INF;
        }
    }
    
    // 读入边信息
    for (int k = 0; k < G.arcnum; k++) {
        int v1, v2, w;
        scanf("%d%d%d", &v1, &v2, &w);
        G.Edge[v1][v2] = w;
        G.Edge[v2][v1] = w;  // 无向图对称
    }
}

复杂度分析

操作时间复杂度
判断两顶点是否相邻O(1)
获取某顶点的度O(n)
空间复杂度O(n²)

特点

  • 适合稠密图
  • 空间复杂度高 O(n²)
  • 矩阵A的i行/j列非零元素个数 = 对应顶点的度（无向图）

2. 邻接表法

存储方式

每个顶点建立一个单链表，存储与其相邻的所有顶点。

1
2
3
4
v0 → [v1] → [v2]
v1 → [v0] → [v3]
v2 → [v0] → [v3]
v3 → [v1] → [v2]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#define MaxVertexNum 100

// 边表结点
typedef struct ArcNode {
    int adjvex;           // 邻接点下标
    struct ArcNode *next; // 指向下一条边
    int weight;           // 权值（网需要）
} ArcNode;

// 顶点表结点
typedef struct VNode {
    char data;            // 顶点信息
    ArcNode *firstarc;    // 指向第一条边
} VNode, AdjList[MaxVertexNum];

// 图
typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

// 添加边（无向图）
void AddEdge(ALGraph &G, int i, int j) {
    // i → j
    ArcNode *p = new ArcNode;
    p->adjvex = j;
    p->next = G.vertices[i].firstarc;
    G.vertices[i].firstarc = p;
    
    // j → i
    p = new ArcNode;
    p->adjvex = i;
    p->next = G.vertices[j].firstarc;
    G.vertices[j].firstarc = p;
}

复杂度分析

操作时间复杂度
判断两顶点是否相邻O(degree(v))
获取某顶点的度O(degree(v))
空间复杂度O(V + E)

特点

  • 适合稀疏图
  • 节省空间
  • 无向图边表结点数 = 2E，有向图边表结点数 = E

3. 十字链表（有向图）

同时存储出边和入边，解决邻接表无法同时获取入度和出度的问题。

1
2
3
4
5
6
7
8
9
10
11
12
十字链表结构示意：
       ┌─────────┐
       │  data   │ firstout（出边链表头）
       │   v0    │ firstin（入边链表头）
       └─────────┘
            │
      ┌─────┴─────┐
      ▼           ▼
   [v0→v1]     [v2→v0]
      │           │
      ▼           ▼
   [v0→v2]      null

适用于需要频繁获取入度的有向图算法（如拓扑排序）。

4. 邻接多重表（无向图）

每条边只存储一次，同时关联两个顶点，解决邻接表中删边需要删除两个结点的问题。

1
2
3
4
5
6
邻接多重表结构示意：
边结点：
┌─────┬─────┬─────┬─────┐
│mark │ i   │ j   │ ilink│ jlink│
└─────┴─────┴─────┴─────┘
   标记  顶点i  顶点j  下一个i起点的边 下一个j起点的边

适用于需要频繁删边的无向图算法（如割点、桥的判定）。

5. 四种存储结构对比

存储结构空间复杂度适用场景特点
邻接矩阵O(V²)稠密图判断相邻 O(1)，度获取 O(V)
邻接表O(V+E)稀疏图空间省，判断相邻 O(degree)
十字链表O(V+E)有向图兼顾出入度
邻接多重表O(V+E)无向图删边高效

三、图的基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 图的基本操作（邻接矩阵实现）

// 判断是否存在边 (x, y)
bool Adjacent(MGraph G, int x, int y) {
    return G.Edge[x][y] != 0 && G.Edge[x][y] != INF;
}

// 获取第一个邻接点
int FirstNeighbor(MGraph G, int v) {
    for (int i = 0; i < G.vexnum; i++) {
        if (G.Edge[v][i] != 0 && G.Edge[v][i] != INF)
            return i;
    }
    return -1;
}

// 获取下一个邻接点
int NextNeighbor(MGraph G, int v, int w) {
    for (int i = w + 1; i < G.vexnum; i++) {
        if (G.Edge[v][i] != 0 && G.Edge[v][i] != INF)
            return i;
    }
    return -1;
}

// 获取顶点度数（无向图）
int Degree(MGraph G, int v) {
    int count = 0;
    for (int i = 0; i < G.vexnum; i++) {
        if (G.Edge[v][i] != 0 && G.Edge[v][i] != INF)
            count++;
    }
    return count;
}

四、图的遍历

1. 广度优先遍历（BFS）

算法思想

层序遍历：先访问起始顶点，再访问其所有邻接点，然后访问邻接点的邻接点……

1
2
3
4
5
6
7
8
9
10
BFS层序遍历示例：
    v1(第1层)
   /    \
v2      v3(第2层)
  \      /
   v4  v5(第3层)
    \  /
    v6(第4层)

遍历顺序：v1 → v2 → v3 → v4 → v5 → v6

代码实现（邻接表）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define MaxVertexNum 100
bool visited[MaxVertexNum];
Queue Q;

void BFS(ALGraph G, int v) {
    visit(v);
    visited[v] = true;
    EnQueue(Q, v);
    
    while (!IsEmpty(Q)) {
        DeQueue(Q, v);
        for (ArcNode *p = G.vertices[v].firstarc; p; p = p->next) {
            int w = p->adjvex;
            if (!visited[w]) {
                visit(w);
                visited[w] = true;
                EnQueue(Q, w);
            }
        }
    }
}

// 遍历非连通图
void BFSTraverse(ALGraph G) {
    for (int v = 0; v < G.vexnum; v++) {
        if (!visited[v])
            BFS(G, v);
    }
}

复杂度分析

存储结构时间复杂度空间复杂度
邻接矩阵O(V²)O(V)
邻接表O(V + E)O(V)

BFS 生成树

1
2
3
4
5
6
原图：              BFS生成树：
  v1                v1
 /  \              / \
v2   v3           v2  v3
|    |            |   |
v4   v5           v4  v5

2. 深度优先遍历（DFS）

算法思想

类似树的先序遍历：尽可能深地访问顶点，走不通再回溯。

代码实现（邻接表）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define MaxVertexNum 100
bool visited[MaxVertexNum];

void DFS(ALGraph G, int v) {
    visit(v);
    visited[v] = true;
    
    for (ArcNode *p = G.vertices[v].firstarc; p; p = p->next) {
        int w = p->adjvex;
        if (!visited[w])
            DFS(G, w);
    }
}

// 遍历非连通图
void DFSTraverse(ALGraph G) {
    for (int v = 0; v < G.vexnum; v++) {
        if (!visited[v])
            DFS(G, v);
    }
}

复杂度分析

存储结构时间复杂度空间复杂度
邻接矩阵O(V²)O(V)
邻接表O(V + E)O(V)

DFS 生成树/森林

1
2
3
4
5
6
原图：              DFS生成树：
  v1                v1
 /  \              / \
v2   v3           v2  v3
|    |            |   |
v4   v5           v4  v5

3. BFS 与 DFS 对比

特性BFSDFS
数据结构队列栈（或递归）
生成树宽而短窄而深
适用场景最短路径、层次遍历拓扑排序、连通分量
空间复杂度O(V)O(V)

五、最小生成树

1. 基本概念

  • 生成树：包含图中所有顶点的极小连通子图
  • 最小生成树（MST）：权值之和最小的生成树

MST 性质

切分定理：给定任意切分，横切该切分的所有边中，权重最小的边必然属于某个最小生成树。

1
2
3
4
5
6
7
切分示意图：
  ┌───────┬───────┐
  │ A     │   B   │  ← 切分
  │ v1    │   v2  │
  │       │   v3  │
  └───────┴───────┘
  边(v1,v2) 边(v1,v3) 边(v2,v3) → 横切边

2. Prim 算法

算法思想

从某个顶点开始，逐步加入顶点，每次选择与当前生成树距离最短的顶点。

1
2
3
4
5
6
7
8
9
Prim算法过程示例：
初始：只在集合U={v1}中

第1步：找到与v1距离最近的边(v1,v2)，加入v2
第2步：找到与{v1,v2}距离最近的边(v2,v4)，加入v4
第3步：找到与{v1,v2,v4}距离最近的边(v1,v3)，加入v3
第4步：找到与{v1,v2,v3,v4}距离最近的边(v3,v4)，加入v4

最终得到MST

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void Prim(MGraph G) {
    int min, k;
    int adjvex[MaxVertexNum];  // 候选边对应的另一顶点
    int lowcost[MaxVertexNum]; // 候选边的权值
    
    // 初始化：0号顶点加入生成树
    lowcost[0] = 0;
    adjvex[0] = 0;
    for (int i = 1; i < G.vexnum; i++) {
        lowcost[i] = G.Edge[0][i];
        adjvex[i] = 0;
    }
    
    for (int i = 1; i < G.vexnum; i++) {
        // 找到权值最小的边
        min = INF;
        for (int j = 1; j < G.vexnum; j++) {
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        
        // 输出这条边
        printf("(%d, %d)\n", adjvex[k], k);
        lowcost[k] = 0;  // 加入生成树
        
        // 更新候选边
        for (int j = 1; j < G.vexnum; j++) {
            if (G.Edge[k][j] < lowcost[j]) {
                lowcost[j] = G.Edge[k][j];
                adjvex[j] = k;
            }
        }
    }
}

复杂度分析

时间复杂度适用场景
O(V²)稠密图

3. Kruskal 算法

算法思想

每次选择权值最小且不构成环的边，逐步构建生成树。

1
2
3
4
5
6
7
8
9
Kruskal算法过程示例：

初始：各顶点独立，候选边按权值排序
边权值：(v1,v2)=1, (v2,v4)=2, (v1,v3)=3, (v3,v4)=3, (v2,v3)=4

第1步：取(v1,v2)=1，不成环，加入
第2步：取(v2,v4)=2，不成环，加入
第3步：取(v1,v3)=3，不成环，加入
第4步：取(v3,v4)=3，成环，丢弃

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// 并查集实现
int Find(int parent[], int x) {
    while (parent[x] >= 0) 
        x = parent[x];
    return x;
}

bool Union(int parent[], int x, int y) {
    int rootX = Find(parent, x);
    int rootY = Find(parent, y);
    if (rootX == rootY) return false;  // 成环
    parent[rootY] = rootX;
    return true;
}

// Kruskal算法
typedef struct {
    int u, v, w;
} Edge;

int Kruskal(MGraph G) {
    Edge edges[MaxVertexNum * MaxVertexNum];
    int parent[MaxVertexNum];
    int edgeCount = 0;
    int sum = 0;
    
    // 初始化：所有顶点都是独立的
    for (int i = 0; i < G.vexnum; i++)
        parent[i] = -1;
    
    // 收集所有边
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = i + 1; j < G.vexnum; j++) {
            if (G.Edge[i][j] != INF) {
                edges[edgeCount].u = i;
                edges[edgeCount].v = j;
                edges[edgeCount].w = G.Edge[i][j];
                edgeCount++;
            }
        }
    }
    
    // 按权值排序（此处略，可用qsort）
    // sort(edges, edges + edgeCount, cmp);
    
    // 依次取边
    for (int i = 0; i < edgeCount; i++) {
        if (Union(parent, edges[i].u, edges[i].v)) {
            sum += edges[i].w;
            printf("(%d, %d)\n", edges[i].u, edges[i].v);
        }
    }
    return sum;
}

复杂度分析

时间复杂度适用场景
O(E log E)稀疏图

4. Prim vs Kruskal

算法思想时间复杂度适用场景
Prim逐点加入O(V²)稠密图
Kruskal逐边加入O(E log E)稀疏图

六、最短路径

1. BFS 算法（无权图）

适用场景

所有边权值相同的最短路径。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void BFS_MIN_Distance(ALGraph G, int v) {
    int distance[MaxVertexNum];
    int path[MaxVertexNum];
    
    for (int i = 0; i < G.vexnum; i++) {
        distance[i] = -1;
        path[i] = -1;
    }
    
    distance[v] = 0;
    Queue Q;
    EnQueue(Q, v);
    
    while (!IsEmpty(Q)) {
        DeQueue(Q, v);
        for (ArcNode *p = G.vertices[v].firstarc; p; p = p->next) {
            int w = p->adjvex;
            if (distance[w] == -1) {
                distance[w] = distance[v] + 1;
                path[w] = v;
                EnQueue(Q, w);
            }
        }
    }
}

复杂度

O(V + E)

2. Dijkstra 算法

适用场景

单源最短路径，且所有边权值非负。

算法思想

类似 Prim，逐步加入距离源点最近的顶点。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void Dijkstra(MGraph G, int v0) {
    int dist[MaxVertexNum];    // 最短路径长度
    int path[MaxVertexNum];    // 前驱顶点
    bool S[MaxVertexNum];      // 已确定最短路径的顶点集合
    
    // 初始化
    for (int i = 0; i < G.vexnum; i++) {
        dist[i] = G.Edge[v0][i];
        S[i] = false;
        path[i] = (G.Edge[v0][i] != INF) ? v0 : -1;
    }
    S[v0] = true;
    dist[v0] = 0;
    
    for (int i = 1; i < G.vexnum; i++) {
        // 找到dist最小的顶点u
        int min = INF, u = -1;
        for (int j = 0; j < G.vexnum; j++) {
            if (!S[j] && dist[j] < min) {
                min = dist[j];
                u = j;
            }
        }
        
        S[u] = true;
        
        // 更新dist
        for (int j = 0; j < G.vexnum; j++) {
            if (!S[j] && G.Edge[u][j] != INF 
                && dist[u] + G.Edge[u][j] < dist[j]) {
                dist[j] = dist[u] + G.Edge[u][j];
                path[j] = u;
            }
        }
    }
}

复杂度分析

存储结构时间复杂度
邻接矩阵O(V²)
邻接表 + 堆O((V+E) log V)

⚠️ 重要限制

Dijkstra 算法不能处理负权边！

1
2
3
4
5
6
7
8
9
10
11
负权边示例导致的问题：

v0 → v1: 2
v0 → v2: 5  
v1 → v2: -4

正确最短路径：v0→v1→v2 = 2 + (-4) = -2
Dijkstra结果：v0→v2 = 5（错误）

因为Dijkstra第一次选中v1后，v2的最短路径就"确定"了
但实际还有更短的负权路径

3. Floyd 算法

适用场景

多源最短路径（任意两点间最短路径）。

算法思想

动态规划：允许通过中间顶点中转。

1
2
3
Floyd核心思想：
d[i][j] = min(d[i][j], d[i][k] + d[k][j])
允许经过k中转，看是否能缩短距离

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void Floyd(MGraph G) {
    int A[MaxVertexNum][MaxVertexNum];
    int path[MaxVertexNum][MaxVertexNum];
    
    // 初始化
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            A[i][j] = G.Edge[i][j];
            path[i][j] = -1;
        }
    }
    
    // 动态规划
    for (int k = 0; k < G.vexnum; k++) {
        for (int i = 0; i < G.vexnum; i++) {
            for (int j = 0; j < G.vexnum; j++) {
                if (A[i][k] != INF && A[k][j] != INF 
                    && A[i][k] + A[k][j] < A[i][j]) {
                    A[i][j] = A[i][k] + A[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}

复杂度分析

O(V³)，适合小规模图

4. 三种最短路径算法对比

算法作用时间复杂度限制
BFS单源无权最短路径O(V+E)边权相同
Dijkstra单源非负权最短路径O(V²) 或 O(E log V)不能有负权
Floyd多源最短路径O(V³)不能有负环

七、有向无环图描述表达式

1. 基本概念

  • DAG：有向无环图（Directed Acyclic Graph）
  • 可用于表示算术表达式，避免重复计算

2. 表达式 DAG 构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
表达式：(a + b) * (a + b) + c

普通二叉树（重复）：
        +
       / \
      *   c
     / \
    +   +
   / \ / \
  a  b a  b

DAG（共享公共子表达式）：
        +
       / \
      *   c
     / \
    +   +
   / \   \
  a   b   |
   \     /
     a ←┘

3. 构造方法

按照运算符优先级建树，然后合并相同子表达式。

八、拓扑排序

1. AOV 网

  • AOV：Activity On Vertex（用顶点表示活动）
  • 顶点表示活动，边表示活动间的优先关系
  • 必须是 DAG

2. 拓扑排序算法

算法思想

每次选择入度为 0 的顶点输出，然后删除该顶点及其出边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
bool TopologicalSort(ALGraph G) {
    int indegree[MaxVertexNum];
    Stack S;
    
    // 计算所有顶点入度
    for (int i = 0; i < G.vexnum; i++) {
        indegree[i] = 0;
    }
    for (int i = 0; i < G.vexnum; i++) {
        for (ArcNode *p = G.vertices[i].firstarc; p; p = p->next) {
            indegree[p->adjvex]++;
        }
    }
    
    // 入度为0的顶点入栈
    for (int i = 0; i < G.vexnum; i++) {
        if (indegree[i] == 0)
            Push(S, i);
    }
    
    int count = 0;
    while (!IsEmpty(S)) {
        int v;
        Pop(S, v);
        printf("%d ", v);
        count++;
        
        for (ArcNode *p = G.vertices[v].firstarc; p; p = p->next) {
            int w = p->adjvex;
            indegree[w]--;
            if (indegree[w] == 0)
                Push(S, w);
        }
    }
    
    return count == G.vexnum;  // 是否所有顶点都输出
}

复杂度

O(V + E)

3. 逆拓扑排序

每次选择出度为 0 的顶点输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 逆拓扑排序（邻接表）
bool InverseTopologicalSort(ALGraph G) {
    int outdegree[MaxVertexNum];
    Stack S;
    
    // 计算出度
    for (int i = 0; i < G.vexnum; i++) {
        outdegree[i] = 0;
    }
    for (int i = 0; i < G.vexnum; i++) {
        for (ArcNode *p = G.vertices[i].firstarc; p; p = p->next) {
            outdegree[i]++;
        }
    }
    
    for (int i = 0; i < G.vexnum; i++) {
        if (outdegree[i] == 0)
            Push(S, i);
    }
    
    int count = 0;
    while (!IsEmpty(S)) {
        int v;
        Pop(S, v);
        printf("%d ", v);
        count++;
        
        // 删除入边（相当于减少源点出度）
        for (ArcNode *p = G.vertices[v].firstarc; p; p = p->next) {
            int w = p->adjvex;
            outdegree[w]--;
            if (outdegree[w] == 0)
                Push(S, w);
        }
    }
    
    return count == G.vexnum;
}

4. 拓扑排序唯一性

若图中只有一个入度为 0 的顶点，则拓扑排序唯一。

九、关键路径

1. AOE 网

  • AOE：Activity On Edge（用边表示活动）
  • 顶点表示事件（开始/结束），边表示活动
  • 通常用于工程计划
1
2
3
4
5
6
7
AOE网示例：
    1        3
  ↙  ↓    ↙  ↓
0 → a1 → 2 ← a4
  ↘  ↑    ↘  ↑
    2        4
a1(v0→v2), a2(v0→v1), a3(v1→v2), a4(v1→v3), a5(v2→v3)

2. 关键路径概念

  • 事件最早发生时间 ve(k)：从起点到 vk 的最长路径长度
  • 事件最晚发生时间 vl(k)：在不影响整个工程工期的前提下，事件 vk 允许的最晚发生时间
  • 活动最早开始时间 e(i)：活动 ai 的起点事件的最早发生时间
  • 活动最晚开始时间 l(i)：活动 ai 的终点事件的最晚发生时间减去 ai 的持续时间
  • 关键活动：e(i) = l(i) 的活动
  • 关键路径：由关键活动组成的路径

3. ve/vl 计算公式

ve（最早发生时间）

1
2
3
ve(源点) = 0
ve(k) = max{ ve(j) + <j, k>的权值 }
        （j 为 vk 的前驱）

vl（最晚发生时间）

1
2
3
vl(汇点) = ve(汇点)
vl(j) = min{ vl(k) - <j, k>的权值 }
        （k 为 vj 的后继）

4. e/l 计算与关键活动

1
2
3
4
e(i) = ve(活动起点)
l(i) = vl(活动终点) - 活动持续时间

关键活动：l(i) == e(i)

5. 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void CriticalPath(ALGraph G) {
    int ve[MaxVertexNum], vl[MaxVertexNum];
    
    // 1. 计算ve（拓扑顺序）
    for (int i = 0; i < G.vexnum; i++) ve[i] = 0;
    // ... 拓扑排序过程中更新ve
    
    // 2. 初始化vl
    for (int i = 0; i < G.vexnum; i++) 
        vl[i] = ve[G.vexnum - 1];
    
    // 3. 计算vl（逆拓扑顺序）
    // ... 逆拓扑排序过程中更新vl
    
    // 4. 找关键活动
    for (int i = 0; i < G.vexnum; i++) {
        for (ArcNode *p = G.vertices[i].firstarc; p; p = p->next) {
            int k = p->adjvex;
            int e = ve[i];
            int l = vl[k] - p->weight;
            if (e == l) 
                printf("<%d,%d> is critical activity\n", i, k);
        }
    }
}

十、本章最容易写错、算错、混淆的地方

  1. 邻接矩阵的空间复杂度是 O(V²)，不是 O(E)
  2. 邻接表的空间复杂度是 O(V+E)
  3. 十字链表用于有向图，邻接多重表用于无向图
  4. BFS/DFS 的时间复杂度：邻接矩阵 O(V²)，邻接表 O(V+E)
  5. Prim 算法类似 Dijkstra，但比较的是到集合的距离，不是到源点的距离
  6. Kruskal 需要用并查集判断是否成环
  7. Dijkstra 不能处理负权边！
  8. Floyd 可以处理负权边，但不能有负环
  9. 拓扑排序检查环：输出顶点数 < 总顶点数则存在环
  10. 拓扑排序唯一性：只有当入度为0的顶点唯一时，唯一
  11. 关键路径是所有路径中长度最长的，不是最短的
  12. 事件最早用 max（取最长），事件最晚用 min（取最短）
  13. 活动最早等于起点事件的 ve，活动最晚等于终点事件的 vl 减持续时间
  14. 缩短关键活动可以缩短整个工期，但缩短到一定程度后可能产生新的关键路径

十一、图像化总览（Mermaid）

1. BFS 与 DFS 访问风格图

2. Prim 与 Kruskal 选边风格图

3. 三类最短路定位图

4. 拓扑排序判环图

5. 关键路径计算链图

十二、易错点与易混淆点（详细版）

A. 易混淆点（A vs B）

  1. 连通图 vs 强连通图

    • 连通图：无向图里任意两点可达
    • 强连通图：有向图里任意两点双向可达

  2. 邻接矩阵 vs 邻接表

    • 邻接矩阵判断相邻 O(1)，空间 O(V^2)
    • 邻接表空间 O(V+E)，更适合稀疏图

  3. Prim vs Dijkstra

    • Prim 比较“到生成树集合的最小代价”
    • Dijkstra 比较“到源点的最短距离”
    • 两者流程像，但优化目标不同。

  4. AOV vs AOE

    • AOV：顶点是活动，做拓扑排序
    • AOE：边是活动，做关键路径

  5. 最短路径 vs 关键路径

    • 最短路径求“最小总代价”
    • 关键路径求“最大总工期（最长路径）”

B. 易错点（为什么错 + 怎么改）

  1. 把 Dijkstra 用在负权图

    • 错因：忽略“已确定最短路不会再变短”这个前提。
    • 正解：Dijkstra 仅适用于非负权边。

  2. Kruskal 漏做成环检查

    • 错因：只按边权排序一路加入。
    • 正解：每加一条边前用并查集判断是否同根。

  3. 拓扑排序输出一个序列就当 DAG

    • 错因：没核对输出顶点个数。
    • 正解：必须检查 count == V 才能判无环。

  4. 关键路径 ve/vl 用反了 max/min

    • 错因：把两套递推都写成 max 或都写成 min。
    • 正解：
      • ve 前推取 max
      • vl 回推取 min

  5. 邻接矩阵复杂度按 E 写

    • 错因：被“边数少”误导。
    • 正解：矩阵遍历通常是按顶点双循环，常见 O(V^2)。

C. 本章做题顺序建议

1
2
3
4
5
6
先判图类型（有向/无向、有权/无权、稠密/稀疏）
  |
  +-- 再选存储结构
  |
  +-- 再选算法：
        遍历 / MST / 最短路 / DAG问题

十三、书签级思维导图复现（第六章，Mermaid）

十四、PDF 例题与知识点补充（图）

例题 1：无向图握手定理

题目：无向图中顶点度数和与边数关系是什么？

答案：所有顶点度数和 = 2|E|。

详细解析：

  1. 每条无向边都连接两个端点。
  2. 统计度数时，每条边会被计算两次。

例题 2：有向图度关系

题目：有向图中入度和、出度和与边数关系是什么？

答案：Σ入度 = Σ出度 = |E|。

详细解析：

  1. 每条有向边都有且仅有一个起点和一个终点。
  2. 因此每条边分别贡献一次出度和一次入度。

例题 3：连通分量与生成森林

题目：非连通无向图做 DFS/BFS 会得到什么结构？

答案：遍历生成森林。

详细解析：

  1. 每个连通分量各自产生一棵生成树。
  2. 所有分量生成树合在一起就是生成森林。

例题 4：邻接矩阵复杂度

题目：邻接矩阵判相邻和空间复杂度分别是什么？

答案：判相邻 O(1)，空间 O(V^2)。

详细解析：

  1. 判相邻是直接访问矩阵元素。
  2. 需要开 V*V 个单元存边信息。

例题 5：邻接表复杂度

题目：邻接表空间复杂度和适用场景是什么？

答案：空间 O(V+E)，更适合稀疏图。

详细解析：

  1. 邻接表只存实际存在的边。
  2. 当 E << V^2 时节省显著。

例题 6：BFS 最短路适用条件

题目：BFS 可用于哪类最短路径问题？

答案：无权图（或等权图）单源最短路。

详细解析：

  1. BFS 按层扩展，层数即边数。
  2. 在等权边场景中，最先到达即最短。

例题 7：DFS 与 BFS 差异

题目：DFS 与 BFS 的核心访问差异是什么？

答案：BFS 按层，DFS 先深后回溯。

详细解析：

  1. BFS 依赖队列，体现 FIFO。
  2. DFS 依赖递归栈或显式栈，体现深度优先。

例题 8：Prim 与 Kruskal 选型

题目：Prim 与 Kruskal 各适合什么图？

答案：Prim 常用于稠密图，Kruskal 常用于稀疏图。

详细解析：

  1. Prim 以点集扩张，常配邻接矩阵。
  2. Kruskal 以边为中心，排序后并查集判环。

例题 9：Dijkstra 限制

题目：Dijkstra 的关键限制是什么？

答案：不能处理负权边。

详细解析：

  1. Dijkstra 依赖“已确定最短路不会再变短”的性质。
  2. 负权边会破坏该性质，导致错误。

例题 10：Floyd 递推式

题目：Floyd 更新公式是什么？

答案：d[i][j] = min(d[i][j], d[i][k] + d[k][j])。

详细解析：

  1. 含义是“走中转点 k 是否更短”。
  2. 三重循环逐步放宽可用中转点集合。

例题 11：拓扑排序判环

题目：如何通过拓扑排序判定有向图是否有环？

答案：若最终输出顶点数 < V，则有环。

详细解析：

  1. 有环时环上顶点入度无法降到 0。
  2. 因而这些点无法被输出，计数不足 V。

例题 12：拓扑序唯一性

题目：什么时候拓扑序唯一？

答案：每一步入度为 0 的可选顶点始终唯一。

详细解析：

  1. 若某一步出现多个入度 0 顶点，就可产生不同选择顺序。
  2. 只有全程唯一选择才唯一。

例题 13：关键路径核心量

题目：关键路径计算中 ve 和 vl 分别怎么求？

答案：

  1. ve 前推取 max
  2. vl 回推取 min

详细解析：

  1. ve 表示事件最早发生时间，必须满足所有前驱约束，取最大。
  2. vl 表示不延误工期的最晚时间，回推取最小。

例题 14：关键活动判定

题目：活动何时为关键活动？

答案：当 e(i) == l(i)。

详细解析：

  1. e(i) 是活动最早开始时间。
  2. l(i) 是不延误工期的最晚开始时间。
  3. 两者相等说明无机动时间，必在关键路径上。

例题 15：关键路径本质

题目：AOE 网关键路径本质是什么？

答案：决定总工期的最长路径。

详细解析：

  1. 工程总工期由最慢那条依赖链决定。
  2. 缩短非关键活动可能不改变总工期。

十五、第六章必背核对表

  1. 邻接矩阵/邻接表复杂度要会对比。
  2. BFS/DFS 的数据结构支撑不能写反。
  3. MST 两算法：Prim（点扩张）、Kruskal（边筛选）。
  4. Dijkstra 负权限制必须写明。
  5. Floyd 是多源最短路。
  6. 拓扑排序可用于判环。
  7. 关键路径计算顺序：拓扑求 ve -> 逆拓扑求 vl -> 判关键活动。

总结

第六章虽然内容多，但主线清晰：

  1. 存储结构：邻接矩阵（稠密）、邻接表（稀疏）
  2. 遍历：BFS（最短路径）、DFS（递归）
  3. 最小生成树：Prim（稠密）、Kruskal（稀疏）
  4. 最短路径：BFS（无权）、Dijkstra（非负权）、Floyd（多源）
  5. 拓扑排序：AOV 网、检测环
  6. 关键路径：AOE 网、ve/vl/e/l

必须滚瓜烂熟的内容：

  • 四种存储结构的复杂度对比
  • BFS 与 DFS 的区别和适用场景
  • Prim 与 Kruskal 的选择依据
  • Dijkstra 的负权限制
  • 拓扑排序的环检测原理
  • 关键路径的 ve/vl 计算方法

把这些吃透，图这一章就能达到考研要求。

作者：[Austoin]
参考教材：王道考研《数据结构》