手工模拟 DFS、BFS、Prim、Kruskal、Dijkstra、Floyd、拓扑排序和关键路径,掌握各算法的问题前提与复杂度。

# 一、深度优先与广度优先遍历

图遍历要用 visited 标记已发现的顶点,避免环导致重复访问。若图不连通,仅从一个起点遍历不能覆盖所有顶点,因此完整遍历需从每个仍未访问的顶点启动一次。

# 1. 深度优先搜索

深度优先搜索(DFS)沿一条尚未访问的边尽量向深处走,直到不能继续,再回溯。递归版本隐式使用调用栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdbool.h>

void DFS(AdjListGraph *G, int v, bool visited[]) {
visited[v] = true;
Visit(v);

for (ArcNode *p = G->vertices[v].firstArc; p != NULL; p = p->next) {
int w = p->adjvex;
if (!visited[w]) {
DFS(G, w, visited);
}
}
}

void DFSTraverse(AdjListGraph *G) {
bool visited[MAX_VERTEX_NUM] = {false};
for (int v = 0; v < G->vexnum; v++) {
if (!visited[v]) {
DFS(G, v, visited);
}
}
}

邻接表实现时,时间复杂度为 O(V+E)O(V+E),递归栈最坏为 O(V)O(V);邻接矩阵实现需扫描整行,时间复杂度为 O(V2)O(V^2)。

# 2. 广度优先搜索

广度优先搜索(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
26
27
28
29
void BFS(AdjListGraph *G, int start, bool visited[]) {
int queue[MAX_VERTEX_NUM];
int front = 0;
int rear = 0;

visited[start] = true;
queue[rear++] = start;
while (front < rear) {
int v = queue[front++];
Visit(v);

for (ArcNode *p = G->vertices[v].firstArc; p != NULL; p = p->next) {
int w = p->adjvex;
if (!visited[w]) {
visited[w] = true;
queue[rear++] = w;
}
}
}
}

void BFSTraverse(AdjListGraph *G) {
bool visited[MAX_VERTEX_NUM] = {false};
for (int v = 0; v < G->vexnum; v++) {
if (!visited[v]) {
BFS(G, v, visited);
}
}
}

将顶点入队时立即标记 visited,能确保每个顶点最多入队一次。邻接表 BFS 的时间复杂度为 O(V+E)O(V+E)。在无权图中,BFS 首次到达某顶点时得到从起点出发的最少边数路径。

# 二、最小生成树

连通无向带权图的生成树包含全部顶点、恰有 V−1V-1 条边且无回路。总权值最小的生成树称为最小生成树(MST)。若原图不连通,结果是最小生成森林。

# 1. Prim 算法

Prim 从一个顶点开始,每次选择一条连接 “已纳入顶点集合” 和 “未纳入顶点” 的最小权边,将新顶点加入生成树,直至包含全部顶点。邻接矩阵配合线性扫描时,复杂度为 O(V2)O(V^2);邻接表配合最小堆通常为 O(Elog⁡V)O(E\log V)。

# 2. Kruskal 算法

Kruskal 将所有边按权值升序排列,依次尝试加入当前森林。若边的两个端点已属于同一集合,则加入会形成回路,应跳过;否则加入并合并两个集合。并查集用于判定连通性,排序是主要代价,复杂度通常为 O(Elog⁡E)O(E\log E)。

对比项PrimKruskal
每步选择已有树到新顶点的最小边全图尚未处理的最小权边
维护对象一棵逐步扩大的树多棵互不相交的树
常用表示邻接矩阵或邻接表加堆边集数组加并查集
常见适用情形稠密图稀疏图

# 三、最短路径

# 1. Dijkstra 单源最短路径

Dijkstra 适用于边权非负的带权图。维护集合 SS 保存已确定最短距离的顶点;每次从 V−SV-S 中选择当前距离最小的顶点 uu,并用 uu 松弛其邻边:

dist⁡[v]←min⁡(dist⁡[v],dist⁡[u]+w(u,v)).\operatorname{dist}[v]\leftarrow \min(\operatorname{dist}[v],\operatorname{dist}[u]+w(u,v)).

邻接矩阵加线性选点为 O(V2)O(V^2);邻接表加优先队列通常为 O((V+E)log⁡V)O((V+E)\log V)。存在负权边时不能使用 Dijkstra,因为一个已确定的距离之后仍可能被负边降低。

# 2. Floyd 全源最短路径

Floyd 算法枚举中间顶点,逐步允许路径经过顶点 0,…,k0,\ldots,k:

d[i][j]←min⁡(d[i][j],d[i][k]+d[k][j]).d[i][j]\leftarrow \min\bigl(d[i][j],\,d[i][k]+d[k][j]\bigr).

1
2
3
4
5
6
7
8
9
10
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != INF && dist[k][j] != INF &&
dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}

