【数据结构与算法】第41篇：图论（五）：拓扑排序与关键路径

目录一、AOV网与拓扑排序1.1 AOV网的定义1.2 拓扑排序1.3 算法思想Kahn算法1.4 代码实现二、AOE网与关键路径2.1 AOE网的定义2.2 关键路径概念2.3 算法步骤2.4 代码实现三、AOV网与AOE网对比四、关键路径的实际意义五、小结六、思考题一、AOV网与拓扑排序1.1 AOV网的定义AOV网Activity On Vertex Network用顶点表示活动用有向边表示活动之间的先后关系。边u → v表示活动 u 必须在活动 v 之前完成AOV网必须是有向无环图DAG示例课程先修关系text高等数学 → 离散数学 → 数据结构 → 算法设计 ↘ ↘ 线性代数 → 数值分析1.2 拓扑排序拓扑排序将DAG中所有顶点排成一个线性序列使得对每条边u → vu 都在 v 之前出现。应用课程安排编译依赖Makefile任务调度1.3 算法思想Kahn算法计算所有顶点的入度将所有入度为0的顶点入栈或队列弹出顶点加入拓扑序列将其所有邻接点的入度减1若邻接点入度变为0入栈重复直到栈空判断是否有环如果输出的顶点数 总顶点数说明图中有环。1.4 代码实现c#include stdio.h #include stdlib.h #define MAX_VERTICES 100 // 邻接表节点 typedef struct EdgeNode { int vertex; struct EdgeNode *next; } EdgeNode; typedef struct { EdgeNode *first; } VertexNode; typedef struct { VertexNode vertices[MAX_VERTICES]; int vertexCount; } Graph; // 栈结构 typedef struct { int data[MAX_VERTICES]; int top; } Stack; void initStack(Stack *s) { s-top -1; } int isEmpty(Stack *s) { return s-top -1; } void push(Stack *s, int val) { s-data[s-top] val; } int pop(Stack *s) { return s-data[s-top--]; } // 初始化图 void initGraph(Graph *g, int n) { g-vertexCount n; for (int i 0; i n; i) { g-vertices[i].first NULL; } } // 添加边 u - v void addEdge(Graph *g, int u, int v) { EdgeNode *e (EdgeNode*)malloc(sizeof(EdgeNode)); e-vertex v; e-next g-vertices[u].first; g-vertices[u].first e; } // 拓扑排序 int topologicalSort(Graph *g, int result[]) { int indegree[MAX_VERTICES] {0}; // 1. 计算入度 for (int i 0; i g-vertexCount; i) { EdgeNode *p g-vertices[i].first; while (p ! NULL) { indegree[p-vertex]; p p-next; } } // 2. 入度为0的顶点入栈 Stack stack; initStack(stack); for (int i 0; i g-vertexCount; i) { if (indegree[i] 0) { push(stack, i); } } // 3. 处理 int index 0; while (!isEmpty(stack)) { int u pop(stack); result[index] u; EdgeNode *p g-vertices[u].first; while (p ! NULL) { int v p-vertex; indegree[v]--; if (indegree[v] 0) { push(stack, v); } p p-next; } } // 判断是否有环 if (index ! g-vertexCount) { printf(图中有环无法进行拓扑排序\n); return 0; } return 1; } int main() { Graph g; initGraph(g, 6); // 构建DAG addEdge(g, 5, 2); addEdge(g, 5, 0); addEdge(g, 4, 0); addEdge(g, 4, 1); addEdge(g, 2, 3); addEdge(g, 3, 1); int result[MAX_VERTICES]; printf(拓扑排序序列: ); if (topologicalSort(g, result)) { for (int i 0; i g.vertexCount; i) { printf(%d , result[i]); } printf(\n); } return 0; }运行结果text拓扑排序序列: 4 5 2 0 3 1二、AOE网与关键路径2.1 AOE网的定义AOE网Activity On Edge Network用边表示活动用顶点表示事件。事件某个时间点表示它前面的活动已完成活动从事件i到事件j耗时w源点入度为0的顶点工程开始汇点出度为0的顶点工程结束示例项目进度text2 3 v1 → v2 → v4 | ↗ | 4 | / | 2 | /1 | v ↙ ↓ v3 → → → v5 52.2 关键路径概念最早开始时间ve事件最早发生时间最晚开始时间vl事件最晚发生时间不影响工期关键路径ve vl 的顶点组成的路径关键活动在关键路径上的活动关键路径上的活动任何延迟都会导致整个工程延期。2.3 算法步骤拓扑排序得到顶点顺序计算ve按拓扑序ve[j] max(ve[i] w(i,j))计算vl按逆拓扑序vl[i] min(vl[j] - w(i,j))汇点vlve判断关键活动对边i→j若ve[i] vl[j] - w(i,j)则为关键活动2.4 代码实现c#include stdio.h #include stdlib.h #include string.h #include limits.h #define MAX_VERTICES 100 #define INF INT_MAX // 边结构 typedef struct Edge { int to; int weight; struct Edge *next; } Edge; // 图结构 typedef struct { Edge *heads[MAX_VERTICES]; int vertexCount; } Graph; // 入度数组拓扑排序用 int indegree[MAX_VERTICES]; void initGraph(Graph *g, int n) { g-vertexCount n; for (int i 0; i n; i) { g-heads[i] NULL; indegree[i] 0; } } void addEdge(Graph *g, int from, int to, int weight) { Edge *e (Edge*)malloc(sizeof(Edge)); e-to to; e-weight weight; e-next g-heads[from]; g-heads[from] e; indegree[to]; } // 拓扑排序同时返回拓扑序 int topologicalSort(Graph *g, int topo[]) { int stack[MAX_VERTICES]; int top -1; for (int i 0; i g-vertexCount; i) { if (indegree[i] 0) { stack[top] i; } } int index 0; while (top ! -1) { int u stack[top--]; topo[index] u; Edge *e g-heads[u]; while (e ! NULL) { int v e-to; indegree[v]--; if (indegree[v] 0) { stack[top] v; } e e-next; } } return index g-vertexCount; } // 关键路径 void criticalPath(Graph *g) { int topo[MAX_VERTICES]; int ve[MAX_VERTICES]; // 最早发生时间 int vl[MAX_VERTICES]; // 最晚发生时间 // 复制入度拓扑排序会修改 int tempIndegree[MAX_VERTICES]; memcpy(tempIndegree, indegree, sizeof(indegree)); // 1. 拓扑排序 int stack[MAX_VERTICES]; int top -1; for (int i 0; i g-vertexCount; i) { if (tempIndegree[i] 0) { stack[top] i; } ve[i] 0; } int topoIndex 0; while (top ! -1) { int u stack[top--]; topo[topoIndex] u; Edge *e g-heads[u]; while (e ! NULL) { int v e-to; // 更新ve if (ve[u] e-weight ve[v]) { ve[v] ve[u] e-weight; } tempIndegree[v]--; if (tempIndegree[v] 0) { stack[top] v; } e e-next; } } // 2. 计算vl int sink topo[g-vertexCount - 1]; for (int i 0; i g-vertexCount; i) { vl[i] ve[sink]; } for (int i g-vertexCount - 1; i 0; i--) { int u topo[i]; Edge *e g-heads[u]; while (e ! NULL) { int v e-to; if (vl[v] - e-weight vl[u]) { vl[u] vl[v] - e-weight; } e e-next; } } // 3. 输出关键路径 printf(事件\tve\tvl\t关键事件\n); for (int i 0; i g-vertexCount; i) { printf(v%d\t%d\t%d\t%s\n, i, ve[i], vl[i], (ve[i] vl[i]) ? 是 : 否); } printf(\n关键活动:\n); for (int i 0; i g-vertexCount; i) { Edge *e g-heads[i]; while (e ! NULL) { int j e-to; int ete ve[i]; // 活动最早开始 int lte vl[j] - e-weight; // 活动最晚开始 if (ete lte) { printf(v%d → v%d (权值%d) 是关键活动\n, i, j, e-weight); } e e-next; } } printf(\n工程最短工期: %d\n, ve[sink]); } int main() { Graph g; initGraph(g, 6); // 构建AOE网顶点0~5 addEdge(g, 0, 1, 3); addEdge(g, 0, 2, 4); addEdge(g, 1, 3, 5); addEdge(g, 1, 4, 6); addEdge(g, 2, 3, 8); addEdge(g, 2, 4, 7); addEdge(g, 3, 5, 6); addEdge(g, 4, 5, 4); criticalPath(g); return 0; }运行结果text事件 ve vl 关键事件 v0 0 0 是 v1 3 4 否 v2 4 4 是 v3 12 12 是 v4 11 12 否 v5 18 18 是 关键活动: v0 → v2 (权值4) 是关键活动 v2 → v3 (权值8) 是关键活动 v3 → v5 (权值6) 是关键活动 工程最短工期: 18三、AOV网与AOE网对比对比项AOV网AOE网顶点活动事件边先后关系活动带权值主要问题拓扑排序可行性关键路径最短工期权值无有耗时应用课程安排、编译依赖项目管理、工程进度四、关键路径的实际意义应用说明项目管理找出关键任务重点关注工期压缩压缩非关键活动不缩短工期资源调配将资源优先分配给关键活动风险控制关键活动延迟会直接影响工期五、小结这一篇我们学习了拓扑排序和关键路径概念核心算法时间复杂度拓扑排序AOV网入度为0Kahn算法栈/队列O(VE)关键路径AOE网ve/vl拓扑序 逆拓扑序O(VE)关键公式ve[j] max(ve[i] w(i,j))vl[i] min(vl[j] - w(i,j))关键活动ve[i] vl[j] - w(i,j)注意关键路径可能有多条所有关键活动都必须在压缩范围内才能缩短工期。下一篇我们讲并查集。六、思考题拓扑排序的结果唯一吗什么情况下不唯一如何用拓扑排序检测一个有向图是否有环关键路径上的活动如果缩短工期一定会缩短吗如果AOE网有多条关键路径压缩某条关键路径上的活动能缩短工期吗欢迎在评论区讨论你的答案。