数据结构C++

2023-09-24 16:47| 来源: 网络整理| 查看: 265

数据结构C++——关键路径

文章目录数据结构C++——关键路径一、前言二、关键路径的概念三、关键路径的实现①关键路径的实现原理②关键路径的代码实现③测试的全部代码四、总结

一、前言

理解关键路径需要掌握拓扑排序和邻接表的相关知识，由于此部分笔者在之前的文章中已经介绍过，此处不再过多赘述，对此部分知识还不熟练的读者，欢迎移步此文章，共同学习！：数据结构C++——拓扑排序数据结构C++——图的邻接矩阵和邻接表

二、关键路径的概念

（1）AOE-网:与AOV-网相对应的是AOE-网 , 即以边表示活动的网。AOE-网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。（2）源点和汇点：由于整个工程中只有一个开始点和一个完成点，故在正常的情况（无环）下，网中只有一个入度为零的点，称作源点，也只有一个出度为零的点，称作汇点。（3）关键路径和关键活动：要估算整项工程完成的最短时间，就是要找一条从源点到汇点的带权路径长度最长的路径，称为关键路径。关键路径上的活动叫做关键活动，这些活动是影响工程进度的关键，它们的提前或拖延将使整个工程提前或拖延。

三、关键路径的实现 ①关键路径的实现原理

关键路径算法的实现需要引入两个辅助数组ve[i]和vl[i]，分别用来记录事件vi的最早发生时间和记录事件vi的最迟发生时间。遍历整个topo数组，计算出其中存放的顶点（事件）最早发生时间，按逆拓扑序列求出每个事件的最迟发生时间。求出每个边（活动）的最早开始时间和最晚开始时间，边（活动）最早开始时间和最晚开始时间相等的边（活动）即为关键活动。由关键活动形成的由源点到汇点的每一条路径就是关键路径。

②关键路径的代码实现

关键路径的代码实现

关键路径算法思路： 1：给每个时间的最早发生时间置初值为0 2：取得拓扑序列中的顶点，并遍历该顶点的所有邻接点，更新邻接点（事件）发生的最早时间 3：取得逆拓扑序列中的顶点，遍历该顶点的所有邻接点，更新邻接点（事件）发生的最迟时间 4：遍历顶点表，输出最早发生时间和最迟发生时间相等的某边（活动）所依附的两个顶点输出 /*---------关键路径算法---------*/ Status CriticalPath(ALGraph& G) { //G为邻接表存储的有向图，输出G的各项关键活动 if (!TopologicalSort(G, topo)) return ERROR; //调用拓扑排序算法，使拓扑序列保存在topo中，若调用失败，则存在有向环，返回ERROR int n = G.vexnum;//n为顶点个数 for (int i = 0; i int j = p->adjvex;//j为邻接顶点的序号 if (ve[j] weight)//更新顶点j的最早发生时间ve[j] ve[j] = ve[k] + p->weight; p = p->nextarc;//p指向k的下一个邻接顶点 } } for (int i = 0; i = 0; i--) { int k = topo[i];//取得拓扑序列中的顶点序号k ArcNode* 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 int j = p->adjvex;//j为邻接顶点的序号 int e = ve[i];//计算活动的最早开始时间 int l = vl[j] - p->weight;//计算活动的最迟开始时间 if (e == l) cout 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 cin >> G.vexnum >> G.arcnum; for (int i = 0; i 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 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，否则ERROR FindInDegree(G, indegree);//求出各结点的入度存入数组indegree中 SqStack S; InitStack(S);//初始化栈 for (int i = 0; i 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 int k = topo[i];//取得拓扑序列中的顶点序号k ArcNode* p = new ArcNode; p = G.vertices[k].firstarc;//p指向k的第一个邻接顶点 while (p != NULL) { int j = p->adjvex;//j为邻接顶点的序号 if (ve[j] weight)//更新顶点j的最早发生时间ve[j] ve[j] = ve[k] + p->weight; p = p->nextarc;//p指向k的下一个邻接顶点 } } for (int i = 0; i = 0; i--) { int k = topo[i];//取得拓扑序列中的顶点序号k ArcNode* 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 int j = p->adjvex;//j为邻接顶点的序号 int e = ve[i];//计算活动的最早开始时间 int l = vl[j] - p->weight;//计算活动的最迟开始时间 if (e == l) cout

【本文地址】

数据结构C++

数据结构C++

今日新闻

推荐新闻