图的算法和应用

🔥 高优先级

图的应用就 四大天王 ：最小生成树、最短路径、拓扑排序 和 关键路径。需掌握这四种应用当中的 每个细节 。当然还有 DFS 和 BFS 这两种 遍历方式 也不能忽略。

DFS

深度优先搜索（Depth-First Search，简称 DFS ）是一种用于图的遍历和搜索的算法，它从图中的一个起始顶点开始，尽可能深地访问顶点，直到无法继续前进，然后回溯到之前的顶点，继续深入其他分支。DFS 通常用递归或栈来实现，确保在深度方向上优先遍历。

以下是 DFS 算法的一般步骤：

1. 从起始顶点开始，将其标记为已访问。
2. 遍历与当前顶点相邻的未访问顶点，选择其中一个未访问顶点作为下一个深度遍历的目标，然后递归地进行 DFS 。
3. 如果无法继续深度遍历（即当前顶点没有未访问的邻居），则回溯到上一个顶点，继续遍历其他未访问的邻居。
4. 重复步骤 2 和步骤 3，直到所有顶点都被访问。

图中 DFS 实现的框架与 树的遍历 类似，不同点在于需要使用 visit 数组记录已经访问过的节点，避免重复遍历：

function DFS(G, v, visited):
    visited[v] ← true
    for each neighbor u of v in G.adjacent[v]:
        if not visited[u]:
            DFS(G, u, visited)

DFS 逐步运行

图在 邻接矩阵 和 邻接表 中的 DFS 都遵循这个框架，两者的不同点在于获取 v 的邻居 u 的方式不同。

邻接矩阵

在 邻接矩阵 中，我们定义一个递归函数 dfs，函数从 start 顶点出发，输出当前结点，然后递归地去访问所有与其相邻的顶点。

注意递归前需要保证下一个顶点未被访问过，这样可以避免重复访问结点以及死循环。

// 全局变量，标记顶点是否被访问过
int visited[MAX_VERTICES];

// 递归函数，从 start 顶点出发
void dfs(int start) {
    visited[start] = 1;
    printf("%d ", start);

    // 依次访问 start 的邻接顶点
    for (int i = 0; i < MAX_VERTICES; i++) {
        // 递归的两个条件：
        // 1. 顶点 (start, i) 之间存在边
        // 2. 顶点 i 未被访问过
        if (adjMatrix[start][i] == 1 && !visited[i]) {
            // 递归调用
            dfs(i);
        }
    }
}

DFS 邻接矩阵演示

邻接表

邻接表 的递归思路与 邻接矩阵 一致，唯一的区别就是访问邻接顶点方式的不同。

在 邻接矩阵 中，通过遍历矩阵中的一行来访问相邻顶点。在 邻接表 中，通过遍历链表来访问相邻顶点。

// 全局变量，标记顶点是否被访问过
int visited[MAX_VERTICES];

// 递归函数，从 start 顶点出发
void dfs(struct Graph* graph, int start) {
    visited[start] = 1;
    printf("%d ", start);

    // 依次访问 start 的邻接顶点
    struct Node* temp = graph->adjacencyList[start];
    while (temp) {
        int adjVertex = temp->data;
        // 递归条件：顶点 i 未被访问过
        if (!visited[adjVertex]) {
            dfs(graph, adjVertex);
        }
        temp = temp->next;
    }
}

DFS 邻接表演示

BFS

广度优先搜索（Breadth-First Search，简称 BFS ）是一种用于图的遍历和搜索的算法，它从图中的一个起始顶点开始，逐层地访问与该顶点相邻的顶点，然后再访问这些相邻顶点的邻居，以此类推。BFS 通常用 队列 来实现，确保按照广度优先的顺序访问顶点。

以下是 BFS 算法的一般步骤：

1. 将起始顶点放入队列中，标记为已访问。
2. 从队列中弹出一个顶点并访问它。
3. 遍历该顶点的所有未被访问的邻居，将它们放入队列中，并标记为已访问。
4. 重复步骤 2 和步骤 3，直到队列为空。

等权图的 BFS 最短路与 MST 的目标差异

若每条边权都为 1，一条路径的路径权值等于经过的边数。BFS 从源点逐层访问，BFS 层数就是源点到该层顶点的最少边数，因此第一次发现顶点时便得到等权图的单源最短距离。Prim、Kruskal 优化的是整棵生成树的总权值，不保证源点到各顶点的距离最短；“最小生成树”不能替代“最短路径树”。

BFS 的伪代码实现如下所示，基于 邻接矩阵 或 邻接表 的 BFS 都遵循这个框架：

function BFS(G, start):
visited[start] ← true
enqueue(Q, start)




