【大话数据结构C语言】50 关键路径
【摘要】
欢迎关注我的公众号是【CodeAllen】，关注回复【1024】获取精品学习资源 程序员技术交流①群：736386324 ，程序员技术交流②群：371394777
上一篇的拓扑排序是解决工作是否顺序进行的问题，但是有时候需要解决工程完成需要的最短时间问题
&nb...
欢迎关注我的公众号是【CodeAllen】，关注回复【1024】获取精品学习资源
程序员技术交流①群：736386324 ，程序员技术交流②群：371394777
上一篇的拓扑排序是解决工作是否顺序进行的问题，但是有时候需要解决工程完成需要的最短时间问题
以造车举例子
请问汽车产造一辆汽车，最短需要多少时间呢？其中生产轮子：0.5天，发动机：3天，底盘：2天，外壳：2天，其他零部件：2天，全部零部件集中到一处：0.5天，组装成车并测试：2天
这里边要考虑实际生产是流水线工作，所以这些时间不是简单的相加！
关键路径
-
AOE网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为AOE网（Activity On Edge Network）。
-
我们把AOE网中没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点。
还是画图看下问题
事件2就是时间1完成了，可以进行事件2
AOV网与AOE网的比较
其中的红色为关键路径
现实中情况会更复杂，所以这部分工作就需要找出关键路径
代码实践
几个关键词
1.事件的最早发生时间etv（earliest time of vertex）：即顶点vkvk的最早发生时间
2.事件的最晚发生时间ltv（latest time of vertex）：即顶点vkvk的最晚发生时间，也就是每个顶点对应的事件最晚需要开始时间，超出此时间将会延误整个工期
3.活动的最早开工时间ete（earliest time of edge）：即弧akak的最早发生时间
4.活动的最晚开工时间lte（latest time of edge）：即弧akak的最晚发生时间，也就是不推迟工期的最晚开工时间
按图分析
CriticalPath.c
-
// 边表结点声明
-
typedef struct EdgeNode
-
{
-
int adjvex;
-
struct EdgeNode *next;
-
}EdgeNode;
-
-
// 顶点表结点声明
-
typedef struct VertexNode
-
{
-
int in; // 顶点入度
-
int data;
-
EdgeNode *firstedge;
-
}VertexNode, AdjList[MAXVEX];
-
-
typedef struct
-
{
-
AdjList adjList;
-
int numVertexes, numEdges;
-
}graphAdjList, *GraphAdjList;
-
-
int *etv, *ltv;
-
int *stack2; // 用于存储拓扑序列的栈
-
int top2; // 用于stack2的栈顶指针
-
-
// 拓扑排序算法
-
// 若GL无回路，则输出拓扑排序序列并返回OK，否则返回ERROR
-
Status TopologicalSort(GraphAdjList GL)
-
{
-
EdgeNode *e;
-
int i, k, gettop;
-
int top = 0; // 用于栈指针下标索引
-
int count = 0; // 用于统计输出顶点的个数
-
int *stack; // 用于存储入度为0的顶点
-
-
stack = (int *)malloc(GL->numVertexes * sizeof(int));
-
-
for( i=0; i < GL->numVertexes; i++ )
-
{
-
if( 0 == GL->adjList[i].in )
-
{
-
stack[++top] = i; // 将度为0的顶点下标入栈
-
}
-
}
-
-
// 初始化etv都为0
-
top2 = 0;
-
etv = (int *)malloc(GL->numVertexes*sizeof(int));
-
for( i=0; i < GL->numVertexes; i++ )
-
{
-
etv[i] = 0;
-
}
-
stack2 = (int *)malloc(GL->numVertexes*sizeof(int));
-
-
while( 0 != top )
-
{
-
gettop = stack[top--]; // 出栈
-
// printf("%d -> ", GL->adjList[gettop].data);
-
stack2[++top2] = gettop; // 保存拓扑序列顺序 C1 C2 C3 C4 .... C9
-
count++;
-
-
for( e=GL->adjList[gettop].firstedge; e; e=e->next )
-
{
-
k = e->adjvex;
-
// 注意：下边这个if条件是分析整个程序的要点！
-
// 将k号顶点邻接点的入度-1，因为他的前驱已经消除
-
// 接着判断-1后入度是否为0，如果为0则也入栈
-
if( !(--GL->adjList[k].in) )
-
{
-
stack[++top] = k;
-
}
-
-
if( (etv[gettop]+e->weight) > etv[k] )
-
{
-
etv[k] = etv[gettop] + e->weight;
-
}
-
}
-
}
-
-
if( count < GL->numVertexes ) // 如果count小于顶点数，说明存在环
-
{
-
return ERROR;
-
}
-
else
-
{
-
return OK;
-
}
-
}
-
-
// 求关键路径，GL为有向图，输出GL的各项关键活动
-
void CriticalPath(GraphAdjList GL)
-
{
-
EdgeNode *e;
-
int i, gettop, k, j;
-
int ete, lte;
-
-
// 调用改进后的拓扑排序，求出etv和stack2的值
-
TopologicalSort(GL);
-
-
// 初始化ltv都为汇点的时间
-
ltv = (int *)malloc(GL->numVertexes*sizeof(int));
-
for( i=0; i < GL->numVertexes; i++ )
-
{
-
ltv[i] = etv[GL->numVertexes-1];
-
}
-
-
// 从汇点倒过来逐个计算ltv
-
while( 0 != top2 )
-
{
-
gettop = stack2[top2--]; // 注意，第一个出栈是汇点
-
for( e=GL->adjList[gettop].firstedge; e; e=e->next )
-
{
-
k = e->adjvex;
-
if( (ltv[k] - e->weight) < ltv[gettop] )
-
{
-
ltv[gettop] = ltv[k] - e->weight;
-
}
-
}
-
}
-
-
// 通过etv和ltv求ete和lte
-
for( j=0; j < GL->numVertexes; j++ )
-
{
-
for( e=GL->adjList[j].firstedge; e; e=e->next )
-
{
-
k = e->adjvex;
-
ete = etv[j];
-
lte = ltv[k] - e->weight;
-
-
if( ete == lte )
-
{
-
printf("<v%d,v%d> length: %d , ", GL->adjList[j].data, GL->adjList[k].data, e->weight );
-
}
-
}
-
}
-
}
文章来源: allen5g.blog.csdn.net，作者：CodeAllen的博客，版权归原作者所有，如需转载，请联系作者。
原文链接：allen5g.blog.csdn.net/article/details/116861329
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）