数据结构--拓扑排序

秒速五厘米 2022-12-29 04:55 115阅读 0赞

## 数据结构–拓扑排序 ##

> 拓扑排序是图中重要的操作之一,在实际中应用很广泛.再AOV网中,不应该出现有向环路,因为有环意味着某项活动以自己作为先决条件,这样就进入了死循环.因此,对给定的AOV网应该首先判定网中是否存在环\*.**检测的办法就是对有向图进行拓扑排序,拓扑排序是指照有向图给出的次序关系,将图中顶点排成一个线性序列,对于有向图中没有限定次序关系的顶点,则可以人为加上任意的次序关系.由此所得顶点的线性序列称为拓扑有序序列.**\*

## 1.拓扑排序的定义 ##

> 给出有向图**G - ( V , E )**, 对于**V**中顶点的线性序列\*\*(v1,v2,…,vk)\*\*,如果满足如下条件: 若在 **G** 中从顶点 **vi** 到 **vj** 有一条路径,则在序列中顶点 **vi** 必须在顶点 **vj** 之前,称该序列为 **G** 的一个拓扑序列. **构造有向图的拓扑序列的过程称为拓扑排序.**

### ( 1 ) 拓扑排序的注意事项 ###

1.  再AOV 网中,若不存在回路.则所有活动可排成一个线性序列,使得每个活动的所有前驱活动都排在该活动的前面,那么该序列为拓扑序列.
2.  拓扑序列不是唯一的.
3.  对AOV图不一定都有拓扑序列.
4.  从前驱和后继的传递性和反自反性来看,AOV 网中不能出现有向回路(或称有向环).再AOV网中如果出现了有向环,则意味着某项活动应以自己作为先决条件,这不是对的,工程将无法进行.对程序流程而言,将出现死循环.因此,对给定的AOV网,应先判断它是否存在有向环.判断AOV网是否存在有向环的方法是对该AOV网进行拓扑排序,将AOV网中的顶点排列成一个线性有序序列,若该线性序列,若该线性序列中包含AOV 网全部的顶点,则AOV 网中无环,否则,AOV网中存在有向环,该网所代表的工程是不可行的.

### ( 2 )拓扑排序的实际意义 ###

如果按照拓扑序列中的顶点次序进行每一项活动,就能够保证在每一项活动时,他的所有前驱活动均已完成,从而使整个工程顺序执行.

### ( 3 ) 拓扑排序的基本步骤 ###

1.  在AOV网中选一个**入度为0**的顶点 ( *即没有前驱* ) 且输出之.
2.  从AOV网中删除此顶点以及从该顶点发出来的所有有向边;
3.  重复 **1 , 2**两步,知道AOV网中所有的顶点都被输出或网中不存在入度为 0 的顶点.

从拓扑排序步骤可知,若在第三步中,网中所有顶点都被输出,则表明网中无有向环,拓扑排序成功,若按照拓扑排序的顺序开展活动则此工程能顺利完成;若仅输出部分顶点,网中已不存在入度为 0 的顶点,则表明网中有有向环,拓扑排序不成功,则此工程不能顺利完成.

## 2.拓扑排序的实现 ##

*  AOV网一般采用邻接表的存储方式,为了标记某个顶点是否有前驱节点,可以在邻接表的头结点中增加一个记录顶点入度的数据域.

\*\*头结点结构体定义为 : \*\*

typedef struct VexNode{ 
        int innum;         //顶点的入度值
        VexInfo vex;       //顶点的信息
        ArcNode *firstarc; //标记第一个 vi 的邻接节点的指针
    }VexNode VexList[MaxVerNum];

**头结点示意图**

<table> 
 <thead> 
  <tr> 
   <th align="center">innum</th> 
   <th align="center">vex</th> 
   <th align="center">firstarc</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

此外,我们还需要一个栈来保存拓扑排序过程中入度为 0 的顶点.

## 算法: 拓扑排序 ##

void TopologicalOrder(ALGraph G)
    { 
        InitStack(stack);
        int count = 0;
        for( i=0 ;i < G.vexnum ; i++ )
            if(VexList[i].innum==0) Push(stack,i);
        while (!EmptyStack(stack))
        { 
            Pop(stack,i);
            count++;
            for(p=G.vexs[i].firstarc;p!=NULL;p=p->nextarc)
            { 
            	k=p->adjvex;
                VexList[k].innum--;
                if(VexList[k].innum==0) Push(stack,k);
    	    }
        }
        if(count==G.vexnum) printf("拓扑排序失败,网中存在回路 .");
        else printf("拓扑排序成功,网中不存在回路 . ");
    }

*  **通过上面算法的温习,可以看出 , 对 有 n 个顶点 和 e 条边的有向图来说,求个各顶点入度的时间复杂度为 O(e),建立辅助栈的时间复杂度为O(n).当一个图拓扑排序成功时.所有顶点入度减1 的操作进行了e次.因此拓扑排序的时间复杂度为O(e+n).**
 *  **有向无环图可以采用深度优先遍历的方法进行拓扑排序.从图中某一顶点出发进行深度优先遍历时最先退出DFS函数的顶点即为出度为 0 的顶点,它是拓扑序列的最后一个顶点.我们用一个临时数组按照先后顺序保存退出DFS函数的顶点,然后逆向输入该数组得到的就是拓扑有序序列.**