【数据结构】图-----关键路径

一、核心前提AOE 网有向无环、带权边边代表活动顶点代表事件源点起点入度为 0、汇点终点出度为 0。关键路径从源点 → 汇点的最长路径决定工程最短完成时间路径上活动为关键活动。二、四大必背参数考试核心设顶点为事件边为活动ve[i]事件 i 的最早发生时间vl[i]事件 i 的最晚发生时间e活动最早开始时间l活动最晚开始时间l−e0 → 该活动为关键活动计算公式最早发生时间正向拓扑源点权最晚发生时间逆拓扑汇点汇点权活动时间活动 u,veve[u],lvl[v]−w三、算法步骤对 AOE 网做拓扑排序按拓扑序正向遍历求数组 ve按逆拓扑序反向遍历求数组 vl遍历所有边计算 、l−e0 的边 → 关键活动串联即为关键路径四、完整 C 语言代码邻接表・带详细注释#include stdio.h #include string.h #define MAXN 105 #define INF 0x3f3f3f3f // 边结点终点、权值、后继边 typedef struct Edge{ int to,w; struct Edge *next; }Edge; Edge* G[MAXN]; int n,m; int in[MAXN]; // 入度 int topo[MAXN],cnt; // 拓扑序列 int ve[MAXN],vl[MAXN]; // 加边 void addEdge(int u,int v,int w){ Edge *p(Edge*)malloc(sizeof(Edge)); p-tov; p-ww; p-nextG[u]; G[u]p; in[v]; } // 1.拓扑排序得到topo数组 void TopSort(){ int stk[MAXN],top0; cnt0; for(int i1;in;i) if(in[i]0) stk[top]i; while(top0){ int ustk[--top]; topo[cnt]u; for(Edge *pG[u];p;pp-next){ int vp-to; in[v]--; if(in[v]0) stk[top]v; } } } // 2.求ve正向拓扑 void getVE(){ memset(ve,0,sizeof(ve)); for(int i1;icnt;i){ int utopo[i]; for(Edge *pG[u];p;pp-next){ int vp-to; if(ve[v] ve[u]p-w) ve[v] ve[u]p-w; } } } // 3.求vl逆拓扑 void getVL(){ for(int i1;in;i) vl[i]ve[topo[cnt]]; for(int icnt;i1;i--){ int utopo[i]; for(Edge *pG[u];p;pp-next){ int vp-to; if(vl[u] vl[v]-p-w) vl[u] vl[v]-p-w; } } } // 4.查找并输出关键活动、关键路径 void KeyPath(){ printf(关键活动\n); for(int u1;un;u){ for(Edge *pG[u];p;pp-next){ int vp-to; int e ve[u]; int l vl[v] - p-w; if(e l){ printf(关键活动%d - %d 权%d\n,u,v,p-w); } } } printf(工程最短工期%d\n,ve[topo[cnt]]); } int main(){ scanf(%d%d,n,m); memset(G,0,sizeof(G)); memset(in,0,sizeof(in)); for(int i1;im;i){ int u,v,w; scanf(%d%d%d,u,v,w); addEdge(u,v,w); } TopSort(); getVE(); getVL(); KeyPath(); return 0; }五、考点必背关键路径仅存在于AOE 有向无环图关键路径 源点到汇点最长路径关键活动l−e0关键活动推迟→整体工期延长非关键活动有时间余量可适当延迟拓扑求 ve逆拓扑求 vl关键路径可能多条