第六章 图

6.1 图的基本概念

一、图的定义

图（Graph）：由顶点集 $V$ 和边集 $E$ 组成。记作 $G=(V, E)$，其中 $V(G)$ 是顶点的有穷非空集合，$E(G)$ 是边的有穷集合。

⚠️ 注意：图的顶点集 $V$ 必须非空（至少有一个顶点），但边集 $E$ 可以为空。

有向图 vs 无向图：

🗣️ 大白话：无向图就像微信好友——你加了我，我们互相是好友；有向图就像微博关注——我关注你，但你不一定关注我。

二、图的基本术语

重要公式：

• 无向图：$\sum\limits_{i=1}^{n} TD(v_i) = 2|E|$（每条边贡献两个端点各1度）
• 有向图：$\sum ID(v_i) = \sum OD(v_i) = |E|$
• 无向完全图边数：$C_n^2 = \frac{n(n-1)}{2}$
• 有向完全图弧数：$2C_n^2 = n(n-1)$
• 连通图至少需要 $n-1$ 条边（即生成树）
• 强连通图至少需要 $n$ 条弧（形成一个环）
• 若无向图边数 $|E| > n-1$，则图中一定有回路
• $n$ 个顶点的连通图最多 $\frac{(n-1)(n-2)}{2} + 1$ 条边（$n-1$ 个顶点完全图 + 1个顶点连1条边）

⚠️ 2010年真题考点：$n$ 个顶点的无向图要保证在任何情况下都连通（即无论边怎么分布都连通），最少需要 $C_{n-1}^2 + 1 = \frac{(n-1)(n-2)}{2} + 1$ 条边。

思路：先让 $n-1$ 个顶点构成完全图 $K_{n-1}$（需 $\frac{(n-1)(n-2)}{2}$ 条边），此时第 $n$ 个顶点还是孤立的。再加1条边将第 $n$ 个顶点连上，共 $\frac{(n-1)(n-2)}{2}+1$ 条边。例如7个顶点时：$C_6^2 + 1 = 15 + 1 = 16$。

特殊图：

• 简单图：不存在重复边，也不存在顶点到自身的边（考研中只讨论简单图）
• 多重图：两个顶点之间边数多于一条或有顶点到自身的边
• 完全图：任意两个顶点之间都存在边
• 稀疏图：边数很少（$|E| < |V| \log |V|$），用邻接表存储
• 稠密图：边数很多，用邻接矩阵存储
• 有向无环图（DAG）：没有环路的有向图
• 树：不存在回路且连通的无向图。$n$ 个顶点的树有且仅有 $n-1$ 条边
• 有向树：一个顶点入度为0，其余顶点入度为1的有向图

⚠️ 易错点：连通分量是无向图的极大连通子图（不能再加入任何顶点/边仍连通）；生成树是连通图的极小连通子图（再删任何一条边就不连通）。

6.2 图的存储结构

一、邻接矩阵

用二维数组 $A[n][n]$ 存储图，$A[i][j] = 1$ 表示存在边，$A[i][j] = 0$ 表示不存在。

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

class MGraph {
    static final int MaxVertexNum = 100;
    char[] vex = new char[MaxVertexNum];                       // 顶点表
    int[][] edge = new int[MaxVertexNum][MaxVertexNum];        // 邻接矩阵
    int vexnum, arcnum;                                        // 顶点数和边数
}

特点：

• 空间复杂度：$O(|V|^2)$，与边数无关
• 无向图的邻接矩阵是对称矩阵，可采用压缩存储（只存下三角）
• 无向图第 $i$ 行（或列）非零元素个数 $=$ 顶点 $v_i$ 的度
• 有向图第 $i$ 行非零元素个数 $=$ $OD(v_i)$；第 $i$ 列非零元素个数 $=$ $ID(v_i)$
• 适合稠密图
• 求度的时间复杂度：$O(|V|)$

