图论核心算法与手算例题一、 代码实现C语言1. 图的邻接矩阵存储与DFS/BFS遍历#include stdio.h #include stdlib.h #define MAX_VERTEX_NUM 100 #define INFINITY 65535 // 图的邻接矩阵存储结构 typedef struct { int vexs[MAX_VERTEX_NUM]; // 顶点数组 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vexNum, arcNum; // 顶点数和边数 } MGraph; // 初始化图 void InitGraph(MGraph *G, int n) { G-vexNum n; G-arcNum 0; for (int i 0; i n; i) { for (int j 0; j n; j) { G-arcs[i][j] (i j) ? 0 : INFINITY; // 对角线为0其余为无穷大 } } } // 添加边无向图 void AddEdge(MGraph *G, int v, int w, int weight) { G-arcs[v][w] weight; G-arcs[w][v] weight; // 有向图则注释此行 G-arcNum; } // 深度优先搜索DFS递归实现 int visited[MAX_VERTEX_NUM] {0}; // 访问标记数组 void DFS(MGraph G, int v) { visited[v] 1; printf(%d , v); // 访问顶点v for (int w 0; w G.vexNum; w) { if (G.arcs[v][w] ! 0 G.arcs[v][w] ! INFINITY !visited[w]) { DFS(G, w); // 递归访问未访问的邻接点 } } } // 广度优先搜索BFS队列实现 #include stdbool.h #define QUEUE_SIZE 100 typedef struct { int data[QUEUE_SIZE]; int front, rear; } Queue; void InitQueue(Queue *Q) { Q-front Q-rear 0; } bool QueueEmpty(Queue Q) { return Q.front Q.rear; } bool EnQueue(Queue *Q, int e) { if ((Q-rear 1) % QUEUE_SIZE Q-front) return false; Q-data[Q-rear] e; Q-rear (Q-rear 1) % QUEUE_SIZE; return true; } bool DeQueue(Queue *Q, int *e) { if (QueueEmpty(*Q)) return false; *e Q-data[Q-front]; Q-front (Q-front 1) % QUEUE_SIZE; return true; } void BFS(MGraph G, int v) { int visited[MAX_VERTEX_NUM] {0}; Queue Q; InitQueue(Q); printf(%d , v); visited[v] 1; EnQueue(Q, v); while (!QueueEmpty(Q)) { DeQueue(Q, v); for (int w 0; w G.vexNum; w) { if (G.arcs[v][w] ! 0 G.arcs[v][w] ! INFINITY !visited[w]) { printf(%d , w); visited[w] 1; EnQueue(Q, w); } } } } // 测试DFS和BFS int main() { MGraph G; InitGraph(G, 5); AddEdge(G, 0, 1, 1); AddEdge(G, 0, 2, 1); AddEdge(G, 1, 3, 1); AddEdge(G, 2, 4, 1); printf(DFS遍历结果: ); DFS(G, 0); printf( ); printf(BFS遍历结果: ); BFS(G, 0); printf( ); return 0; }2. Prim算法最小生成树// Prim算法求最小生成树邻接矩阵 void Prim(MGraph G) { int lowcost[MAX_VERTEX_NUM]; // 存储当前生成树到剩余顶点的最小权值 int closest[MAX_VERTEX_NUM]; // 存储最小权值边对应的顶点 int min, k; // 从顶点0开始构造最小生成树 for (int i 0; i G.vexNum; i) { lowcost[i] G.arcs[0][i]; // 初始化lowcost数组 closest[i] 0; // 所有顶点初始依附于顶点0 } printf(最小生成树的边: ); for (int i 1; i G.vexNum; i) { min INFINITY; k 0; // 寻找当前lowcost中的最小值 for (int j 1; j G.vexNum; j) { if (lowcost[j] ! 0 lowcost[j] min) { min lowcost[j]; k j; } } printf((%d, %d) 权值: %d , closest[k], k, min); lowcost[k] 0; // 将顶点k加入生成树 // 更新lowcost和closest数组 for (int j 1; j G.vexNum; j) { if (lowcost[j] ! 0 G.arcs[k][j] lowcost[j]) { lowcost[j] G.arcs[k][j]; closest[j] k; } } } }3. Dijkstra算法单源最短路径// Dijkstra算法求单源最短路径 void Dijkstra(MGraph G, int v0) { int dist[MAX_VERTEX_NUM]; // 从v0到各顶点的最短路径长度 int path[MAX_VERTEX_NUM]; // 前驱顶点数组 int S[MAX_VERTEX_NUM] {0}; // 标记是否已找到最短路径 // 初始化 for (int i 0; i G.vexNum; i) { dist[i] G.arcs[v0][i]; if (dist[i] INFINITY) path[i] v0; else path[i] -1; } S[v0] 1; // 将v0加入S集 // 循环n-1次每次确定一个顶点的最短路径 for (int i 1; i G.vexNum; i) { int min INFINITY; int u v0; // 选择当前dist中的最小值 for (int j 0; j G.vexNum; j) { if (!S[j] dist[j] min) { min dist[j]; u j; } } S[u] 1; // 将顶点u加入S集 // 更新dist和path数组 for (int w 0; w G.vexNum; w) { if (!S[w] G.arcs[u][w] INFINITY dist[u] G.arcs[u][w] dist[w]) { dist[w] dist[u] G.arcs[u][w]; path[w] u; } } } // 输出结果 printf(从顶点%d出发的最短路径: , v0); for (int i 0; i G.vexNum; i) { if (i ! v0) { printf(到顶点%d的最短距离: %d , i, dist[i]); } } }4. Floyd算法多源最短路径// Floyd算法求所有顶点对之间的最短路径 void Floyd(MGraph G) { int A[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 距离矩阵 int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 路径矩阵 // 初始化 for (int i 0; i G.vexNum; i) { for (int j 0; j G.vexNum; j) { A[i][j] G.arcs[i][j]; if (i ! j A[i][j] INFINITY) path[i][j] i; else path[i][j] -1; } } // 三重循环更新 for (int k 0; k G.vexNum; k) { for (int i 0; i G.vexNum; i) { for (int j 0; j G.vexNum; j) { if (A[i][k] A[k][j] A[i][j]) { A[i][j] A[i][k] A[k][j]; path[i][j] path[k][j]; } } } } // 输出结果示例输出A矩阵 printf(Floyd算法结果距离矩阵: ); for (int i 0; i G.vexNum; i) { for (int j 0; j G.vexNum; j) { if (A[i][j] INFINITY) printf(INF ); else printf(%3d , A[i][j]); } printf( ); } }5. 拓扑排序基于邻接表// 邻接表存储结构 typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 } ArcNode; typedef struct VNode { int data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针 } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; // 拓扑排序Kahn算法 int TopologicalSort(ALGraph G) { int indegree[MAX_VERTEX_NUM] {0}; int stack[MAX_VERTEX_NUM], top -1; int count 0; // 计数输出的顶点数 // 计算所有顶点的入度 for (int i 0; i G.vexnum; i) { ArcNode *p G.vertices[i].firstarc; while (p) { indegree[p-adjvex]; p p-nextarc; } } // 将所有入度为0的顶点入栈 for (int i 0; i G.vexnum; i) { if (indegree[i] 0) { stack[top] i; } } printf(拓扑排序结果: ); while (top ! -1) { int v stack[top--]; printf(%d , v); count; // 删除顶点v的所有出边 ArcNode *p G.vertices[v].firstarc; while (p) { int k p-adjvex; indegree[k]--; if (indegree[k] 0) { stack[top] k; } p p-nextarc; } } if (count G.vexnum) { printf( 图中存在环无法完成拓扑排序 ); return 0; } return 1; }6. 关键路径算法// 关键路径算法基于拓扑排序 typedef struct { int ve[MAX_VERTEX_NUM]; // 事件最早发生时间 int vl[MAX_VERTEX_NUM]; // 事件最迟发生时间 } CriticalPath; int CriticalPathMethod(ALGraph G) { int indegree[MAX_VERTEX_NUM] {0}; int stack1[MAX_VERTEX_NUM], top1 -1; // 用于拓扑排序的栈 int stack2[MAX_VERTEX_NUM], top2 -1; // 用于逆拓扑排序的栈 CriticalPath cp; // 初始化ve数组 for (int i 0; i G.vexnum; i) cp.ve[i] 0; // 计算入度并初始化栈 for (int i 0; i G.vexnum; i) { ArcNode *p G.vertices[i].firstarc; while (p) { indegree[p-adjvex]; p p-nextarc; } } // 拓扑排序求ve for (int i 0; i G.vexnum; i) { if (indegree[i] 0) stack1[top1] i; } int count 0; while (top1 ! -1) { int v stack1[top1--]; stack2[top2] v; // 将顶点压入逆拓扑栈 count; ArcNode *p G.vertices[v].firstarc; while (p) { int k p-adjvex; if (--indegree[k] 0) stack1[top1] k; // 更新ve[k] if (cp.ve[v] 1 cp.ve[k]) { // 假设边权为1 cp.ve[k] cp.ve[v] 1; } p p-nextarc; } } if (count G.vexnum) return 0; // 存在环 // 初始化vl数组 for (int i 0; i G.vexnum; i) cp.vl[i] cp.ve[stack2[top2]]; // 逆拓扑排序求vl while (top2 ! -1) { int v stack2[top2--]; ArcNode *p G.vertices[v].firstarc; while (p) { int k p-adjvex; if (cp.vl[k]1 cp.vl[v]) { // 假设边权为1 cp.vl[v] cp.vl[k]1; } p p-nextarc; } } // 输出关键路径 printf(关键路径: ); for (int i 0; i G.vexnum; i) { if (cp.ve[i] cp.vl[i]) { printf(%d , i); } } printf( ); return 1; }二、 手算步骤与例题1. Prim算法手算例题题目使用Prim算法构造下图的最小生成树从顶点A开始。A /|\ 1 3 4 / | \ B--2--C \ | / 5 6 \| D边权AB1, AC3, AD4, BC2, BD5, CD6手算步骤初始化选择A作为起点U{A}V-U{B,C,D}第一轮比较边AB(1), AC(3), AD(4)选择最小权值边AB(1)将B加入UU{A,B}第二轮比较边AC(3), AD(4), BC(2)选择最小权值边BC(2)将C加入UU{A,B,C}第三轮比较边AD(4), CD(6)选择最小权值边AD(4)将D加入UU{A,B,C,D}结果最小生成树包含边AB(1), BC(2), AD(4)总权值72. Dijkstra算法手算例题题目使用Dijkstra算法求顶点A到其他各顶点的最短路径。A /|\2 6 9 / | \ B--1--C \ | / 3 2 \| D边权AB2, AC6, AD9, BC1, BD3, CD2手算步骤表格形式步骤S已确定最短路径的顶点集U未确定最短路径的顶点集dist[B]dist[C]dist[D]初始化{A}{B,C,D}2691{A,B}{C,D}2min(6, 213)3min(9, 235)52{A,B,C}{D}23min(5, 325)53{A,B,C,D}{}235结果A到B最短路径2A到C最短路径3A到D最短路径53. Floyd算法手算例题题目使用Floyd算法求所有顶点对之间的最短路径邻接矩阵如下。初始邻接矩阵 A B C A 0 2 6 B ∞0 1 C ∞ ∞ 0手算步骤初始化A⁽⁰⁾ 初始矩阵k0以A为中间点B→Cmin(∞, 268) ∞无变化C→Bmin(∞, ∞∞) ∞k1以B为中间点A→Cmin(6, 213) 3C→Amin(∞, ∞∞) ∞k2以C为中间点A→Bmin(2, 3∞) 2B→Amin(∞, 1∞) ∞最终结果矩阵A B C A 0 2 3 B ∞ 0 1 C ∞ ∞ 04. 拓扑排序手算例题题目对下图进行拓扑排序。A → B → D ↓ ↗ C → E手算步骤计算入度A(0), B(1), C(1), D(2), E(2)第一轮选择入度为0的顶点A输出A删除A及其出边更新入度B(0), C(0), D(2), E(2)第二轮选择入度为0的顶点B或C假设选B输出B删除B及其出边更新入度C(0), D(1), E(2)第三轮选择入度为0的顶点C输出C删除C及其出边更新入度D(0), E(1)第四轮选择入度为0的顶点D输出D删除D及其出边更新入度E(0)第五轮选择入度为0的顶点E输出E结果一种可能的拓扑序列为 A → B → C → D → E5. 关键路径手算例题题目求下图AOE网的关键路径。23 A —→ B —→ D ↘ ↗1↘ /2 C活动与时间a1(A→B)2, a2(A→C)1, a3(B→D)3, a4(C→D)2手算步骤求ve事件最早发生时间ve(A)0ve(B)max{ve(A)2}2 - ve(C)max{ve(A)1}1 - ve(D)max{ve(B)35, ve(C)23}5求vl事件最迟发生时间vl(D)ve(D)5 - vl(B)min{vl(D)-3}2 - vl(C)min{vl(D)-2}3 - vl(A)min{vl(B)-20, vl(C)-12}0求e活动最早开始时间和l活动最迟开始时间a1: eve(A)0, lvl(B)-20 a2: eve(A)0, lvl(C)-12 - a3: eve(B)2, lvl(D)-32a4: eve(C)1, lvl(D)-23求关键活动el的活动是关键活动a1: el0 ✓ - a2: e0≠l2 ✗a3: el2 ✓ - a4: e1≠l3 ✗结果关键路径为 A → B → D总工期5三、 算法对比总结算法适用场景时间复杂度空间复杂度核心思想DFS/BFS图的遍历、连通性判断O(VE)O(V)DFS深度探索BFS广度探索Prim稠密图的最小生成树O(V²)O(V)从一点开始每次添加距离当前树最近的顶点Dijkstra单源最短路径无负权O(V²)O(V)贪心策略每次选择距离源点最近的未处理顶点Floyd多源最短路径O(V³)O(V²)动态规划通过中间点逐步优化所有顶点对距离拓扑排序有向无环图的排序O(VE)O(V)不断删除入度为0的顶点关键路径AOE网求关键活动O(VE)O(V)基于拓扑排序求ve和vlel的活动为关键活动注1. Prim算法通常用于稠密图Kruskal算法未在用户query中要求更适合稀疏图。2. Dijkstra算法不能处理带负权边的图。3. 拓扑排序可用于检测有向图中是否存在环。4. 关键路径算法基于拓扑排序用于确定项目的最短完成时间和关键活动。参考来源C 408—《数据结构》图、查找、排序专题考点含解析-云社区-华为云408数据结构常考算法 - CSDN文库《数据结构》代码【数据结构与编译原理】图论算法与文法分类核心知识点最短路径、最小生成树、拓扑排序、关键路径及编译过程详解资源-CSDN下载图领计算机2026年408考研选择题专项突破1800题常见技术问题有哪些_编程语言-CSDN问答
【数据结构】图论算法C语言实现与手算例题
图论核心算法与手算例题一、 代码实现C语言1. 图的邻接矩阵存储与DFS/BFS遍历#include stdio.h #include stdlib.h #define MAX_VERTEX_NUM 100 #define INFINITY 65535 // 图的邻接矩阵存储结构 typedef struct { int vexs[MAX_VERTEX_NUM]; // 顶点数组 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vexNum, arcNum; // 顶点数和边数 } MGraph; // 初始化图 void InitGraph(MGraph *G, int n) { G-vexNum n; G-arcNum 0; for (int i 0; i n; i) { for (int j 0; j n; j) { G-arcs[i][j] (i j) ? 0 : INFINITY; // 对角线为0其余为无穷大 } } } // 添加边无向图 void AddEdge(MGraph *G, int v, int w, int weight) { G-arcs[v][w] weight; G-arcs[w][v] weight; // 有向图则注释此行 G-arcNum; } // 深度优先搜索DFS递归实现 int visited[MAX_VERTEX_NUM] {0}; // 访问标记数组 void DFS(MGraph G, int v) { visited[v] 1; printf(%d , v); // 访问顶点v for (int w 0; w G.vexNum; w) { if (G.arcs[v][w] ! 0 G.arcs[v][w] ! INFINITY !visited[w]) { DFS(G, w); // 递归访问未访问的邻接点 } } } // 广度优先搜索BFS队列实现 #include stdbool.h #define QUEUE_SIZE 100 typedef struct { int data[QUEUE_SIZE]; int front, rear; } Queue; void InitQueue(Queue *Q) { Q-front Q-rear 0; } bool QueueEmpty(Queue Q) { return Q.front Q.rear; } bool EnQueue(Queue *Q, int e) { if ((Q-rear 1) % QUEUE_SIZE Q-front) return false; Q-data[Q-rear] e; Q-rear (Q-rear 1) % QUEUE_SIZE; return true; } bool DeQueue(Queue *Q, int *e) { if (QueueEmpty(*Q)) return false; *e Q-data[Q-front]; Q-front (Q-front 1) % QUEUE_SIZE; return true; } void BFS(MGraph G, int v) { int visited[MAX_VERTEX_NUM] {0}; Queue Q; InitQueue(Q); printf(%d , v); visited[v] 1; EnQueue(Q, v); while (!QueueEmpty(Q)) { DeQueue(Q, v); for (int w 0; w G.vexNum; w) { if (G.arcs[v][w] ! 0 G.arcs[v][w] ! INFINITY !visited[w]) { printf(%d , w); visited[w] 1; EnQueue(Q, w); } } } } // 测试DFS和BFS int main() { MGraph G; InitGraph(G, 5); AddEdge(G, 0, 1, 1); AddEdge(G, 0, 2, 1); AddEdge(G, 1, 3, 1); AddEdge(G, 2, 4, 1); printf(DFS遍历结果: ); DFS(G, 0); printf( ); printf(BFS遍历结果: ); BFS(G, 0); printf( ); return 0; }2. Prim算法最小生成树// Prim算法求最小生成树邻接矩阵 void Prim(MGraph G) { int lowcost[MAX_VERTEX_NUM]; // 存储当前生成树到剩余顶点的最小权值 int closest[MAX_VERTEX_NUM]; // 存储最小权值边对应的顶点 int min, k; // 从顶点0开始构造最小生成树 for (int i 0; i G.vexNum; i) { lowcost[i] G.arcs[0][i]; // 初始化lowcost数组 closest[i] 0; // 所有顶点初始依附于顶点0 } printf(最小生成树的边: ); for (int i 1; i G.vexNum; i) { min INFINITY; k 0; // 寻找当前lowcost中的最小值 for (int j 1; j G.vexNum; j) { if (lowcost[j] ! 0 lowcost[j] min) { min lowcost[j]; k j; } } printf((%d, %d) 权值: %d , closest[k], k, min); lowcost[k] 0; // 将顶点k加入生成树 // 更新lowcost和closest数组 for (int j 1; j G.vexNum; j) { if (lowcost[j] ! 0 G.arcs[k][j] lowcost[j]) { lowcost[j] G.arcs[k][j]; closest[j] k; } } } }3. Dijkstra算法单源最短路径// Dijkstra算法求单源最短路径 void Dijkstra(MGraph G, int v0) { int dist[MAX_VERTEX_NUM]; // 从v0到各顶点的最短路径长度 int path[MAX_VERTEX_NUM]; // 前驱顶点数组 int S[MAX_VERTEX_NUM] {0}; // 标记是否已找到最短路径 // 初始化 for (int i 0; i G.vexNum; i) { dist[i] G.arcs[v0][i]; if (dist[i] INFINITY) path[i] v0; else path[i] -1; } S[v0] 1; // 将v0加入S集 // 循环n-1次每次确定一个顶点的最短路径 for (int i 1; i G.vexNum; i) { int min INFINITY; int u v0; // 选择当前dist中的最小值 for (int j 0; j G.vexNum; j) { if (!S[j] dist[j] min) { min dist[j]; u j; } } S[u] 1; // 将顶点u加入S集 // 更新dist和path数组 for (int w 0; w G.vexNum; w) { if (!S[w] G.arcs[u][w] INFINITY dist[u] G.arcs[u][w] dist[w]) { dist[w] dist[u] G.arcs[u][w]; path[w] u; } } } // 输出结果 printf(从顶点%d出发的最短路径: , v0); for (int i 0; i G.vexNum; i) { if (i ! v0) { printf(到顶点%d的最短距离: %d , i, dist[i]); } } }4. Floyd算法多源最短路径// Floyd算法求所有顶点对之间的最短路径 void Floyd(MGraph G) { int A[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 距离矩阵 int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 路径矩阵 // 初始化 for (int i 0; i G.vexNum; i) { for (int j 0; j G.vexNum; j) { A[i][j] G.arcs[i][j]; if (i ! j A[i][j] INFINITY) path[i][j] i; else path[i][j] -1; } } // 三重循环更新 for (int k 0; k G.vexNum; k) { for (int i 0; i G.vexNum; i) { for (int j 0; j G.vexNum; j) { if (A[i][k] A[k][j] A[i][j]) { A[i][j] A[i][k] A[k][j]; path[i][j] path[k][j]; } } } } // 输出结果示例输出A矩阵 printf(Floyd算法结果距离矩阵: ); for (int i 0; i G.vexNum; i) { for (int j 0; j G.vexNum; j) { if (A[i][j] INFINITY) printf(INF ); else printf(%3d , A[i][j]); } printf( ); } }5. 拓扑排序基于邻接表// 邻接表存储结构 typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 } ArcNode; typedef struct VNode { int data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针 } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; // 拓扑排序Kahn算法 int TopologicalSort(ALGraph G) { int indegree[MAX_VERTEX_NUM] {0}; int stack[MAX_VERTEX_NUM], top -1; int count 0; // 计数输出的顶点数 // 计算所有顶点的入度 for (int i 0; i G.vexnum; i) { ArcNode *p G.vertices[i].firstarc; while (p) { indegree[p-adjvex]; p p-nextarc; } } // 将所有入度为0的顶点入栈 for (int i 0; i G.vexnum; i) { if (indegree[i] 0) { stack[top] i; } } printf(拓扑排序结果: ); while (top ! -1) { int v stack[top--]; printf(%d , v); count; // 删除顶点v的所有出边 ArcNode *p G.vertices[v].firstarc; while (p) { int k p-adjvex; indegree[k]--; if (indegree[k] 0) { stack[top] k; } p p-nextarc; } } if (count G.vexnum) { printf( 图中存在环无法完成拓扑排序 ); return 0; } return 1; }6. 关键路径算法// 关键路径算法基于拓扑排序 typedef struct { int ve[MAX_VERTEX_NUM]; // 事件最早发生时间 int vl[MAX_VERTEX_NUM]; // 事件最迟发生时间 } CriticalPath; int CriticalPathMethod(ALGraph G) { int indegree[MAX_VERTEX_NUM] {0}; int stack1[MAX_VERTEX_NUM], top1 -1; // 用于拓扑排序的栈 int stack2[MAX_VERTEX_NUM], top2 -1; // 用于逆拓扑排序的栈 CriticalPath cp; // 初始化ve数组 for (int i 0; i G.vexnum; i) cp.ve[i] 0; // 计算入度并初始化栈 for (int i 0; i G.vexnum; i) { ArcNode *p G.vertices[i].firstarc; while (p) { indegree[p-adjvex]; p p-nextarc; } } // 拓扑排序求ve for (int i 0; i G.vexnum; i) { if (indegree[i] 0) stack1[top1] i; } int count 0; while (top1 ! -1) { int v stack1[top1--]; stack2[top2] v; // 将顶点压入逆拓扑栈 count; ArcNode *p G.vertices[v].firstarc; while (p) { int k p-adjvex; if (--indegree[k] 0) stack1[top1] k; // 更新ve[k] if (cp.ve[v] 1 cp.ve[k]) { // 假设边权为1 cp.ve[k] cp.ve[v] 1; } p p-nextarc; } } if (count G.vexnum) return 0; // 存在环 // 初始化vl数组 for (int i 0; i G.vexnum; i) cp.vl[i] cp.ve[stack2[top2]]; // 逆拓扑排序求vl while (top2 ! -1) { int v stack2[top2--]; ArcNode *p G.vertices[v].firstarc; while (p) { int k p-adjvex; if (cp.vl[k]1 cp.vl[v]) { // 假设边权为1 cp.vl[v] cp.vl[k]1; } p p-nextarc; } } // 输出关键路径 printf(关键路径: ); for (int i 0; i G.vexnum; i) { if (cp.ve[i] cp.vl[i]) { printf(%d , i); } } printf( ); return 1; }二、 手算步骤与例题1. Prim算法手算例题题目使用Prim算法构造下图的最小生成树从顶点A开始。A /|\ 1 3 4 / | \ B--2--C \ | / 5 6 \| D边权AB1, AC3, AD4, BC2, BD5, CD6手算步骤初始化选择A作为起点U{A}V-U{B,C,D}第一轮比较边AB(1), AC(3), AD(4)选择最小权值边AB(1)将B加入UU{A,B}第二轮比较边AC(3), AD(4), BC(2)选择最小权值边BC(2)将C加入UU{A,B,C}第三轮比较边AD(4), CD(6)选择最小权值边AD(4)将D加入UU{A,B,C,D}结果最小生成树包含边AB(1), BC(2), AD(4)总权值72. Dijkstra算法手算例题题目使用Dijkstra算法求顶点A到其他各顶点的最短路径。A /|\2 6 9 / | \ B--1--C \ | / 3 2 \| D边权AB2, AC6, AD9, BC1, BD3, CD2手算步骤表格形式步骤S已确定最短路径的顶点集U未确定最短路径的顶点集dist[B]dist[C]dist[D]初始化{A}{B,C,D}2691{A,B}{C,D}2min(6, 213)3min(9, 235)52{A,B,C}{D}23min(5, 325)53{A,B,C,D}{}235结果A到B最短路径2A到C最短路径3A到D最短路径53. Floyd算法手算例题题目使用Floyd算法求所有顶点对之间的最短路径邻接矩阵如下。初始邻接矩阵 A B C A 0 2 6 B ∞0 1 C ∞ ∞ 0手算步骤初始化A⁽⁰⁾ 初始矩阵k0以A为中间点B→Cmin(∞, 268) ∞无变化C→Bmin(∞, ∞∞) ∞k1以B为中间点A→Cmin(6, 213) 3C→Amin(∞, ∞∞) ∞k2以C为中间点A→Bmin(2, 3∞) 2B→Amin(∞, 1∞) ∞最终结果矩阵A B C A 0 2 3 B ∞ 0 1 C ∞ ∞ 04. 拓扑排序手算例题题目对下图进行拓扑排序。A → B → D ↓ ↗ C → E手算步骤计算入度A(0), B(1), C(1), D(2), E(2)第一轮选择入度为0的顶点A输出A删除A及其出边更新入度B(0), C(0), D(2), E(2)第二轮选择入度为0的顶点B或C假设选B输出B删除B及其出边更新入度C(0), D(1), E(2)第三轮选择入度为0的顶点C输出C删除C及其出边更新入度D(0), E(1)第四轮选择入度为0的顶点D输出D删除D及其出边更新入度E(0)第五轮选择入度为0的顶点E输出E结果一种可能的拓扑序列为 A → B → C → D → E5. 关键路径手算例题题目求下图AOE网的关键路径。23 A —→ B —→ D ↘ ↗1↘ /2 C活动与时间a1(A→B)2, a2(A→C)1, a3(B→D)3, a4(C→D)2手算步骤求ve事件最早发生时间ve(A)0ve(B)max{ve(A)2}2 - ve(C)max{ve(A)1}1 - ve(D)max{ve(B)35, ve(C)23}5求vl事件最迟发生时间vl(D)ve(D)5 - vl(B)min{vl(D)-3}2 - vl(C)min{vl(D)-2}3 - vl(A)min{vl(B)-20, vl(C)-12}0求e活动最早开始时间和l活动最迟开始时间a1: eve(A)0, lvl(B)-20 a2: eve(A)0, lvl(C)-12 - a3: eve(B)2, lvl(D)-32a4: eve(C)1, lvl(D)-23求关键活动el的活动是关键活动a1: el0 ✓ - a2: e0≠l2 ✗a3: el2 ✓ - a4: e1≠l3 ✗结果关键路径为 A → B → D总工期5三、 算法对比总结算法适用场景时间复杂度空间复杂度核心思想DFS/BFS图的遍历、连通性判断O(VE)O(V)DFS深度探索BFS广度探索Prim稠密图的最小生成树O(V²)O(V)从一点开始每次添加距离当前树最近的顶点Dijkstra单源最短路径无负权O(V²)O(V)贪心策略每次选择距离源点最近的未处理顶点Floyd多源最短路径O(V³)O(V²)动态规划通过中间点逐步优化所有顶点对距离拓扑排序有向无环图的排序O(VE)O(V)不断删除入度为0的顶点关键路径AOE网求关键活动O(VE)O(V)基于拓扑排序求ve和vlel的活动为关键活动注1. Prim算法通常用于稠密图Kruskal算法未在用户query中要求更适合稀疏图。2. Dijkstra算法不能处理带负权边的图。3. 拓扑排序可用于检测有向图中是否存在环。4. 关键路径算法基于拓扑排序用于确定项目的最短完成时间和关键活动。参考来源C 408—《数据结构》图、查找、排序专题考点含解析-云社区-华为云408数据结构常考算法 - CSDN文库《数据结构》代码【数据结构与编译原理】图论算法与文法分类核心知识点最短路径、最小生成树、拓扑排序、关键路径及编译过程详解资源-CSDN下载图领计算机2026年408考研选择题专项突破1800题常见技术问题有哪些_编程语言-CSDN问答
