5.4.3拓扑排序

有向无环图：一个有向图中不存在环，则称为有向无环图，简称DAG图。

AOV网：如果用DAG图表示一个工程，其顶点表示活动，用有向边<Vi，Vj>表示活动Vi必须先于活动Vj进行的这样一种关系，则将这种有向图称为顶点表示活动的网络，记为AOV网。在AOV网中，活动Vj是活动Vi的直接后继，这种前驱和后继关系具有传递性，且任何活动Vi不能以它自己作为自己的前驱或后继。

拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序。

①每个顶点出现且只出现一次。

②若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。

或者定义为：

拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中顶点B出现在顶点A的后面。每个DAG图都有一个或多个拓扑排序序列。

对一个DAG图进行拓扑排序的算法：

①从DAG图中选择一个没有前驱的顶点并输出。

②从图中删除该顶点和所有以它为起点的有向边。

③重复①和②直到DAG图为空或当前图中不存在无前驱的顶点为止。而后一种情况则说明有向图中必然存在环。

bool TopoLogicalSort(Graph G){
//如果G存在拓扑序列，返回true;否则返回false，这时G中存在环
	initStack(s);//初始化栈，存储入度为0的顶点
	for(int i=0;i<G.vexnum;i++)
		if(indegree[i]==0)
			push(s,i);//将所有入度为0的顶点进栈
	int count=0;//计数，记录当前已经输出的顶点数
        while(!isEmpty(s)){//栈不为空，则存在入度为0的顶点
             Pop(s,i);//栈顶元素出栈
             print[count++]=i;//输出顶点i<pre name="code" class="cpp">             for(P=G.vertices[i].firstarc;p;p=p->nextarc){
             //将所有i指向的顶点的入度减1，并且将入度为0的顶点压入栈S
                    v=p->adjvext;
                    if(!(--indegree[v]))
                         push(s,v);//入度为0，则入栈
             }//for
      }//while
       if(count<G.vexnum){
             return false;//排序失败，有向图中有回路
       }else{
              return true;//拓扑排序成功
       }
}

由于输出每个顶点的同事还要删除以它为起点的边，故拓扑排序的时间复杂度为O(|V|+|E|)。

①入度为零的顶点即没有前驱活动的，或前驱活动都已经完成的顶点，工程可以从这个顶点所代表的活动开始或继续。

②如果一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但如果各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，再作拓扑排序时，则排序的结果是唯一的。

③由于DAG图中各顶点的地位平等，每个顶点编号是认为的，因此可以按照拓扑排序的结果重新安排顶点的序号，生成的DAG图的新的邻接矩阵存储表示，这种邻接矩阵可以是三角矩阵；但是对于一般的图，如果它的邻接矩阵是三角矩阵，则存在拓扑序列，反之则不一定成立。