💎 重要性质：设 $A$ 为图 $G$ 的邻接矩阵，则 $A^n[i][j]$ 等于从顶点 $i$ 到顶点 $j$ 的长度为 $n$ 的路径的数目。这是一个经典的考点。

⚠️ 2012年真题考点：若用邻接矩阵存储有向图，且主对角线以下的元素均为零（即上三角矩阵），则：

• 该图一定无环（不存在从编号大的顶点到编号小的顶点的边）
• 一定存在拓扑序列
• 但拓扑序列可能不唯一（多个顶点可能同时入度为0）

反之，若图存在拓扑序列，通过适当调整顶点编号，总可以使邻接矩阵满足上三角形式。

二、邻接表

为每个顶点建立一个单链表，链表中的结点表示与该顶点邻接的顶点。

// 边表结点
typedef struct ArcNode {
    int adjvex;            // 邻接点在数组中的位置
    struct ArcNode *next;
} ArcNode;

// 顶点表结点
typedef struct VNode {
    char data;             // 顶点信息
    ArcNode *first;        // 指向第一个邻接点
} VNode, AdjList[MaxVertexNum];

// 用邻接表存储的图
typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

// 边表结点
class ArcNode {
    int adjvex;         // 邻接点在数组中的位置
    ArcNode next;
}
// 顶点表结点
class VNode {
    char data;          // 顶点信息
    ArcNode first;      // 指向第一个邻接点
}
// 用邻接表存储的图
class ALGraph {
    VNode[] vertices = new VNode[100];
    int vexnum, arcnum;
}

特点：

• 空间复杂度：无向图 $O(|V|+2|E|)$（每条边存两次），有向图 $O(|V|+|E|)$
• 适合稀疏图
• 邻接表不唯一（各边结点的链接顺序可以不同）
• 对于有向图，求顶点入度需遍历整个邻接表（不方便），求出度只需遍历该顶点的边链表

三、十字链表与邻接多重表

• 十字链表：有向图的一种链式存储，方便求顶点的入度和出度。空间 $O(|V|+|E|)$
• 邻接多重表：无向图的一种链式存储，方便对边的删除等操作。空间 $O(|V|+|E|)$

十字链表结点结构（有向图专用）：

💡 沿 firstout→tlink 链可遍历该顶点所有出弧（求出度）；沿 firstin→hlink 链可遍历该顶点所有入弧（求入度）。

邻接多重表结点结构（无向图专用）：

💡 每条边只存一个边结点（vs 邻接表中无向边存两次），删边只需 $O(1)$。mark 字段用于标记该边是否已被搜索过。

四种存储结构对比：

图的基本操作时间复杂度对比：

6.3 图的遍历

一、广度优先搜索（BFS）

思想：类似于层序遍历。从某个顶点出发，先访问所有邻接点，再访问邻接点的邻接点。借助队列实现。

void BFS(Graph G, int v) {
    visit(v);
    visited[v] = TRUE;
    EnQueue(Q, v);
    while (!IsEmpty(Q)) {
        DeQueue(Q, v);
        for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
            if (!visited[w]) {
                visit(w);
                visited[w] = TRUE;
                EnQueue(Q, w);
            }
        }
    }
}

// BFS（邻接表实现）
void bfs(List<List<Integer>> graph, int v, boolean[] visited) {
    Queue<Integer> queue = new LinkedList<>();
    visited[v] = true;
    queue.offer(v);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        visit(u);
        for (int w : graph.get(u)) {
            if (!visited[w]) {
                visited[w] = true;
                queue.offer(w);
            }
        }
    }
}

时间复杂度：

• 邻接矩阵：$O(|V|^2)$
• 邻接表：$O(|V|+|E|)$

空间复杂度：$O(|V|)$（队列大小）

BFS的应用：

1. BFS 求无权图的单源最短路径（核心应用）

在 BFS 过程中维护两个辅助数组：