while Q is not empty:
    v ← dequeue(Q)
    process(v)
    for each neighbor u of v in G.adjacent[v]:
        if not visited[u]:
            visited[u] ← true
            enqueue(Q, u)

邻接矩阵

实现 BFS 时，首先添加起始顶点进入队列中，然后不断从队列中取出顶点，并添加该顶点的未访问相邻顶点进入队列。重复直到队列为空。

在 DFS 中，visited 数组是各个递归函数都需要访问的数据结构，为了方便起见，可以定义为全局变量。
在 BFS 中，由于算法实现是基于迭代而非递归，所以 visited 和队列可以定义为局部变量。

// 从 start 开始遍历图
void bfs(int start, int vertices) {
    // 队列 q
    queue q;
    // 标记顶点是否被访问过
    int visited[MAX_VERTICES];
    // 添加初始顶点
    q.enqueue(start);
    visited[start] = 1;

    // 一直遍历到队列为空
    while (q.size() > 0) {
        // 从队列头部取出结点作为当前结点
        int currentVertex = q.dequeue();
        // 输出当前结点
        printf("%d ", currentVertex);
        // 将当前结点的所有 相邻的未访问顶点 添加到队列中
        for (int i = 0; i < vertices; i++) {
            if (adjMatrix[currentVertex][i] == 1 && !visited[i]) {
                q.enqueue(i);
                visited[i] = 1;
            }
        }
    }
}

BFS 队列变化演示

BFS 邻接矩阵演示

邻接表

实现思路与 邻接矩阵 方式一致，不同点在于访问相邻顶点的方式不同。

void bfs(struct Graph* graph, int start) {
    // 队列 q
    queue q;
    // 标记顶点是否被访问过
    int visited[MAX_VERTICES];
    // 添加初始顶点
    q.enqueue(start);
    visited[start] = 1;

    // 一直遍历到队列为空
    while (front != rear) {
        // 从队列头部取出结点作为当前结点
        int currentVertex = q.dequeue();
        // 输出当前结点
        printf("%d ", currentVertex);
        // 将当前结点的所有 相邻的未访问顶点 添加到队列中
        struct Node* temp = graph->adjacencyList[currentVertex];
        while (temp) {
            int adjVertex = temp->data;
            if (!visited[adjVertex]) {
                q.enqueue(adjVertex);
                visited[adjVertex] = 1;
            }
            temp = temp->next;
        }
    }
}

BFS 邻接表演示

最小生成树

最小生成树（Minimum Spanning Tree ，MST ）是在一个连接所有顶点的无向图中，通过选择一部分边而形成的树，使得树的总权重（或成本）最小。

准确的 MST 定义如下：在无向图 G=(V,E) 中， (u,v) 代表连接顶点 u 和顶点 v 的边，而 w(u,v) 代表此边的权重，若存在 T 为 E 的子集且 (V,T) 为树，使得 w(T)=∑(u,v)∈T​w(u,v) 最小，则此 T 为 G 的 最小生成树 。

MST 满足以下特点：

• 包含图中的所有顶点。
• 通过选择一些边而形成一个树结构，没有环路。
• 边的总权重最小。

最小生成树的三个判断边界

对连通无向图，任一最小生成树都恰有 |V|-1 条边，但“边数为 |V|-1”本身不能推出它是树，更不能推出它是最小生成树：还必须同时连通且无环。MST 可能不唯一，但所有 MST 的总权值相同。边权互不相同可保证 MST 唯一；反过来不成立，例如三角形边权为 1、1、2 时，唯一 MST 仍由两条权值为 1 的边组成。因此，看到“存在相同边权就一定有多棵 MST”应立即用这个反例否定。

prim 算法

Prim 算法通过 逐步扩展顶点集合 来构建最小生成树：从一个初始顶点出发，每次都选择一条 连接生成树与外部顶点的最小权重边 ，并将该顶点并入生成树，直到所有顶点都被包含。

prim 算法步骤 如下：

1. 选定一个起始顶点作为生成树的根。
2. 初始化生成树，只含有该顶点。
3. 在所有 连接生成树与未加入顶点的边 中，选取权重最小的一条，并将对应顶点加入生成树。
4. 重复步骤 3，直到所有顶点均被纳入生成树。
5. 得到的生成树即为原图的 最小生成树 。

补充

prim 是一种 贪心算法 ，这里关键在于理解什么叫做 所有连接生成树与未加入顶点的边 ：

当我们已经有一个部分生成树（初始时只有一个顶点），它把图中的顶点分成两类：

1. 已加入生成树的顶点集合 T
2. 尚未加入生成树的顶点集合 V−T

此时，