Floyd 时间复杂度为 O(V3)O(V^3),空间复杂度为 O(V2)O(V^2);可以处理负权边,但不能有负权回路。若更新后某个 d[i][i]<0d[i][i]<0,说明存在可检测到的负权回路。

# 四、拓扑排序

有向无环图的拓扑序列是顶点的线性排列,使每条弧的起点都排在终点之前。Kahn 算法反复选取入度为 00 的顶点输出,并删除其出边:

  1. 计算所有顶点的入度,将入度为 00 的顶点入队。
  2. 队头顶点出队并加入结果序列。
  3. 删除它的所有出边,对应邻接点入度减一;新变为 00 的顶点入队。
  4. 若输出顶点数等于 VV,则图是 DAG;否则图中存在有向环。

邻接表下时间复杂度为 O(V+E)O(V+E)。拓扑序列可能不唯一。顶点活动网络(AOV)用顶点表示活动,弧表示先后约束;拓扑排序可判断是否存在满足全部约束的顺序。

# 五、关键路径

AOE 网用顶点表示事件、带权有向边表示活动及持续时间,通常是单源单汇 DAG。关键路径是从源点到汇点的最长路径,其长度为整个工程完成所需的最短可能工期。位于关键路径上的活动延误会使工程总工期延长。

按拓扑序计算事件最早发生时间:

ve[j]=max⁡(i,j)∈E{ve[i]+w(i,j)}.ve[j]=\max_{(i,j)\in E}\{ve[i]+w(i,j)\}.

令汇点最迟发生时间等于工程工期,再按逆拓扑序计算:

vl[i]=min⁡(i,j)∈E{vl[j]−w(i,j)}.vl[i]=\min_{(i,j)\in E}\{vl[j]-w(i,j)\}.

对活动弧 (i,j)(i,j),其最早开始时间 e(i,j)=ve[i]e(i,j)=ve[i],最迟开始时间 l(i,j)=vl[j]−w(i,j)l(i,j)=vl[j]-w(i,j)。若 e(i,j)=l(i,j)e(i,j)=l(i,j),该活动为关键活动。多源或多汇情形可增加持续时间为 00 的虚拟源点或汇点,再按单源单汇方法处理。

# 六、考场检查清单

  1. DFS/BFS 完整遍历不连通图时,要为每个未访问顶点启动新一轮。
  2. BFS 在无权图中求最少边数路径;带权图不能把 BFS 当作一般最短路算法。
  3. MST 只适用于连通无向带权图;Kruskal 加边前必须排除成环边。
  4. Dijkstra 要求边权非负;Floyd 可处理负权边,但不能有负权回路。
  5. 拓扑排序输出数少于顶点数时,图中存在有向环。
  6. AOE 网中关键活动的判定是 e=le=l,不要把 “持续时间最长” 误当成关键活动。
更新于 阅读次数 次

请我喝[茶]~( ̄▽ ̄)~*

梦前辈 微信支付

微信支付

梦前辈 支付宝

支付宝