• d[]：记录各顶点到源点的最短路径长度（初始化为 $\infty$）
• path[]：记录最短路径上的前驱顶点（初始化为 -1）

void BFS_MIN_Distance(Graph G, int u) {
    // d[i]表示从u到i的最短路径长度
    for (int i = 0; i < G.vexnum; i++) {
        d[i] = INF;       // 初始化为无穷
        path[i] = -1;     // 前驱初始化为-1
    }
    d[u] = 0;
    visited[u] = TRUE;
    EnQueue(Q, u);
    while (!IsEmpty(Q)) {
        DeQueue(Q, v);
        for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
            if (!visited[w]) {
                d[w] = d[v] + 1;     // 路径长度加1
                path[w] = v;          // 记录前驱
                visited[w] = TRUE;
                EnQueue(Q, w);
            }
        }
    }
}

void bfsMinDist(List<List<Integer>> graph, int u) {
    int n = graph.size();
    int[] d = new int[n];
    int[] path = new int[n];
    boolean[] visited = new boolean[n];
    Arrays.fill(d, Integer.MAX_VALUE);
    Arrays.fill(path, -1);
    d[u] = 0;
    visited[u] = true;
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(u);
    while (!queue.isEmpty()) {
        int v = queue.poll();
        for (int w : graph.get(v)) {
            if (!visited[w]) {
                d[w] = d[v] + 1;
                path[w] = v;
                visited[w] = true;
                queue.offer(w);
            }
        }
    }
}

通过 path[] 数组可以逆序追溯得到完整最短路径。

2. BFS 生成树与生成森林

• 对连通图进行 BFS，可得到一棵BFS 生成树（即广度优先生成树）

• 对非连通图，每个连通分量调用一次 BFS，得到BFS 生成森林

• 邻接矩阵存储的图，BFS 生成树唯一；邻接表存储的图，BFS 生成树不唯一

3. 判断连通分量数

BFS 函数的调用次数 = 连通分量的个数（无向图）

二、深度优先搜索（DFS）

思想：类似于先序遍历。从某个顶点出发，沿着一条路径走到底，走不下去了就回溯。借助栈（递归即隐式栈）实现。

void DFS(Graph G, int v) {
    visit(v);
    visited[v] = TRUE;
    for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
        if (!visited[w])
            DFS(G, w);
    }
}

// DFS（邻接表实现）
void dfs(List<List<Integer>> graph, int v, boolean[] visited) {
    visit(v);
    visited[v] = true;
    for (int w : graph.get(v)) {
        if (!visited[w])
            dfs(graph, w, visited);
    }
}

时间复杂度：

• 邻接矩阵：$O(|V|^2)$
• 邻接表：$O(|V|+|E|)$

空间复杂度：$O(|V|)$（递归栈深度）

DFS的特性：

• 对连通图 DFS → DFS 生成树；对非连通图 → DFS 生成森林
• DFS 的调用次数 = 连通分量个数（无向图）
• DFS 可用于判断图中是否有回路
• DFS 算法的逆后序就是有向无环图的拓扑排序
• 对有向图 DFS，在顶点退栈前输出，得到的序列是逆拓扑排序序列

BFS vs DFS 对比：

🗣️ 大白话：BFS 就像水波扩散——从石头入水的地方一圈一圈往外扩；DFS 就像走迷宫——一条路走到黑，走不通就退回来换一条路。BFS生成树是从起点出发"最矮"的树（高度最小）。

🔗 【跨学科联动·计网/OS】 图的算法在408其他学科中有大量应用：

• 计网·路由算法：OSPF 协议使用 Dijkstra 算法求最短路径；RIP 协议使用距离向量算法（类似 Bellman-Ford）
• 计网·网络拓扑：计算机网络本身就是一张图，交换机/路由器是顶点，链路是边
• OS·死锁检测：用资源分配图（有向图）检测死锁——找图中是否有环（DFS 检测）
• OS·进程调度：优先级队列（堆）用于调度，而拓扑排序可用于任务依赖分析