• 所有连接生成树与未加入顶点的边 ，就是一端在 \(T\) 内、另一端在 \(V-T\) 内的边。
• 这些边正好构成了一个“割（cut）”，也叫“横切边”。

Prim 算法的贪心思想就在这里：每次都从这组横切边里挑出一条 权重最小的边 ，把它对应的未加入顶点纳入生成树。

这样保证了：

• 每次扩展都是局部最优（加入的边在候选集合里是最小的）。
• 最终能够得到全局最优的最小生成树（证明基于“割性质”，不是重点这里不说明）。

参考 prim 算法的流程图如下：

举个实际例子，对于以下的无向图，假设我们从顶点 a 出发使用 prim 算法寻找最小生成树，会逐步选择出 ab、bc、ci、cf、fg、gh、cd 以得到最小生成树：

kruskal 算法

Kruskal 算法是一种用于求解 最小生成树 （MST ）的贪心算法。Kruskal 算法的基本思想是从边的权重最小的边开始，逐步构建生成树，确保不会形成环路。

以下是 Kruskal 算法的一般流程：

1. 初始化一个空的生成树，开始时生成树中没有边。
2. 将图中的所有边按照权重 从小到大进行排序 。
3. 依次 从排序后的边列表中选取边 ，加入生成树，但要确保 添加该边不会形成环路 。
4. 重复步骤 3，直到生成树包含了所有的顶点，即生成树中的边数等于顶点数减 1。
5. 返回生成树作为 最小生成树 。

继续使用上文中 prim 中的无向图作为例子，使用 kruskal 算法，会依次选择 hg、ic、gf、ab、cf、cd、ah 以得到最小生成树：

最短路径

dijkstra 算法

Dijkstra 算法是一种用于计算 单源最短路径 的经典算法，适用于 带非负权重 的有向或无向图。

Dijkstra 算法是一种 贪心算法 。它的 核心思想 是：从起点出发，不断“扩展”到距离起点最近的节点，并利用这些节点去尝试更新其他节点的最短路径，直到所有节点的最短路径都被确定。

换句话说，算法始终保持一个 “已确定最短路径的集合”，并且在每一步中把离起点最近的“候选节点”加入其中：

prim 算法和 dijkstra 算法的核心步骤十分类似：

• 两个算法都用一个集合（已确定的顶点集合）逐步扩展。
• 每次都要在“已选顶点集合”与“未选顶点集合”之间，挑选一个“最优”的候选顶点加入集合。

但是 prim 比较的是比较的是 边的权重 （只看与生成树相连的边），dijkstra 比较的是 从源点出发的路径长度 （边的累计权重）。

🛠️ dijkstra 算法需要定义以下 数据结构 ：

• dist[]：数组，dist[v] 表示起点到节点 v 的 当前已知最短路径长度 。

• 初始化时：dist[source] = 0，其余节点均为 ∞。

  • visited[]：布尔数组，表示某个节点的最短路径是否已经被最终确定。

• 初始时：所有节点均为 false。

✨ dijkstra 算法流程 如下：

1. 初始化

• 设起点为 source。
• dist[source] ← 0
• 对于其他顶点 v，dist[v] ← ∞
• visited[v] ← false

2. 主循环（重复 |V| 次，即所有顶点都被处理完）

• 从所有 未访问 的顶点中，找到一个 dist[] 值最小的顶点 u。 （这意味着：当前已知路径中，u 是离起点最近的尚未确定的节点。）
• 将该顶点标记为已访问：visited[u] ← true。
• 对于 u 的每个邻居 v：

  • 如果 v 未被访问，并且通过 u 到达 v 的路径更短（即 dist[u] + w(u,v) < dist[v]）， 则更新：

    dist[v] ← dist[u] + w(u,v)
    

（这一步就是“松弛操作”，表示尝试通过 u 改进到 v 的最短路径。） 3. 结束

• 当所有顶点都被访问后，dist[v] 就保存了起点到各个顶点的最短路径长度。

Dijkstra 算法流程可以通过以下流程图理解：

Dijkstra 的考察侧重于手工模拟其过程，代码实现一般不会考察，这里给出算法的简单 伪代码实现 ，帮助各位理清其中的处理细节。

Dijkstra 手工表与顶点固定顺序

每一轮先从未确定顶点中选 dist 最小者加入集合 S，再用它的出边松弛其他顶点；一旦加入 S，该顶点的最短距离就不会再改变。顶点固定顺序比较的是每轮松弛后的累计路径长度，不是当前边权。例如候选距离为 f=4、d=5、e=7 时先固定 f；若 f 没有改善其余距离，再固定 d，并可能经 d 把 e 从 7 改成 6，最终顺序仍是 f、d、e。手工表至少记录 S、各顶点 dist 和前驱，避免把“暂定值更新”误写成“顶点已固定”。

