本文已参加「新人创作礼」活动， 一起敞开掘金创作之路。

图的应用——要害途径算法

要害途径

假如要对一个流程图取得最短时刻，就必须要剖析它们的拓扑联系，并找到当中最要害的流程，这个流程的时刻便是最短时刻。

在一个表明工程的带权有向图中，用极点表明时刻，用有向边表明活动，用边上的权值表明活动的继续时刻，这种有向图的边表明活动的网，我们称之为AOE网（Activity On Edge Network）。把AOE网中没有入边的极点称之始点或源点，没有出边的极点称为源点或汇点。因为一个工程，总有一个开端，一个结束，所以正常情况下AOE网只要一个源点一个汇点。如图所示。

图的应用——关键路径算法

既然AOE网是表明工程流程的，所以它就具有显着的工程的特性。如有在某极点所代表的事情发生后，从该极点出发的各活动才干开端。只要在进入某极点的各活动都现已结束，该极点所代表的事情才干发生。

虽然AOE网与AOV网都是用来对工程建模的，但它们仍是有很大的不同的，首要体现在AOV网是极点表明活动的网，它只描绘活动之间的制约联系，而AOE网是用边表明活动的网边上的权值表明活动继续的时刻，如下图所示两图的比照。因此，AOE网是要建立在活动之间制约联系没有对立的根底之上，再来剖析完结整个工程至少需要多少时刻，或许为缩短完结工程所需时刻’应当加快哪些活动等问题。

图的应用——关键路径算法

途径上各个活动所继续的时刻之和称为途径长度，从源点到汇点且有最大长度的途径叫要害途径，在要害途径上的活动叫要害活动。在上图中开端→发动机完结→部件会集到位→拼装完结开端 \rightarrow 发动机完结 \rightarrow 部件会集到位 \rightarrow 拼装完结便是要害途径，途径好穿那个地为5.5。

1.1 要害途径算法原理

要害途径算法需要定义几个参数：

  • 事情的最早发生时刻etv（earliest time of vertex）：即极点的最早发生时刻。
  • 事情的最晚发生时刻ltv（latest time of vertex）：即极点的最晚发生时刻，也便是每个极点对应的事情最晚需要开端的时刻，超出此时刻会延误整个工期。
  • 活动的最早开工时刻ete（earliest time of edge）：即弧的最早发生时刻。
  • 活动的最晚开工时刻lte（latest time of edge）：即弧的最晚发生时刻，也便是不推迟工期的最晚开工时刻。

由1和2能够求得3和4，再依据ete[k]是否与lte[k]持平来判断极点是否是要害活动。

1.2 要害途径算法

将AOE网转化成邻接表结构如图所示，注意与拓扑排序的不同的当地在于，弧链表增加了weight域，用来存储弧的权值。

图的应用——关键路径算法

只要缩短要害途径上要害活动的时刻才能够削减整个工期长度。

只需要找到所有活动的最早开端时刻和最晚开端时刻，而且比较它们，假如持平就意味着此活动是要害活动，活动间的途径为要害途径。假如不等，则就不是。

要害途径算法的全局变量：

int *etv,*ltv; /* 事情最早发生时刻和最迟发生时刻数组 */
int *stack2;   /* 用于存储拓扑序列的栈 */
int top2;	   /* 用于stack2的指针 */

要害途径算法的改善拓扑序列算法：

/* 拓扑排序 */
Status TopologicalSort(GraphAdjList GL)
{    /* 若GL无回路，则输出拓扑排序序列并回来1，若有回路回来0。 */    
	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) /* 将入度为0的极点入栈 */           
			stack[++top]=i;    
	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) );/* 初始化拓扑序列栈 */
	printf("TopologicalSort:\t");
	while(top!=0)    
	{        
		gettop=stack[top--];        
		printf("%d -> ",GL->adjList[gettop].data);        
		count++;        /* 输出i号极点，并计数 */ 
		stack2[++top2]=gettop;        /* 将弹出的极点序号压入拓扑序列的栈 */
		for(e = GL->adjList[gettop].firstedge; e; e = e->next)        
		{            
			k=e->adjvex;            
			if( !(--GL->adjList[k].in) )        /* 将i号极点的邻接点的入度减1，假如减1后为0，则入栈 */                
				stack[++top]=k; 
			if((etv[gettop] + e->weight)>etv[k])    /* 求各极点事情的最早发生时刻etv值 */                
				etv[k] = etv[gettop] + e->weight;
		}    
	}    
	printf("\n");   
	if(count < GL->numVertexes)        
		return ERROR;    
	else       
		return OK;
}

要害途径核心算法代码：

/* 求要害途径,GL为有向网，输出G的各项要害活动 */
void CriticalPath(GraphAdjList GL) 
{    
	EdgeNode *e;    
	int i,gettop,k,j;    
	int ete,lte;  /* 声明活动最早发生时刻和最迟发生时刻变量 */        
	TopologicalSort(GL);   /* 求拓扑序列，核算数组etv和stack2的值 */ 
	ltv=(int *)malloc(GL->numVertexes*sizeof(int));/* 事情最早发生时刻数组 */   
	for(i=0; i<GL->numVertexes; i++)        
		ltv[i]=etv[GL->numVertexes-1];    /* 初始化 */        
	printf("etv:\t");   
	for(i=0; i<GL->numVertexes; i++)        
		printf("%d -> ",etv[i]);    
	printf("\n"); 
	while(top2!=0)    /* 出栈是求ltv */    
	{        
		gettop=stack2[top2--];        
		for(e = GL->adjList[gettop].firstedge; e; e = e->next)        /* 求各极点事情的最迟发生时刻ltv值 */        
		{            
			k=e->adjvex;            
			if(ltv[k] - e->weight < ltv[gettop])               
				ltv[gettop] = ltv[k] - e->weight;        
		}   
	}    
	printf("ltv:\t");   
	for(i=0; i<GL->numVertexes; i++)        
		printf("%d -> ",ltv[i]);    
	printf("\n"); 
	for(j=0; j<GL->numVertexes; j++)        /* 求ete,lte和要害活动 */        
	{            
		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 \n",GL->adjList[j].data,GL->adjList[k].data,e->weight);
		}        
	}
}