手工模拟 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 + E ) ,递归栈最坏为 O ( V ) O(V) O ( V ) ;邻接矩阵实现需扫描整行,时间复杂度为 O ( V 2 ) O(V^2) 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) O ( V + E ) 。在无权图中,BFS 首次到达某顶点时得到从起点出发的最少边数路径。
# 二、最小生成树连通无向带权图的生成树包含全部顶点、恰有 V − 1 V-1 V − 1 条边且无回路。总权值最小的生成树称为最小生成树(MST)。若原图不连通,结果是最小生成森林。
# 1. Prim 算法Prim 从一个顶点开始,每次选择一条连接 “已纳入顶点集合” 和 “未纳入顶点” 的最小权边,将新顶点加入生成树,直至包含全部顶点。邻接矩阵配合线性扫描时,复杂度为 O ( V 2 ) O(V^2) O ( V 2 ) ;邻接表配合最小堆通常为 O ( E log V ) O(E\log V) O ( E log V ) 。
# 2. Kruskal 算法Kruskal 将所有边按权值升序排列,依次尝试加入当前森林。若边的两个端点已属于同一集合,则加入会形成回路,应跳过;否则加入并合并两个集合。并查集用于判定连通性,排序是主要代价,复杂度通常为 O ( E log E ) O(E\log E) O ( E log E ) 。
对比项 Prim Kruskal 每步选择 已有树到新顶点的最小边 全图尚未处理的最小权边 维护对象 一棵逐步扩大的树 多棵互不相交的树 常用表示 邻接矩阵或邻接表加堆 边集数组加并查集 常见适用情形 稠密图 稀疏图
# 三、最短路径# 1. Dijkstra 单源最短路径Dijkstra 适用于边权非负的带权图。维护集合 S S S 保存已确定最短距离的顶点;每次从 V − S V-S V − S 中选择当前距离最小的顶点 u u u ,并用 u u u 松弛其邻边:
dist [ v ] ← min ( dist [ v ] , dist [ u ] + w ( u , v ) ) . \operatorname{dist}[v]\leftarrow \min(\operatorname{dist}[v],\operatorname{dist}[u]+w(u,v)). d i s t [ v ] ← min ( d i s t [ v ] , d i s t [ u ] + w ( u , v ) ) .
邻接矩阵加线性选点为 O ( V 2 ) O(V^2) O ( V 2 ) ;邻接表加优先队列通常为 O ( ( V + E ) log V ) O((V+E)\log V) O ( ( V + E ) log V ) 。存在负权边时不能使用 Dijkstra,因为一个已确定的距离之后仍可能被负边降低。
# 2. Floyd 全源最短路径Floyd 算法枚举中间顶点,逐步允许路径经过顶点 0 , … , k 0,\ldots,k 0 , … , 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). d [ i ] [ j ] ← min ( d [ i ] [ j ] , d [ i ] [ k ] + d [ k ] [ j ] ) .
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 ( V 3 ) O(V^3) O ( V 3 ) ,空间复杂度为 O ( V 2 ) O(V^2) O ( V 2 ) ;可以处理负权边,但不能有负权回路。若更新后某个 d [ i ] [ i ] < 0 d[i][i]<0 d [ i ] [ i ] < 0 ,说明存在可检测到的负权回路。
# 四、拓扑排序有向无环图的拓扑序列是顶点的线性排列,使每条弧的起点都排在终点之前。Kahn 算法反复选取入度为 0 0 0 的顶点输出,并删除其出边:
计算所有顶点的入度,将入度为 0 0 0 的顶点入队。 队头顶点出队并加入结果序列。 删除它的所有出边,对应邻接点入度减一;新变为 0 0 0 的顶点入队。 若输出顶点数等于 V V V ,则图是 DAG;否则图中存在有向环。 邻接表下时间复杂度为 O ( V + E ) O(V+E) O ( V + E ) 。拓扑序列可能不唯一。顶点活动网络(AOV)用顶点表示活动,弧表示先后约束;拓扑排序可判断是否存在满足全部约束的顺序。
# 五、关键路径AOE 网用顶点表示事件、带权有向边表示活动及持续时间,通常是单源单汇 DAG。关键路径是从源点到汇点的最长路径,其长度为整个工程完成所需的最短可能工期。位于关键路径上的活动延误会使工程总工期延长。
按拓扑序计算事件最早发生时间:
v e [ j ] = max ( i , j ) ∈ E { v e [ i ] + w ( i , j ) } . ve[j]=\max_{(i,j)\in E}\{ve[i]+w(i,j)\}. v e [ j ] = ( i , j ) ∈ E max { v e [ i ] + w ( i , j ) } .
令汇点最迟发生时间等于工程工期,再按逆拓扑序计算:
v l [ i ] = min ( i , j ) ∈ E { v l [ j ] − w ( i , j ) } . vl[i]=\min_{(i,j)\in E}\{vl[j]-w(i,j)\}. v l [ i ] = ( i , j ) ∈ E min { v l [ j ] − w ( i , j ) } .
对活动弧 ( i , j ) (i,j) ( i , j ) ,其最早开始时间 e ( i , j ) = v e [ i ] e(i,j)=ve[i] e ( i , j ) = v e [ i ] ,最迟开始时间 l ( i , j ) = v l [ j ] − w ( i , j ) l(i,j)=vl[j]-w(i,j) l ( i , j ) = v l [ j ] − w ( i , j ) 。若 e ( i , j ) = l ( i , j ) e(i,j)=l(i,j) e ( i , j ) = l ( i , j ) ,该活动为关键活动。多源或多汇情形可增加持续时间为 0 0 0 的虚拟源点或汇点,再按单源单汇方法处理。
# 六、考场检查清单DFS/BFS 完整遍历不连通图时,要为每个未访问顶点启动新一轮。 BFS 在无权图中求最少边数路径;带权图不能把 BFS 当作一般最短路算法。 MST 只适用于连通无向带权图;Kruskal 加边前必须排除成环边。 Dijkstra 要求边权非负;Floyd 可处理负权边,但不能有负权回路。 拓扑排序输出数少于顶点数时,图中存在有向环。 AOE 网中关键活动的判定是 e = l e=l e = l ,不要把 “持续时间最长” 误当成关键活动。