在非负权图中，顶点按当前 dist 从小到大依次固定。例如最终暂定距离依次达到 d(5)=4、d(2)=5、d(3)=7、d(6)=9、d(4)=11 时，固定顺序就是 5,2,3,6,4。每一轮都应先完成当前顶点的松弛，再比较下一轮候选值。

完整一轮后的 dist 状态

“固定一个顶点”和“用该顶点松弛邻点”共同构成完整一轮。按顶点 2、3、4、5 记录，初始为 (26,3,∞,6)；先固定顶点 3，经 3→2(22) 得 (25,3,∞,6)；再固定顶点 5，经 5→4(8) 与 5→2(15) 得 (21,3,14,6)。因此不能在选出第二个顶点后、尚未松弛它的出边时提前读取数组。

练习：判断两轮松弛后的 dist 状态

function Dijkstra_Simple(Graph, source):
    对于图中每个顶点 v:
        dist[v] ← ∞          // 起点到 v 的距离初始化为无穷大
        visited[v] ← false   // 所有顶点初始都未被访问
    dist[source] ← 0         // 起点到自身距离为 0

    重复 |图中顶点数| 次:
        u ← 所有未访问的顶点中 dist[u] 最小的顶点
        visited[u] ← true    // 标记 u 已被访问

        对于 u 的每个相邻顶点 v:
            边权重 weight ← 图中边(u, v) 的权重
            如果 v 未访问 且 dist[v] > dist[u] + weight:
                dist[v] ← dist[u] + weight  // 通过 u 到 v 更短，更新最短路径

    return dist[] // 表示起点到所有顶点的最短路径

Dijkstra 松弛过程演示

假设顶点的个数为 V ，边的个数为 E ，那么 最佳实现（使用了优先队列）的 dijkstra 算法时间复杂度为 O(V+E) 。

floyd 算法

Floyd Warshall 是一种基于 动态规划 的方法，用于求解任意两个顶点之间的最短路径，它适用于带权有向图。

该算法的核心思想是尝试使用每一个顶点作为中转点，逐步更新所有顶点对之间的最短路径。对任意两点 i→j ，判断是否可以通过一个中间点 k 得到更短路径：

dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])

这个过程会遍历所有可能的中转点 k ，不断优化路径。

✨ 算法具体流程如下：

1. 初始化距离矩阵 dist：

• dist[i][j] = 0（若 i=j）
• dist[i][j] = 边权（若 i→j 有边）
• dist[i][j] = ∞（其余情况）

2. 三重循环更新最短路径

   for k in 所有顶点:
       for i in 所有顶点:
           for j in 所有顶点:
               if dist[i][k] + dist[k][j] < dist[i][j]:
                 dist[i][j] ← dist[i][k] + dist[k][j]

Floyd 距离矩阵演示

3. 输出 dist 矩阵 ：表示所有顶点对之间的最短路径长度。

若顶点数为 n ，则 Floyd Warshall 算法的时间复杂度为 O(n3) ，该算法适合在算法题中兜底使用，因为实现比较简单，建议大家熟练掌握代码实现。

拓扑排序

拓扑排序 这样一种对图中顶点的排序方式：

将图中的所有顶点排序，使得对于每一条有向边 u → v，顶点 u 都排在 v 之前。

拓扑排序 主要应用于 DAG （有向无环图）或 AOV 网，这种图没有环路，因此可以对其进行拓扑排序。

首先需要区分 AOV 和 AOE 这两个概念，注意 拓扑排序 适用于 AOV ，关键路径 适用于 AOE 。

AOV 网

AOV （Activity on Vertex Network）网是一种以顶点表示活动或任务的网络模型。每个 顶点 代表一个 任务或活动 ，而 边 表示任务之间的 依赖关系 。在AOV网中，任务或活动通常表示为顶点，而依赖关系（任务的先后顺序）表示为有向边。

算法步骤

计算 拓扑排序 的算法有两种，一种是 Kahn 算法（基于入度），另一种是 DFS+栈 的实现。

Kahn算法

Kahn 算法的核心思想是 依次选取入度为 0 的顶点进行输出 ，其具体步骤如下：

1. 选择一个没有前驱顶点（入度为 0）的顶点作为起始顶点，将其加入拓扑排序的结果序列中。
2. 从图中移除该顶点以及与之相关的边（即将与之相邻的顶点的入度减 1）。
3. 重复步骤 1 和步骤 2，直到所有的顶点都被加入到拓扑排序的结果序列中，或者发现图中存在环路。
4. 如果所有的顶点都被成功加入结果序列，那么这个序列就是拓扑排序的结果。