6.4 图的应用

一、最小生成树（MST）

定义：连通图的生成树中，边的权值之和最小的生成树。

Prim算法：从某顶点开始，每次选择一条连接已选顶点集与未选顶点集的最小权值边。

• 时间复杂度：$O(|V|^2)$
• 适合稠密图

【Prim 算法手工模拟示例】

设图有 5 个顶点 $V_0 \sim V_4$，从 $V_0$ 出发。邻接矩阵（∞ 表示不相邻）：

MST 边集：{$(V_0,V_2,3)$, $(V_2,V_3,1)$, $(V_2,V_1,2)$, $(V_3,V_4,6)$}，总权值 = 3+1+2+6 = 12

💡 手算要点：每轮更新 lowCost 时，只需检查新加入顶点的邻边是否比当前 lowCost 更小。

Kruskal算法：将所有边按权值从小到大排序，依次选择不构成环的最小边。

• 时间复杂度：$O(|E| \log |E|)$
• 适合稀疏图

🗣️ 大白话：

• Prim：从一个城市出发，每次修一条到最近的还没连通的城市的路。（以"点"为核心）
• Kruskal：把所有可能修的路按长度排序，从最短的开始修，但不能修出环路。（以"边"为核心）

二、最短路径

1. BFS算法（无权图）

适用于求无权图的单源最短路径，时间 $O(|V|+|E|)$。就是对 BFS 的小修改：在 visit 一个顶点时，修改其最短路径长度 d[] 并在 path[] 记录前驱结点（详见 6.3 节 BFS 应用部分）。

2. Dijkstra算法（单源最短路径）

适用：边权值非负的带权图（有向/无向均可）

思想：贪心。维护三个辅助数组：

• final[]：标记各顶点是否已找到最短路径（布尔数组）
• dist[]：当前已知的从源点到各顶点的最短路径长度
• path[]：各顶点最短路径上的前驱

算法步骤（设从 $V_0$ 出发）：

1. 初始化：final[0]=true; dist[0]=0。对其余顶点 $k$：final[k]=false; dist[k]=arcs[0][k]; path[k]=(arcs[0][k]<∞)?0:-1
2. 循环 $n-1$ 轮：
   • 从所有 final[i]==false 的顶点中选 dist 值最小的顶点 $V_i$，令 final[i]=true
   • 检查 $V_i$ 的所有邻接点 $V_j$：若 final[j]==false 且 dist[i]+arcs[i][j]<dist[j]，则更新 dist[j]=dist[i]+arcs[i][j]; path[j]=i

// Dijkstra算法（邻接矩阵）
void Dijkstra(MGraph G, int v0) {
    int n = G.vexnum;
    for (int i = 0; i < n; i++) {
        final_arr[i] = FALSE;
        dist[i] = G.Edge[v0][i];
        path[i] = (dist[i] < INF) ? v0 : -1;
    }
    final_arr[v0] = TRUE; dist[v0] = 0; path[v0] = -1;
    for (int i = 1; i < n; i++) {       // n-1轮
        int min = INF, u = -1;
        for (int j = 0; j < n; j++)     // 找dist最小的未确定顶点
            if (!final_arr[j] && dist[j] < min) { min = dist[j]; u = j; }
        if (u == -1) return;
        final_arr[u] = TRUE;
        for (int w = 0; w < n; w++)     // 更新邻接点
            if (!final_arr[w] && dist[u] + G.Edge[u][w] < dist[w]) {
                dist[w] = dist[u] + G.Edge[u][w];
                path[w] = u;
            }
    }
}

