16、数据结构和算法 - 实战:拓扑排序和关键路径

拓扑排序

无环图:一个无环的有向图,简称DAG图。
AOV网:在一个表示工程的有向图中,用顶点表示活动,弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,称之为AOV网。
拓扑序列:设G(V, E)是一个具有n个顶点的有向图,V中的顶点序列V1,V2…Vn满足若从顶点Vi到Vj有一条路径,则在顶点序列中顶点Vi必在顶点Vj之前,则我们称这样的顶点序列为一个拓扑序列。
拓扑排序:对一个有向图构造拓扑序列的过程。

拓扑排序算法

方法和步骤如下:

1、 从AOV网中选择一个没有前驱的顶点(该顶点的入度为0),并且输出;
2、 从网中删去该顶点,并且删除从该顶点发出的全部有向边;
3、 重复上述两步,直到剩余网中不再存在没有前驱顶点为止;

可以用邻接表的数据结构表示
 
表示为邻接表
 
部分代码实现:

//边表结点声明
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;

//拓扑排序算法
//若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的顶点下标入栈
		}
	}
	
	while( 0 != top )
	{
   
     
		gettop = stack[top--];
		printf("%d -> ",GL->adjList[gettop].data);
		count ++;
		
		for( e = GL->adjList[gettop].firstedge; e; e= e->next)
		{
   
     
			k = e->adjvex;
			//下面的if条件是要点
			//将k号顶点邻接点的入度-,因为前驱已经消除
			if(!( -- GL->adjList[k].in))
			{
   
     
				stack[++top] = k;
			}
		}
	}
	
	if(count <GL->numVertexes) // 存在环
	{
   
     
		return ERROR;
	}
	else
	{
   
     
		return OK;
	}

}

关键路径

AOE网:在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动的持续时间,这种有向图的边表示活动的网,我们称为AOE网(Activity On Edge Network).
始点或源点:没有入边的顶点。
终点或汇点:没有出边的顶点。
 
二者的比较(AOE和AOV)
 
表示完成的流程,全部流程
 
(红色部分是一个关键路径),有一些关键活动。

关键路径算法

一些关键词:

  • etv(Earliest Time Of Vertex):时间最早发生时间,就是顶点的最早发生时间
  • ltv(Latest Time of Vertex):时间最晚发生时间,就是每个顶点对应的事件最晚需要开始的时间,如果超出此时间将会延误整个工期。
  • ete(Earliest Time of Edge):活动的最早开工时间,就是弧的最早发生时间
  • lte(Latest Time of Edge):活动的最晚发生时间,就是不推迟工期的最晚开工时间
     
     
    当etv = ltv时,事件的连接就是关键路径。
    实现代码如下:
//边表结点声明
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;

//拓扑排序算法
//若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);
		count ++;
		stack2[top++] = gettop; //保存拓扑序列顺序
		
		for( e = GL->adjList[gettop].firstedge; e; e= e->next)
		{
   
     
			k = e->adjvex;
			//下面的if条件是要点
			//将k号顶点邻接点的入度-,因为前驱已经消除
			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) // 存在环
	{
   
     
		return ERROR;
	}
	else
	{
   
     
		return OK;
	}

}

//求关键路径,GL为有向图,输出GL的各项关键活动
void CriticalPath(GraphAdiList GL)
{
   
     
	EdgeNode *e;
	int i,gettop, k ,j;
	int ete,lte;

	TopologicalSort(GL);
		
	//初始化ltv为汇点的时间
	ltv = (int * )malloc(GL->numVertexes *sizeof(int));
	for( i =0; i< GL->numVertexes ;i ++)
	{
   
     
		ltv[i] = etv[GL->numVertexes - 1];
	}
	
	//从汇点倒过来逐个计算
	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[gettop].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->adhList[k].data, e->weight);
		}
	}
}