【答案解析】从数学的角度来讲,拓扑排序就是由任意集合上的一个偏序关系得到一个该集合的全序关系的操作。如果将某一集合中的所有元素作为图的结点,将该集合上的偏序关系作为图的边,则任意一个偏序关系即可以表示一个有向图。
拓扑排序是有向图的一个重要操作。在给定的有向图G中,若顶点序列v1,v2,…,vn满足下列条件:若在有向图G中从顶点vi到顶点Vj有一条路径,则在序列中顶点vi必在顶点vj之前,便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。
一个图的拓扑排序可以看成是图中所有顶点沿水平线排列而成的一个序列,使得所有的有向边均从左指向右。在很多应用中,有向无环图用于说明事件发生的先后次序。
常用的拓扑排序方法如下:
1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它。
2)从图中删去该顶点,并且删去从该顶点发出的所有边。
3)重复上述步骤1)和步骤2),直到当前有向图中不存在没有前驱结点的顶点为止,或者当前有向图中的所有结点均已输出为止。
需要注意的是,一个有向无环图的拓扑排序序列不是唯一的。例如,对于下图而言,进行拓扑排序会得到两个序列:{v1,v2,v5,v4,v3,v7,v6}或者{v1,v2,v5,V4,v7,v3,v6)。