下图展示了一个采用 Kahn 算法输出 AOE 网中的 拓扑序列 的实例：

此外，可以通过 DFS+栈 得到 拓扑序列 ，其步骤如下：

1. 对图进行深度优先遍历。
2. 每个节点 DFS 结束后将其压入栈中。
3. 最后依次出栈，得到完成时间从晚到早的 拓扑排序 结果。

DFS 过程中，每个节点在其所有后继节点访问完成后才被压栈，因此后完成的前驱位于栈顶；直接按出栈顺序输出，正好满足 拓扑排序 所需的“前驱先于后继”约束。若不用栈而记录完成序列，则应将“完成时的记录顺序”逆序。

拓扑序列计数与验证（6.3）

枚举拓扑序列时，每一步选剩余入度为 0 的顶点，输出后删除它的出边并更新入度；某一步有多个候选时分别继续计数。候选序列只有在每一步都能选到当前入度为 0 的顶点时才有效。

拓扑序列计数的分支树

计数不能只把某一步的零入度顶点个数相乘，因为选择一个顶点后，新释放的零入度顶点可能不同。应把每个状态写成“已输出序列 + 当前零入度集合”：每选一个候选就复制状态、删除其出边并递归，直到输出全部顶点时计 1；若还有顶点却没有零入度候选，该分支含环，计 0。多个候选只有在它们后续始终互不影响时才可用阶乘快捷计数，通常应画分支树逐支枚举。

DFS 序列合法性验证（6.3）

验证 DFS 首次访问序列时维护访问栈：访问当前顶点后必须栈式深入到其未访问邻接点；只有当前顶点没有可走分支时才能回溯，回溯后再换到上层顶点的下一条分支。若序列在栈顶仍有未访问邻接点时跳到非邻接顶点，则不是合法 DFS 序列。

拓扑序验证边约束

验证一个候选序列时，为每条边 u→v 记录顶点位置，必须满足 pos(u) < pos(v)；逐边检查即可确认它是否为拓扑序。

无向图邻接矩阵对称

无向边同时表示两个方向，因此无向图邻接矩阵满足 aᵢⱼ = aⱼᵢ，是对称矩阵（无自环时主对角线为 0）。有向图、AOV 网或 AOE 网不保证这一性质。

按拓扑序编号得到严格上/下三角矩阵

按拓扑序给顶点编号时，每条边都从较小编号指向较大编号，邻接矩阵非零元素只会出现在主对角线上方，得到严格上三角矩阵；若采用反向编号，非零元素位于主对角线下方，得到严格下三角矩阵。编号方向决定上三角或下三角，且无自环时主对角线为 0。

严格上三角邻接矩阵只能保证编号顺序 1,2,...,n 是一个拓扑序，不能保证它唯一。唯一性仍要用 Kahn 过程检查每一步是否恰有一个零入度顶点。反例：3 个顶点只有 1→3、2→3，邻接矩阵严格上三角，但初始顶点 1、2 都为零入度，所以 1,2,3 与 2,1,3 都合法。若要由矩阵直接保证该编号序列唯一，至少还需形成相邻编号之间的强制先后链（如存在 1→2→...→n）。

用零入度候选数判断拓扑序唯一性

Kahn 过程中，若每一步都恰好只有一个零入度顶点，拓扑序唯一；只要某一步同时出现两个或更多候选，就可以交换或分支，得到不止一种拓扑序。对题图逐轮删除后，候选依次唯一为 A、B、C、D、E、F，所以唯一序列是 A→B→C→D→E→F。注意“当前只有一个源点”只证明第一步唯一，不能替代全过程检查。

DFS完成时间序列为逆拓扑序

在 DAG 上进行 DFS，只有一个顶点的所有后继完成后它才完成。因此对任意边 u→v，finish(v) < finish(u)；按完成时间从早到晚输出得到逆拓扑序，按完成时间从晚到早输出才是拓扑序。

拓扑排序 的时间复杂度通常为 O(V+E) ，其中 V 是顶点的数量， E 是边的数量。这个算法非常适合于解决任务调度和依赖关系问题，因为它可以确定任务的执行顺序或依赖关系的合理性。

邻接表拓扑排序为什么是 O(n+e)

Kahn 算法初始化入度并让每个顶点至多入队、出队一次，顶点工作为 O(n)；删除出边时，每条弧只沿邻接表扫描一次，边工作为 O(e)，合计 O(n+e)。若图改用邻接矩阵，找每个已输出顶点的出边要扫描一整行，通常为 O(n²)；复杂度取决于存储结构，不能只背“拓扑排序是线性的”。

