算法和应用

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

DFS

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

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

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

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

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 都遵循这个框架，两者的不同点在于获取 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);
        }
    }
}

邻接表

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

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

// 全局变量，标记顶点是否被访问过
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;
    }
}

BFS

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

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

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

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

邻接表

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

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

最小生成树

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

准确的 MST 定义如下：在无向图 $G=(V,E)$ 中， $(u,v)$ 代表连接顶点 $u$ 和顶点 $v$ 的边，而 $w(u,v)$ 代表此边的权重。若存在 $T\subseteq E$ ，使得 $(V,T)$ 为树，且

w(T)=\sum_{(u,v)\in T}w(u,v)

在所有生成树中最小，则 $T$ 为 $G$ 的 最小生成树。

MST 满足以下特点：

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

Prim 算法

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

prim 算法步骤 如下：

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

补充

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

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

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

此时，

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

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

这样保证了：

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

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

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

Kruskal 算法

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

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

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

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

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

最短路径

Dijkstra 算法

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

执行轨迹

Dijkstra 如何选点并松弛邻边

逐步点击顶点，观察源点 S 到各点的暂定距离如何更新，以及最短距离何时最终确定。

0S1A2B3C4D

初始化源点 Sdist[S]=0，其余为 ∞；确定 S，松弛后得到 A=4、B=1。

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

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

补充

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

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

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

Dijkstra 所需的数据结构

dist[]：数组，dist[v] 表示起点到节点 v 的 当前已知最短路径长度。
- 初始化时：dist[source] = 0，其余节点均为 ∞。
visited[]：布尔数组，表示某个节点的最短路径是否已经被最终确定。
- 初始时：所有节点均为 false。

Dijkstra 算法流程

初始化
- 设起点为 source。
- dist[source] ← 0
- 对于其他顶点 v，dist[v] ← ∞
- visited[v] ← false
主循环（重复 |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 的最短路径。）
    
    $dist[v]=\min\{dist[v],dist[u]+w(u,v)\}.$
结束
- 当所有顶点都被访问后，dist[v] 就保存了起点到各个顶点的最短路径长度。

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

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

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[] // 表示起点到所有顶点的最短路径

假设顶点数为 $V$ 、边数为 $E$ ，使用邻接表和二叉最小堆实现时，Dijkstra 算法的时间复杂度为

O\bigl((V+E)\log V\bigr),

对连通图常简写为 $O(E\log V)$ 。若使用朴素数组从未确定顶点中选取最小距离，则复杂度为 $O(V^2)$ 。

Floyd 算法

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

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

\operatorname{dist}[i][j] =\min\bigl(\operatorname{dist}[i][j], \operatorname{dist}[i][k]+\operatorname{dist}[k][j]\bigr).

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

✨ 算法具体流程如下：

初始化距离矩阵 dist：
- dist[i][j] = 0（若 i=j）
- dist[i][j] = 边权（若 i→j 有边）
- dist[i][j] = ∞（其余情况）

三重循环更新最短路径

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]

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

若顶点数为 $n$ ，则 Floyd–Warshall 算法的时间复杂度为 $O(n^3)$ ，空间复杂度为 $O(n^2)$ 。该算法实现较直接，适合求任意两点之间的最短路径。

拓扑排序

拓扑排序是一种对图中顶点进行排序的方式：

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

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

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

AOV 网

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

算法步骤

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

Kahn 算法

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

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

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

DFS + 栈

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

对图进行深度优先遍历。
每个节点 DFS 结束后将其压入栈中。
最后将栈中元素逆序输出，就是 拓扑排序 结果。

DFS 过程中，每个节点在其所有后继节点访问完成后才被加入栈中，因此栈中元素的逆序正好满足 拓扑排序 所需的“前驱先于后继”的约束。

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

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

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

关键路径

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

AOE 网

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

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

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

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

事件和活动

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

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

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

事件的发生时间

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

两个关键时间

时间名称	含义	数学符号
最早发生时间	某事件最早可以发生的时间	$ve(i)$
最晚发生时间	某事件最晚必须发生的时间（不影响工期）	$vl(i)$