void dijkstra(int[][] graph, int v0) {
    int n = graph.length;
    boolean[] fin = new boolean[n];
    int[] dist = new int[n];
    int[] path = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    Arrays.fill(path, -1);
    for (int i = 0; i < n; i++)
        if (graph[v0][i] != Integer.MAX_VALUE) { dist[i] = graph[v0][i]; path[i] = v0; }
    fin[v0] = true; dist[v0] = 0;
    for (int i = 1; i < n; i++) {
        int min = Integer.MAX_VALUE, u = -1;
        for (int j = 0; j < n; j++)
            if (!fin[j] && dist[j] < min) { min = dist[j]; u = j; }
        if (u == -1) return;
        fin[u] = true;
        for (int w = 0; w < n; w++)
            if (!fin[w] && graph[u][w] != Integer.MAX_VALUE && dist[u] + graph[u][w] < dist[w]) {
                dist[w] = dist[u] + graph[u][w];
                path[w] = u;
            }
    }
}

时间复杂度：$O(|V|^2)$（可用堆优化为 $O(|E| \log |V|)$）

【Dijkstra 算法手工模拟示例】

使用与 Prim 相同的图（$V_0 \sim V_4$），从 $V_0$ 出发求单源最短路径：

最终结果：$V_0 \to V_1$: 距离 4（直达），$V_0 \to V_2$: 距离 3（直达），$V_0 \to V_3$: 距离 4（$V_0→V_2→V_3$），$V_0 \to V_4$: 距离 7（直达）

⚠️ Dijkstra 手算步骤（考试模板）：

1. 画表，列出所有顶点的 dist 列，初始为邻接矩阵第一行
2. 每轮选 dist 最小的未确定顶点 $u$，标记 ✓
3. 用 $u$ 的出边更新所有未确定顶点：若 $\text{dist}[u] + w(u,v) < \text{dist}[v]$，则更新
4. 重复直到所有顶点确定
5. 追问最短路径时：通过 path[] 数组逆序回溯

⚠️ Dijkstra 不适用于有负权值边的图！ 因为贪心策略在负权边下可能导致已确定的"最短路径"被后续更短路径推翻。

⚠️ 最短路径算法选择陷阱（高频选择题）：

陷阱警告：Dijkstra 无法处理负权边的根本原因是它的贪心策略：一旦选定一个顶点的最短路径，就认为已经确定，不再回头更新。而负权边可能让"回头路"变得更短。

💡 Dijkstra 与 Prim 算法的类比：两者结构几乎完全相同！Prim 每次选 lowCost 最小、Dijkstra 每次选 dist 最小，都是 $O(|V|^2)$。区别在于 Prim 的 lowCost[j] 是 $j$ 到当前生成树集合的最近距离，而 Dijkstra 的 dist[j] 是从源点经 $S$ 到 $j$ 的最短路径长度。

3. Floyd算法（各顶点间最短路径）

适用：带权图（可以有负权边，但不能有负权回路）

思想：动态规划。维护两个矩阵：

• $A^{(k)}[i][j]$：从 $V_i$ 到 $V_j$，中间顶点编号不超过 $k$ 的最短路径长度
• $path^{(k)}[i][j]$：对应最短路径上的中转顶点

递推公式： $A^{(k)}[i][j] = \min\{A^{(k-1)}[i][j],\ A^{(k-1)}[i][k] + A^{(k-1)}[k][j]\}$

若经过 $V_k$ 中转更短，则 $path^{(k)}[i][j] = k$；否则保持不变。

初始化：$A^{(-1)}$ 为邻接矩阵，$path^{(-1)}$ 全部设为 $-1$。

// Floyd算法核心
// A[][] 初始化为邻接矩阵, path[][] 初始化为-1
for (int k = 0; k < n; k++)          // 中转点
    for (int i = 0; i < n; i++)      // 起点
        for (int j = 0; j < n; j++)  // 终点
            if (A[i][k] + A[k][j] < A[i][j]) {
                A[i][j] = A[i][k] + A[k][j];
                path[i][j] = k;       // 记录中转点
            }

// Floyd算法核心
for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; 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;
            }