用零入度候选集验证拓扑序

验证多个候选序列时先看第一处分歧：维护当前零入度集合，候选序列的下一项不在集合中即可立即排除。例如初始零入度集合只有 {1,5}，那么前两位只能是 1,5 或 5,1；以 5,2 开头却仍把 1 留到后面的序列必不合法。这个方法比每个选项从头完整模拟更快，但最终仍等价于逐边检查所有 u→v 是否满足 pos(u)<pos(v)。

关于拓扑排序，还需要关注以下几点：

• 拓扑排序的结果 可能不唯一 ，因为在构建过程中往往会出现多个入度为 0 的顶点，不同的选择顺序会产生不同的合法排序结果。
• 如果图中 存在环路 ，那么 无法进行拓扑排序 ，因为无法找到入度为 0 的顶点作为起始顶点。

四个图论结论的反例与反证

一般有向图不保证存在零入度顶点，例如有向环中每个顶点入度都为 1；DAG 只保证拓扑序存在，不保证唯一，某轮出现多个零入度候选即可产生不同序列。若有限无向图所有顶点度至少为 2，它不可能是森林，因为每棵非平凡树都有叶子、孤立树有度为 0 的顶点，所以图中必有回路。BFS 只直接解决无权或等权图的单源最短路，不能求一般带权图的全点对最短路径；非负权单源用 Dijkstra，全点对可用 Floyd。

关键路径

关键路径 是指 AOE 网（Activity On Edge Network）中，从源点到汇点所经过的 最长路径 。这条路径决定了整个项目完成所需的最短时间，因此被称为 关键 路径。

关键路径定义与工期变化

关键路径从 AOE 网的源点通向汇点，最长的是路径权值之和，不是边数；其长度就是工程工期。增加任一关键活动的持续时间，会让至少一条原关键路径超过原工期，所以工期必然增加。反过来，缩短任一关键活动不保证工期缩短：若有其他关键路径未受影响，最长路径长度仍等于原工期；即使原来只有一条，缩短后也应重新比较所有路径。

从局部活动反推最早/最迟开始时间

AOE 中活动 d=<u,v> 的最早开始时间是弧尾事件的最早发生时间 e(d)=ve(u)；若 u 有多条入路，取所有到达 u 的路径长度最大值。最迟开始时间是弧头事件最迟发生时间减活动时长：l(d)=vl(v)-w(d)。例如 ve(u)=max{3,4+8}=12，工期 27，v 到汇点还需 6，所以 vl(v)=27-6=21；若 d 持续 7，则 l(d)=21-7=14。答案是 12/14，而不是把活动持续时间重复减两次。

AOE 网

AOE （Activity on Edge Network）网是一种以边表示活动或任务的网络模型。每条边代表一个任务或活动，而顶点通常表示事件，表示任务的开始或完成时间。

为了理解 关键路径 ，首先需要明确 AOE 网中的以下概念：

• 源点 ：在 AOE 网中仅有一个入度为 0 的顶点，称为开始顶点，表示整个工程的开始。
• 汇点 ：在 AOE 网中仅有一个出度为 0 的顶点，称为结束结点，表示整个工程的结束。
• 关键路径的长度 ：完成整个工程的最短时间，也是 AOE 网中从源点到汇点的 最长路径 。
• 关键活动 ：关键路径 上的活动。
• 活动的时间余量 ：某个活动可以被延迟的最大时间，而不会影响整个项目的最短完成时间（总工期）。
• ve(k)：事件 vk​ 的最早可以发生时间。
• vl(k)：事件 vk​ 的最晚可以发生时间。

有几个概念比较重要，还需要进行进一步的阐述：

事件和活动

在 AOE 网中，边代表活动（Activity） ，顶点代表事件（Event） 。

• 活动（边） ：表示一个具体的工作、任务或操作，具有确定的持续时间。一个活动必须在其起点事件“发生”之后才能开始。
• 事件（顶点） ：表示一个时间点，通常是某些活动的“开始”或“结束”条件已经满足，代表某种逻辑上的时刻状态。

通俗来讲：活动是“做某事”，事件是“可以开始做某事的时间点”

事件的发生时间

在 AOE 网中，一个事件的“发生”是指其所有前驱活动都已完成 ，这标志着“条件成熟”，从该事件出发的活动才可能被启动。

两个关键时间 ：

事件发生的判断逻辑 ：

一个事件是否可以发生，不看它的出边活动，而是看它的所有前驱活动（入边）是否完成 ：

• 若某事件 i 的所有进入活动（任务）都已完成 → 则事件 i 发生；
• 一旦事件 i 发生，其所有出边活动 可以开始 ，但 不必须同时开始 ；
• 出边活动的实际开始时间取决于它们自身的调度灵活性（浮动时间）。

