【大话数据结构C语言】50 关键路径

欢迎关注我的公众号是【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(" length: %d , ", GL->adjList[j].data, GL->adjList[k].data, e->weight );

}

}

}

}

C 语言 数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。