通过 path 矩阵递归追溯完整路径：查找 $V_i$ 到 $V_j$ 的路径时，先查 path[i][j]=k，再递归查 $V_i$ 到 $V_k$、$V_k$ 到 $V_j$ 的中转点。

时间复杂度：$O(|V|^3)$，空间复杂度：$O(|V|^2)$

🗣️ 大白话：Floyd的思想很简单——"我从 $i$ 到 $j$ 直接走会不会比绕道 $k$ 更远？如果绕道更近就更新路线"。把所有可能的中转站都试一遍，需要 $n$ 轮递推。

4. Bellman-Ford算法（可处理负权边的单源最短路径）

适用：带权有向图（允许负权边，但不能有负权回路）

思想：对所有边进行 $|V|-1$ 轮"松弛"操作。每轮遍历所有边 $(u,v)$，如果 $\text{dist}[u] + w(u,v) < \text{dist}[v]$，则更新 $\text{dist}[v]$。

🗣️ 大白话：Dijkstra 像个"近视眼贪心"——只看眼前最近的点，遇到负权边就会犯错。而 Bellman-Ford 像个"全面撒网"——不管远近，每轮把所有边都试一遍、看看有没有更短的路，做够 $|V|-1$ 轮就能保证找到最短路径。

核心代码：

// Bellman-Ford 算法
bool BellmanFord(int n, int edges[][3], int edgeNum, int src, int dist[]) {
    for (int i = 0; i < n; i++) dist[i] = INF;
    dist[src] = 0;
    // 松弛 |V|-1 轮
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < edgeNum; j++) {
            int u = edges[j][0], v = edges[j][1], w = edges[j][2];
            if (dist[u] != INF && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }
    // 检测负权回路：第 |V| 轮若仍能松弛，说明存在负权回路
    for (int j = 0; j < edgeNum; j++) {
        int u = edges[j][0], v = edges[j][1], w = edges[j][2];
        if (dist[u] != INF && dist[u] + w < dist[v])
            return false;  // 存在负权回路
    }
    return true;
}

// Bellman-Ford 算法（Java版）
boolean bellmanFord(int n, int[][] edges, int src, int[] dist) {
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    for (int i = 1; i < n; i++) {
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }
    // 负权回路检测
    for (int[] e : edges) {
        if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]])
            return false;
    }
    return true;
}

⚠️ 为何恰好 $|V|-1$ 轮？ 若图中无负权回路，最短路径最多经过 $|V|-1$ 条边（经过所有顶点）。第 $k$ 轮松弛后，至少能正确求出经过不超过 $k$ 条边的最短路径。因此 $|V|-1$ 轮后所有最短路径均已确定。

🔗 【跨学科联动·计算机网络】 Bellman-Ford 算法是 RIP 协议（距离向量路由）的理论基础：

• RIP 中每个路由器维护到各目的网络的"距离"（跳数），定期与邻居交换路由表
• 本质就是分布式的 Bellman-Ford：每个路由器收到邻居的距离向量后执行松弛操作
• RIP 限制最大跳数为 15（16 = 不可达），正是为了限制 Bellman-Ford 的收敛轮数
• RIP 的"慢收敛/路由环路"问题（Count to Infinity）是 Bellman-Ford 分布式执行的固有缺陷
• 对应地，OSPF 协议（链路状态路由）基于 Dijkstra 算法

四种最短路径算法完整对比（⭐ 高频选择题考点）：

💡 也可用 Dijkstra 求所有顶点间最短路径：重复 $|V|$ 次，总时间 $O(|V|^3)$，但不如 Floyd 简洁。

三、拓扑排序

适用：有向无环图（DAG）

AOV网：用DAG表示工程，顶点表示活动，有向边 $\langle V_i, V_j \rangle$ 表示活动 $V_i$ 必须先于 $V_j$ 进行。

拓扑排序定义：将所有顶点排成线性序列，使得若存在边 $\langle u, v \rangle$，则 $u$ 在序列中排在 $v$ 前面。

