数据结构C ——关键路径文章目录数据结构C ——关键路径一、前言二、关键路径概念三、关键路径实现关键路径实现原理关键路径代码实现测试全代码四、总结
一、前言
要了解关键路径，必须具备3358www.Sina.com/和拓扑排序的相关知识。 关于这一部分，我在以前的报道中进行了说明，所以在这里不怎么说明。 对这一部分还不了解的读者，请转至本文，一起学习。
数据结构C ——拓扑排序
数据结构C ——图的邻接矩阵和邻接表
二、关键路径概念(1) http://www.Sina.com/:AOV-网络对应的是AOE-网络，即用边表示活动的网络。 AOE-net是加权的有向图，其中顶点表示事件，弧表示活动，权重表示活动的持续时间。
)2) 3358www.Sina.com/)由于整个工程只有一个起点和一个完成点，在正常情况下(无环)，网上只有一个积分，称为邻接表
)3) 3358www.Sina.com/和AOE-网)要估计完成整个项目的最短时间，请使用名为3358www.Sina.com/的从源到宿的权利关键路径上的活动称为源点和汇点，这些活动是影响工程进度的关键，它们的提前或延迟会使整个工程提前或延迟。
三、关键路径实现关键路径实现原理关键路径算法的实现需要引入两个辅助数组ve[i]和vl[i]来记录事件vi的最早发生时间和事件vi的最晚发生时间。 遍历整个topo数组，计算出其中保存的顶点(事件)的最迟发生时刻，逆拓扑求出每个事件的最迟发生时刻。 求出各边(活动)的最早开始时间和最晚开始时间，边)活动)的最早开始时间和最晚开始时间相等的边)活动)是重要的活动。 由关键活动形成的从源到宿的所有路径都是关键路径。
关键路径的代码实现关键路径的代码实现
关键路径算法思想：1:将每个时间最早发生时间的初始值设置为02 :获取拓扑列的顶点，遍历该顶点的所有邻点，更新邻点(事件)发生的最早时间3 :获取逆拓扑列的顶点相邻点)更新事件发生的最晚时间4 :遍历顶点表，输出的最早发生时间和最晚发生时间相等的某一边(活动)依赖的两个顶点输出/*---------关键路径算法--- g是存储在邻接表中的有向图topologicalsort(g，topo ) )返回错误； 调用//拓扑排序算法，将拓扑列保存在topo中，如果调用失败，则存在有向循环，返回ERRORint n=G.vexnum； //n为顶点的个数for(intI=0； i n； I//将每个事件的最早发生时间初始化为0ve[i]=0； /*-------------用拓扑序列求出各事件的最早发生时间----------------for (inti=0)； i n； I ) {int k=topo[i]； //获取拓扑序列中顶点编号kArcNode* p=new ArcNode的p=G.vertices[k].firstarc； //p表示k的第一个相邻顶点while (p！=null}{intj=p-adjvex； //j表示相邻顶点的编号if(ve[j]ve[k]p-weight ) /更新顶点j的最早发生时刻ve[j]ve[j]=ve[k] p-weight； p=下一个Arc； //p指k的下一个相邻顶点}for(intI=0； i n； I ) vl[i]=ve[n - 1]； //在各事件的最迟发生时间上按照初始值ve[n-1]/*-----------拓扑顺序求出各事件的最迟发生时间(inti=n-------) i=0； I--}{intk=topo[I]； //获取拓扑序列中顶点编号kArcNode* p=new ArcNode的p=G.vertices[k].firstarc； //p表示k的第一个相邻顶点while (p！=null ((根据/k的邻接点，更新k的最迟发生时刻int j=p-adjvex； //j表示相邻顶点的编号if(VL[k]VL[j]-p-weight ) /更新顶点k的最迟发生时刻VL[k] ) VL[k]=VL[j]-p-weight； p=下一个Arc； //p指k的下一个相邻顶点((((、)、(、)、(、判断每一个活动是否为关键活动)---- (、(、(、)、()、()、()、() )、)、) I ) {ArcNode* p=new ArcNode； p=G.vertices[i].firstarc； /
/p指向i的第一个邻接顶点while (p != NULL) {int j = p->adjvex;//j为邻接顶点的序号int e = ve[i];//计算活动<vi,vj>的最早开始时间int l = vl[j] - p->weight;//计算活动<vi,vj>的最迟开始时间if (e == l)cout << G.vertices[i].data << G.vertices[j].data << endl;p = p->nextarc;//p指向i的下一个邻接顶点}}} ③测试的全部代码由于笔者之前的文章已经介绍过图的邻接表及拓扑排序，因此测试代码中此部分未做详细注释，对此部分不熟悉的读者请移步笔者个人主页浏览相关文章，共同学习！！
#include<iostream>#include<string>using namespace std;#define MVNum 100#define OK 1#define ERROR 0#define MaxInt 100typedef string VerTexType;typedef int Status;typedef int SElemType;typedef int OtherInfo;typedef struct{SElemType* base;SElemType* top;int stacksize;}SqStack;typedef struct ArcNode {int adjvex;OtherInfo weight;struct ArcNode* nextarc;}ArcNode;typedef struct VNode {VerTexType data;ArcNode* firstarc;}VNode,AdjList[MVNum];typedef struct {int vexnum, arcnum;AdjList vertices;}ALGraph;/*--------拓扑排序辅助数组的存储结构--------*/int indegree[MVNum];//存放各顶点入度int topo[MVNum];//记录拓扑序列的顶点编号/*-------关键路径算法的两个辅助数组---------*/int ve[MVNum];//事件vi的最早发生时间int vl[MVNum];//事件vi的最迟发生时间Status InitStack(SqStack& S) {S.base = new SElemType[MaxInt];if (!S.base) return ERROR;S.top = S.base;S.stacksize = MaxInt;return OK;}Status StackEmpty(SqStack S) {if (S.top == S.base) return OK;return ERROR;}Status Push(SqStack& S, SElemType e) {if (S.top - S.base == S.stacksize) return ERROR;*S.top = e;S.top++;return OK;}Status Pop(SqStack& S, SElemType& e) {if (S.base == S.top) return ERROR;S.top--;e = *S.top;return OK;}int LocateVex(ALGraph G, VerTexType v) {for (int i = 0; i < G.vexnum; i++) {if (G.vertices[i].data == v)return i;}return -1;}void CreateUDG(ALGraph& G) {cin >> G.vexnum >> G.arcnum;for (int i = 0; i < G.vexnum; i++) {cin >> G.vertices[i].data;G.vertices[i].firstarc = NULL;//初始化表头结点的指针域为NULL}for (int k = 0; k < G.arcnum; k++) {VerTexType v1, v2;int w=0;cin >> v1 >> v2 >> w;int i = LocateVex(G, v1);int j = LocateVex(G, v2);ArcNode* p1 = new ArcNode;p1->adjvex = j;p1->weight = w;p1->nextarc = G.vertices[i].firstarc;G.vertices[i].firstarc = p1;}}void FindInDegree(ALGraph G, int indegree[]) {for (int i = 0; i < G.vexnum; i++) {int cnt = 0;//设置变量存储邻接点域为i的结点个数for (int j = 0; j < G.vexnum; j++) {ArcNode* p = new ArcNode;//定义指向各个边结点的指针p = G.vertices[j].firstarc;while (p) {//当p未指到单个链表的末尾时继续循环if (p->adjvex == i)//当某边结点邻接点域等于i时，计数变量++cnt++;p = p->nextarc;//指针不断向后指}indegree[i] = cnt;//将计数结果保留在indegree数组中}}}/*----------拓扑排序算法---------------*/Status TopologicalSort(ALGraph G, int topo[]) {//有向图G采用邻接表存储结构//若G无回路，则生成G的一个拓扑排序topo[]并返回OK，否则ERRORFindInDegree(G, indegree);//求出各结点的入度存入数组indegree中SqStack S;InitStack(S);//初始化栈for (int i = 0; i < G.vexnum; i++) {if (!indegree[i]) Push(S, i);//入度为0者进栈}int m = 0;//对输出顶点计数u，初始为0while (!StackEmpty(S)) {int i = 0;Pop(S, i);//将栈顶顶点vi出栈topo[m] = i;//将vi保存在拓扑序列数组topo中++m;//对输出顶点计数ArcNode* p = new ArcNode;p = G.vertices[i].firstarc;//p指向vi的第一个邻接点while (p != NULL) {int k = p->adjvex;//vk为vi的邻接点--indegree[k];//vi的每个邻接点的入度减一if (indegree[k] == 0) Push(S, k);//若入度减为0，则入栈p = p->nextarc;//p指向顶点vi下一个邻接结点}}if (m < G.vexnum) return ERROR;//该有向图有回路else return OK;}/*---------关键路径算法---------*/Status CriticalPath(ALGraph& G) {//G为邻接表存储的有向图，输出G的各项关键活动if (!TopologicalSort(G, topo)) return ERROR;//调用拓扑排序算法，使拓扑序列保存在topo中，若调用失败，则存在有向环，返回ERRORint n = G.vexnum;//n为顶点个数for (int i = 0; i < n; i++)//给每个事件的最早发生时间置初值为0ve[i] = 0;/*-------------按拓扑序列求每个事件的最早发生时间---------------*/for (int i = 0; i < n; i++) {int k = topo[i];//取得拓扑序列中的顶点序号kArcNode* p = new ArcNode;p = G.vertices[k].firstarc;//p指向k的第一个邻接顶点while (p != NULL) {int j = p->adjvex;//j为邻接顶点的序号if (ve[j] < ve[k] + p->weight)//更新顶点j的最早发生时间ve[j]ve[j] = ve[k] + p->weight;p = p->nextarc;//p指向k的下一个邻接顶点}}for (int i = 0; i < n; i++)vl[i] = ve[n - 1];//给每个事件的最迟发生时间置初值ve[n-1]/*-----------按拓扑次序求每个事件的最迟发生时间-----------*/for (int i = n - 1; i >= 0; i--) {int k = topo[i];//取得拓扑序列中的顶点序号kArcNode* p = new ArcNode;p = G.vertices[k].firstarc;//p指向k的第一个邻接顶点while (p != NULL) {//根据k的邻接点，更新k的最迟发生时间int j = p->adjvex;//j为邻接顶点的序号if (vl[k] > vl[j] - p->weight)//更新顶点k的最迟发生时间vl[k]vl[k] = vl[j] - p->weight;p = p->nextarc;//p指向k的下一个邻接顶点}}/*-----------判断每一个活动是否为关键活动--------------*/for (int i = 0; i < n; i++) {ArcNode* p = new ArcNode;p = G.vertices[i].firstarc;//p指向i的第一个邻接顶点while (p != NULL) {int j = p->adjvex;//j为邻接顶点的序号int e = ve[i];//计算活动<vi,vj>的最早开始时间int l = vl[j] - p->weight;//计算活动<vi,vj>的最迟开始时间if (e == l)cout << G.vertices[i].data << " " << G.vertices[j].data << endl;p = p->nextarc;//p指向i的下一个邻接顶点}}}int main() {ALGraph G;CreateUDG(G);CriticalPath(G);return 0;} 输入：9 11v0 v1 v2 v3 v4 v5 v6 v7 v8v0 v1 6v0 v2 4v1 v4 1v2 v4 1v4 v6 9v4 v7 7v6 v8 2v7 v8 4v0 v3 5v3 v5 2v5 v7 4输入数据构造的有向无环图：
最终求得的关键路径：
以上为笔者对于关键路径的一些见解，希望初学者都能有所收获，有技术不到位的地方，还望各位大佬指正。
同时，笔者的个人主页还有数据结构中其他部分的一些见解与分析，后续数据结构的相关知识还将陆续更新，欢迎大家访问且共同学习！