事件发生的判断逻辑

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

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

活动时间余量

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

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

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

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

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

对于一个活动 $A(i\to j)$ ，持续时间为 $d_{ij}$ ，其最早开始时间与最晚开始时间分别为

e(i,j)=ve(i),\qquad l(i,j)=vl(j)-d_{ij}.

因此时间余量为

l(i,j)-e(i,j)=vl(j)-ve(i)-d_{ij}.

其中：

ve(i) ：起点事件 i 的最早发生时间
vl(j) ：终点事件 j 的最晚发生时间
$d_{ij}$ ：活动持续时间

关键路径和关键活动

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

关键路径和关键活动的典型特征

关键活动的时间余量为 0：即对某活动 $A(i\to j)$ 有
$l(i,j)-e(i,j)=vl(j)-ve(i)-d_{ij}=0.$
说明该活动不能被延迟任何时间，否则将影响总工期。
判断关键活动应比较活动的最早、最晚开始时间：满足 $e(i,j)=l(i,j)$ 的活动才是关键活动。关键路径上的事件通常满足 $ve=vl$ ，但仅凭两个端点都满足 $ve=vl$ ，不能保证连接它们的活动就是关键活动。
关键路径是工程中的最长路径：它决定了整个项目从开始到结束所需的最短时间，也即项目总工期。
关键路径可能有多条：若多个路径的总时长都等于项目的最短完成时间，这些路径上的活动都必须受到严格监控。

算法步骤

求解 关键路径 时，需要先计算每个事件的最早发生时间（ve）和最晚发生时间（vl），再由它们计算每个活动的最早开始时间 $e$ 与最晚开始时间 $l$ 。所有满足 $e=l$ 的活动都是关键活动；由源点到汇点连接关键活动，得到关键路径。

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

1. 计算最早发生时间 `ve`

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

ve(k)=\max_{v_j\in \operatorname{Pred}(v_k)} \{ve(j)+\operatorname{weight}(v_j,v_k)\}.

其中 $\operatorname{Pred}(v_k)$ 表示 $v_k$ 的所有前驱结点。含义：顶点 $v_k$ 的最早发生时间，取决于它所有前驱活动完成的最晚时间。

2. 计算最迟发生时间 `vl`

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

vl(k)=\min_{v_j\in \operatorname{Succ}(v_k)} \{vl(j)-\operatorname{weight}(v_k,v_j)\}.

其中 $\operatorname{Succ}(v_k)$ 表示 $v_k$ 的所有后继结点。含义：顶点 $v_k$ 的最晚发生时间，取决于它所有后继活动施加的最早约束。

3. 确定关键路径

对每条活动 $A(i\to j)$ 计算 $e(i,j)=ve(i)$ 与 $l(i,j)=vl(j)-d_{ij}$ ；
若 $e(i,j)=l(i,j)$ ，该活动就是关键活动；
从源点到汇点沿关键活动连接，得到一条或多条关键路径。

用图表达树

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

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

算法适用条件与结果核对

DFS 与 BFS 的一次搜索只覆盖起始顶点所在的连通分量。若题目要求遍历整张非连通图，应在外层按顶点编号扫描：每发现一个未访问顶点，就再次启动 DFS 或 BFS，于是得到 DFS 森林或 BFS 森林。采用邻接表时，完整遍历的时间为 $O(|V|+|E|)$ ；采用邻接矩阵时需要扫描每个顶点的一整行，时间为 $O(|V|^2)$ 。访问顺序还受邻接点存放次序影响，题目没有规定次序时，不应擅自认定唯一序列。

最小生成树与最短路径不是同一类问题

Prim 和 Kruskal 都解决无向、带权、连通图的最小生成树问题。生成树只保留 $n-1$ 条边并连通全部顶点，优化目标是总权值最小；它不保证任意两点之间的路径最短。图不连通时，两种算法可分别得到每个分量的最小生成森林，而不是一棵覆盖全图的生成树。