算法步骤：

1. 选择一个入度为0的顶点输出
2. 删除该顶点及其所有出边（即将其邻接点入度减1）
3. 重复1-2直到所有顶点输出，或发现不存在入度为0的顶点（说明图中有回路）

时间复杂度：邻接表 $O(|V|+|E|)$，邻接矩阵 $O(|V|^2)$

逆拓扑排序：

1. 选择一个出度为0的顶点输出
2. 删除该顶点及所有以它为终点的有向边
3. 重复直到图空

DFS 实现逆拓扑排序：对有向无环图进行 DFS，在顶点退栈前输出（即后序输出），得到的序列即为逆拓扑排序序列。

⚠️ 重要应用：拓扑排序可用于判断有向图是否有环——若排序过程中输出的顶点数少于图中顶点总数，则存在环。

DAG 描述表达式（用有向无环图描述表达式，消除公共子表达式）：

1. 把各个操作数不重复地排成一排（作为叶结点）
2. 按运算符生效顺序标出各运算符
3. 按顺序加入运算符结点，注意"分层"
4. 从底向上逐层检查同层运算符是否可以合体（共享公共子表达式）

💡 DAG 的顶点中不可能出现重复的操作数——这是DAG表示与二叉树表示的关键区别。

四、关键路径

用于：AOE网（Activity On Edge NetWork，以边表示活动、以顶点表示事件的网络），求工程的最短完成时间。

AOE网性质：

• 只有某顶点代表的事件发生后，从该顶点出发的各活动才能开始
• 进入某顶点的所有活动都完成后，该顶点代表的事件才能发生
• 源点：入度为0（工程开始），汇点：出度为0（工程结束）

核心概念：

5步计算过程：

① $ve(源点) = 0$；按拓扑排序序列递推：$ve(k) = \max\{ve(j) + Weight(v_j, v_k)\}$（$v_j$ 为 $v_k$ 的任意前驱）

② $vl(汇点) = ve(汇点)$；按逆拓扑排序序列递推：$vl(k) = \min\{vl(j) - Weight(v_k, v_j)\}$（$v_j$ 为 $v_k$ 的任意后继）

③ 若边 $\langle v_k, v_j \rangle$ 表示活动 $a_i$，则 $e(i) = ve(k)$

④ $l(i) = vl(j) - Weight(v_k, v_j)$

⑤ $d(i) = l(i) - e(i)$；$d(i)=0$ 的活动是关键活动，由关键活动组成关键路径

关键路径：从源点到汇点的最长路径。关键路径长度 = 工程的最短完成时间。

重要性质：

• 关键路径上所有活动的时间余量为0
• 缩短关键活动的时间可以缩短工期
• 当缩短到一定程度时，关键活动可能变成非关键活动（原来的非关键路径可能成为新的关键路径）
• 可能存在多条关键路径，此时只有加快所有关键路径上共有的关键活动才能缩短工期

⚠️ 缩短关键活动不一定缩短工期——当存在多条关键路径且该活动不在所有关键路径上时。

📝 真题剖析

【2016年408真题】 使用 Dijkstra 算法求图中从顶点1到其他各顶点的最短路径，依次求得的各最短路径的目标顶点是？

解题方法：

1. 初始化：$dist[1]=0$，其余顶点 $dist=\infty$
2. 每次从未确定最短路径的顶点中选 $dist$ 最小的加入集合 $S$
3. 更新其邻接点的 $dist$ 值
4. 重复直到所有顶点加入 $S$

💡 Dijkstra 三步曲：选最近、加入、更新。每次确定一个顶点的最短路径。

【2022年408真题】 无向连通图边数 $|E|$ 与顶点数 $|V|$ 的关系？

💡 核心结论：无向连通图至少需要 $|V|-1$ 条边（树）。若 $|E| < |V|-1$，则图一定不连通。

【2021年408应用题】 判断无向图中是否存在欧拉回路/欧拉路径。

