什么是拓扑排序

2015年7月26日 4点热度 0条评论 来源: u013063153

如果将某一集合中的所有元素作为图的结点,将该集合上的偏序关系作为图的边,则任意一个偏序关系即可以表示一个有向图。

       拓扑排序是有向图的一个重要操作。在给定的有向图G中,若顶点序列v1,v2,..,vn满足下列条件:若在有向图G中从顶点vi到顶点vj有一条路径,则在序列中顶点vi必在vj之前,便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。

       常用的拓扑排序方法如下:
       (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它。

       (2)从图中删去该顶点,并且删去从该顶点发出的所有边。

       (3)重复上述步骤(1)和(2),直到当前有向图中不存在没有前驱结点的顶点为止,或者当前有向图中的所有结点均已输出为止。

    原文作者:u013063153
    原文地址: https://blog.csdn.net/u013063153/article/details/47070989
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。