活动时间余量

“活动的时间余量” 在 AOE 网中指的是：

一个活动可以被延迟的最大时间 ，而不会影响整个项目的最短完成时间（总工期）。

首先，为什么要有时间余量呢？因为在 AOE 网络中，不是所有活动都在 关键路径 上。

• 关键路径上的活动 ：必须准时进行，没有时间余量 （余量 = 0）
• 非关键路径上的活动 ：允许适当延迟，但必须不阻碍项目的最晚结束时间

时间余量可以通过以下数学公式计算：

对于一个活动 A(i→j) ，持续时间为 dij​ ，其时间余量：

时间余量=vl(j)−ve(i)−dij​

其中：

• ve(i) ：起点事件 i 的最早发生时间
• vl(j) ：终点事件 j 的最晚发生时间
• dij​ ：活动持续时间

从事件时间表计算活动余量

先用正向最大值和反向最小值得到事件时间 ve=(0,2,5,8,9,12)、vl=(0,4,5,8,11,12)，再对每条候选活动 i→j 代入 slack=vl(j)-ve(i)-w(i,j)。本例有 c: 5-2-1=2、g: 12-5-1=6、h: 11-8-1=2、j: 12-9-1=2，故 g 的时间余量最大。ve、vl 描述的是事件最早/最迟发生时间；活动的最早/最迟开始时间分别是 ve(i) 与 vl(j)-w(i,j)，不能混称。

关键路径 上的所有活动都是 关键活动 ，它是决定整个工程的关键因素，因此可通过加快关键活动来缩短整个工程的工期。

关键路径和关键活动具有以下典型特征 ：

1. 关键活动的时间余量为 0 ：即对某活动 A(i→j) 有

vl(j)−ve(i)−dij​=0

说明该活动不能被延迟任何时间，否则将影响总工期。

2. 关键活动连接的事件满足 ：

ve(i)=vl(i)且ve(j)=vl(j)

即活动的起点和终点事件的最早发生时间等于最晚发生时间。它们必须在确定的时间点发生，不能提前也不能推迟。

3. 关键路径是工程中的最长路径 ：它决定了整个项目从开始到结束所需的最短时间，也即项目总工期。

4. 关键路径可能有多条 ：若多个路径的总时长都等于项目的最短完成时间，这些路径上的活动都必须受到严格监控。

算法步骤

求解 关键路径 的 核心思路 在于找到所有 最早发生时间 和 最晚发生时间 相同的结点，连接这些结点即可得到关键路径。

所以在求关键路径的算法中，我们需要依次计算每个顶点的最早发生时间（ve）和最晚发生时间（vl），然后判断哪些顶点的 ve 和 vl 相等。

为了得到关键路径，需要分三步计算：

1. 计算最早发生时间ve

• 从 源点 出发，设 ve(start) = 0；
• 按照 拓扑排序 的顺序依次计算其他顶点的最早发生时间：

ve(k)=vj​∈Pred(vk​)max​{ve(j)+weight(vj​,vk​)}

其中 Pred(vk​) 表示 \(v_k\) 的所有前驱结点。 含义 ：顶点 \(v_k\) 的最早开始时间，取决于它所有前驱活动完成的最晚时间。

2. 计算最迟发生时间vl

• 从 汇点 出发，设 vl(end) = ve(end)；
• 按照 逆拓扑排序 的顺序依次计算其余顶点的最迟发生时间：

vl(k)=vj​∈Succ(vk​)min​{vl(j)−weight(vk​,vj​)}

其中 Succ(vk​) 表示 \(v_k\) 的所有后继结点。 含义 ：顶点 \(v_k\) 的最迟开始时间，取决于它所有后继活动最早开始的最早约束。

3. 确定关键路径

• 若某个顶点满足 ve(i) = vl(i)，则说明该顶点没有时间浮动，必须严格按时发生；
• 将这些顶点按拓扑顺序连接起来，得到关键路径。

AOE 事件时间递推

按拓扑序对每条边 i→j 做正向更新：ve(j)=max(ve(j), ve(i)+d(i,j))；按逆拓扑序反向更新：vl(i)=min(vl(i), vl(j)-d(i,j))，并以 vl(end)=ve(end) 初始化。活动 i→j 的总松弛量为 vl(j)-ve(i)-d(i,j)，为 0 才是关键活动。

缩短工期的关键路径条件

工程工期是所有源点到汇点路径长度的最大值。若存在多条关键路径，缩短只覆盖其中一条的活动不会降低这个最大值；要缩短工程，必须缩短所有关键路径上共有的活动（并在变更后重新计算 ve、vl 与关键路径）。