欧拉路径/回路条件（充要条件）：

1. 欧拉回路（一笔画回到原点）：图连通 + 所有顶点度数为偶数
2. 欧拉路径（一笔画不回原点）：图连通 + 恰好有0个或2个奇度数顶点

算法设计：

1. 用BFS/DFS判断图是否连通
2. 统计所有顶点的度数，计算奇度数顶点个数 $count$
3. 若 $count = 0$：存在欧拉回路；若 $count = 2$：存在欧拉路径；否则：不存在

// 判断无向图是否存在欧拉路径/回路（邻接矩阵）
boolean hasEulerPath(int[][] graph, int n) {
    // Step1: BFS 判连通
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new LinkedList<>();
    visited[0] = true; queue.offer(0);
    int cnt = 1;
    while (!queue.isEmpty()) {
        int v = queue.poll();
        for (int w = 0; w < n; w++)
            if (graph[v][w] != 0 && !visited[w]) {
                visited[w] = true; queue.offer(w); cnt++;
            }
    }
    if (cnt != n) return false; // 不连通
    // Step2: 统计奇度数顶点
    int oddCount = 0;
    for (int i = 0; i < n; i++) {
        int degree = 0;
        for (int j = 0; j < n; j++) if (graph[i][j] != 0) degree++;
        if (degree % 2 != 0) oddCount++;
    }
    return oddCount == 0 || oddCount == 2;
}

【2023年408应用题】 有向图以邻接矩阵存储，找所有"K-顶点"（出度 > 入度的顶点）。

方法：遍历邻接矩阵，对每个顶点分别统计出度（第 $i$ 行非零元素个数）和入度（第 $i$ 列非零元素个数），比较即可。

// 找所有K-顶点（出度 > 入度），邻接矩阵A[n][n]
List<Integer> findKVertices(int[][] A, int n) {
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        int outDeg = 0, inDeg = 0;
        for (int j = 0; j < n; j++) {
            if (A[i][j] != 0) outDeg++;  // 第i行：出度
            if (A[j][i] != 0) inDeg++;   // 第i列：入度
        }
        if (outDeg > inDeg) result.add(i);
    }
    return result;
}

💡 时间复杂度 $O(|V|^2)$——恰好等于邻接矩阵存储的标准复杂度。

【2024年408应用题】 判断有向图是否存在唯一的拓扑排序序列。

充要条件：拓扑排序过程中，每一步恰好只有一个入度为0的顶点。

// 判断DAG是否有唯一拓扑排序
boolean hasUniqueTopoSort(List<List<Integer>> graph, int n) {
    int[] inDeg = new int[n];
    for (int u = 0; u < n; u++)
        for (int v : graph.get(u)) inDeg[v]++;
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++)
        if (inDeg[i] == 0) q.offer(i);
    int count = 0;
    while (!q.isEmpty()) {
        if (q.size() > 1) return false; // 不唯一！
        int u = q.poll(); count++;
        for (int v : graph.get(u))
            if (--inDeg[v] == 0) q.offer(v);
    }
    return count == n; // count<n说明有环
}

⚠️ 若每步恰有1个入度为0的顶点 → 拓扑排序唯一；若某步有多个 → 拓扑排序不唯一。

【2025年408应用题】 AOE网求关键路径，压缩关键活动后分析工期变化。

解题模板（5步法）：

典型追问："将活动 $X$ 压缩2个时间单位，工期能缩短多少？"

• 若 $X$ 在所有关键路径上：工期缩短2（但不能缩短超过 $X$ 本身的持续时间）
• 若 $X$ 只在部分关键路径上：工期不缩短
• 缩短后可能产生新的关键路径，需要重新计算验证

⚠️ 2025年真题实例：AOE网最短完成时间=12，关键活动为 $a,e,m,n$。当压缩 $e$ 时需检查是否出现新关键路径。

【图的高频选择题考点汇总】：

📌 第六章总结