Prim 每次从当前树到未加入顶点的割边中选最轻边；Kruskal 按全局边权从小到大尝试加入、遇到形成环的边就跳过。两者正确性的核心都是割性质：任一割中权值最小的安全边可以加入某棵 MST。权值相等时，MST 可能不唯一；不同的选边顺序得到不同树并不意味着算法错误。

最短路径的权值边界

Dijkstra 的贪心前提是所有边权非负：当顶点 $u$ 以当前最小暂定距离被选中时，任何尚未处理路径都不可能再把它变短。出现负边后，这个结论失效，即使图中没有负环也不能直接使用 Dijkstra。Floyd 的状态转移为

d^{(k)}[i][j] =\min\bigl(d^{(k-1)}[i][j], d^{(k-1)}[i][k]+d^{(k-1)}[k][j]\bigr),

它允许负边，但不允许可达的负权回路；算法结束后若某个 $d[i][i]<0$ ，就说明存在负环，相关最短路没有有限定义。计算时若任一加数为 $\infty$ ，不能把它当普通数相加，否则会把“不可达”错误地更新成一个有限距离。

拓扑序与关键路径的检查点

拓扑排序只适用于有向无环图。Kahn 算法结束时，若输出顶点数小于 $|V|$ ，说明剩余顶点的入度永远不能降为 0，图中必有环；这不是“有些顶点暂时没访问到”。在某一步同时有多个入度为 0 的顶点时，拓扑序通常不唯一。AOV 网的边表示先后约束，而 AOE 网的边表示耗时活动，二者不能把顶点和边的含义对调。

关键路径中，活动 $(i,j)$ 的最早开始时间为 $e(i,j)=ve(i)$ ，最晚开始时间为 $l(i,j)=vl(j)-w(i,j)$ 。只有满足 $e=l$ 的活动才是关键活动；两个端点都满足 $ve=vl$ 仍不足以推出连接它们的边必为关键活动。若多条源到汇路径总工期相同，就会有多条关键路径，任何一条上的活动延误都可能推迟工程完成。

由题目权值含义选择算法

BFS 求得的是无权图中“边数最少”的路径；若每条边权都相同为正数，它也等价于求总权值最小的路径。实现时应在顶点第一次入队时就标记已访问，并记录其前驱，回溯前驱才能输出一条具体路径。若等到出队才标记，一个顶点可能被多个前驱重复入队，队列状态和复杂度都会变得难以判断。

MST 与最短路对权值的限制也不同：最小生成树允许负权边，只要图是无向连通图，负边自然会优先被选中；Dijkstra 却不能处理负权边。Floyd 适合要求所有顶点对距离或图较小、较稠密的场景，时间为 $O(|V|^3)$ 、空间为 $O(|V|^2)$ 。单源非负权最短路若图很稀疏，常结合邻接表和优先队列，避免像邻接矩阵实现那样反复扫描全部顶点。

图算法的输出也要与目标一致：遍历算法输出访问序或搜索树，最短路算法输出距离与前驱，最小生成树输出边集与总权值，拓扑排序输出满足约束的一种线性序。它们都可能使用“访问标记”或“优先队列”，但维护的量不同，不能因为数据结构相同就混用更新规则。

算法和应用

DFS

邻接矩阵

邻接表

BFS

邻接矩阵

邻接表

最小生成树

Prim 算法

Kruskal 算法

最短路径

Dijkstra 算法

Dijkstra 所需的数据结构

Dijkstra 算法流程

Floyd 算法

拓扑排序

AOV 网

算法步骤

Kahn 算法

DFS + 栈

关键路径

AOE 网

事件和活动

事件的发生时间

两个关键时间

事件发生的判断逻辑

活动时间余量

关键路径和关键活动

关键路径和关键活动的典型特征

算法步骤

1. 计算最早发生时间 ve

2. 计算最迟发生时间 vl

3. 确定关键路径

用图表达树

算法适用条件与结果核对

最小生成树与最短路径不是同一类问题

最短路径的权值边界

拓扑序与关键路径的检查点

由题目权值含义选择算法

1. 计算最早发生时间 `ve`

2. 计算最迟发生时间 `vl`