邻接矩阵列全 ∞ 与 AOE 起点

在 a[u][v] 表示弧 u→v 的约定下，第 i 列全为 ∞ 只说明顶点 i 没有入边、入度为 0。只有结合 AOE 网存在关键路径且源点唯一的前提，才能判定该顶点是起点；终点应检查出度（对应行）为 0。

用图表达树

当表达式中存在共享的子表达式时，二叉树可能不是存储这些表达式的最有效方式，因为它会重复存储共享的子表达式。在这种情况下，可以使用 有向无环图 （DAG ）来表示表达式，这样可以避免重复，并且更有效地表示表达式。

比如对于表达式 (x + y) * ((x + y) / x)，用二叉树和 DAG 的表示如下图：

表达式 DAG 的最少顶点计数

先列不同的叶子与运算：变量 x、y 各存一次；公共子表达式 x+y 只建一个加法顶点；其上再建除法和最外层乘法顶点，共 2+1+1+1=5。计数时相同变量也应共享，不能只合并重复运算；边可以多次指向同一顶点，不增加顶点数。

Kruskal 的“按权排序”不等于“每条都选”

按权值递增逐边检查，并查集判断两端是否已连通：已连通则加入会成环，必须跳过。若先选 (b,f)=5、(b,d)=6，下一条 (d,f)=7 的两端已经通过 d-b-f 连通，所以跳过；再选 (a,e)=9、(c,e)=10、(b,e)=11。6 个顶点选满 5 条边即结束，顺序为 (b,f),(b,d),(a,e),(c,e),(b,e)。

DFS 退出时输出得到逆拓扑序

对任意边 u→v，递归 DFS 必须先完成 v 及其后继，才能返回并完成 u。若在退出递归前输出，则 v 先于 u，所有边都表现为“终点在起点之前”，因此得到逆拓扑序；将这个完成序列逆序才是拓扑序。若要输出全部顶点，外层循环还必须覆盖非连通 DAG 的每个顶点。

拓扑排序判定方法

拓扑序列中的可达关系

拓扑序列是有向无环图（DAG）中满足“每条弧的起点排在终点之前”的顶点序列。若序列中 v₁ 在 v₂ 之前，可以有弧 v₁→v₂，也可以只有从 v₁ 到 v₂ 的路径；但若存在从 v₂ 到 v₁ 的路径，v₂ 是 v₁ 的前驱，二者顺序必相反。

拓扑失败与强连通分量

Kahn 拓扑排序反复选择入度为 0 的顶点，删除其出边并更新入度；候选顶点可暂存在栈或队列。若某轮没有入度为 0 的剩余顶点而仍有顶点未输出，剩余子图含有有向环。环上的顶点彼此可达，因而形成顶点数大于 1 的强连通分量；反之，“全图是强连通图”并非必要条件。

唯一拓扑序列的判定

“拓扑序列唯一”不等于“图唯一”，也不要求每个顶点入度、出度最多为 1。唯一性要求每一步只有一个可选的入度为 0 顶点；若同时存在两个候选起点（或两个候选终点），它们可交换，序列就不唯一。即使序列唯一，也可存在分支、汇合或可增删而不改变该序列的弧，因此不能据序列唯一反推出唯一图。

图算法综合应用

破圈法（Reverse-Delete）

按非增权重考察边；若删除某边后图仍连通就删除，否则保留。删除环上最大边保持连通，且由环交换性质存在一棵 MST 不含该边，因此反复处理得到 MST。权值并列时不能随意断言某条边必删，应以删除后连通性判断。

AOE 工序先驱表

由先驱表构边：A=1→2(3)、B=1→3(2)、C=2→4(2)、D=2→5(3)、E=3→4(4)、F=2→8(3)、G=4→8(2)、H=5→8(1)。正向计算 ve=(0,3,2,6,6,8)，逆向 vl=(0,4,2,6,7,8)；活动松弛可由 e=ve[u]、l=vl[v]-w 计算。关键活动为 B、E、G，工期 8。

最短路树不等于最小生成树

Dijkstra 优化的是单源最短距离，MST 优化的是全树总权，目标不同。反例：a-b、a-c、a-d 权均 5，b-d、c-d 权均 1；从 a 可取总权 15 的最短路树，而 MST 取 a-d、b-d、c-d，总权 7。

三色 DFS 拓扑排序

白色顶点开始 DFS，进入时标灰；遇到灰色邻点即发现回边，图有环。顶点所有邻接点完成后标黑并压入栈，最终按完成时间逆序输出拓扑序。对每个未访问顶点启动 DFS 可覆盖非连通 DAG，邻接表复杂度为 O(V+E)。