如何去理解 拓扑排序算法

查看Castle的代码,在Castle.Core中内部的数据结构采用图,排序使用的拓扑排序算法:        对于一条有向边(u,v),定义u < v;满足所有这样条件的结点序列称为拓扑序列。拓扑排序就是求一个有向图的拓扑序列的算法。 一个有向图顶点的拓扑序列不是惟一的。并不是任何有向图的顶点都可以排成拓扑序列,有环图是不能排的。 例子:比如排课问题,比如士兵排队问题等。        拓扑排序在实际生活中和算法中都有很大的应用。比如要排一下几门课程的先后次序,我们可以把课程抽象成结点,把什么课是什么课的基础抽象成边,那么该图的一个拓扑序列就是这些课的一个可行的先后次序。各种语言的编译器都用到了拓扑排序。     数学基础:     什么是拓扑排序(Topological Sort)?简单地说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。     回顾离散数学中关于偏序和全序的定义:         若集合X上的关系R是自反的、反对称的和传递的,则称只是集合X上的偏序关系。         设R是集合X上的偏序(Partial Order),如果对每个x,y∈X必有xRy或yRx,则称R是集合X上的全序关系。     直观地看,偏序指集合中仅有部分成员之间可比较,而全序指集合中全体成员之间均可比较。[例如],图7.25所示的两个有向图,图中弧(x,y)表示x≤y,则(a)表示偏序,(b)表示全序。若在(a)的有向图上人为地加一个表示v2≤v3的弧(符号“≤”表示v2领先于v3),则(a)表示的亦为全序,且这个全序称为拓扑有序(Topological Order),而由偏序定义得到拓扑有序的操作便是拓扑排序。

AOV-网及其拓扑有序序列产生的过程 (a)AOV-网;(b)输出v6之后;(c)输出v1之后;(d)输出v4之后;(e)输出v3之后;(f)输出v2之后 [思想]:     一、从有向图中选取一个没有前驱的顶点,并输出之;     二、从有向图中删去此顶点以及所有以它为尾的弧;     重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。没有前驱 -- 入度为零,删除顶点及以它为尾的弧-- 弧头顶点的入度减1。 [人度为零的顶点拓扑排序算法]:

    Status Topological Sort(ALGraph G){
    //有向图G采用邻接表存储结构。
    //若G无回路,则输出G的顶点的1个拓扑序列并返回OK,否则ERROR。
 FindInDegree(G,indegree); //对各顶点求入度indegree[0..vernum-1]
 InitStack(S);
 for(i=0;i<G.vexnum; ++i)
 if(!indegree[i])Push(S,i) //建零入度顶点栈,s入度为0者进栈
 count=0; //对输出顶点计数 
 while (!StackEmpty(S)) {
  Pop(S,i); 
 printf(i,G.vertices[i].data); ++count; //输出i号顶点并计数 
  for(p=G.vertices[i].firstarc;p; p=p—>nextarc) {
  k=p—>adivex; //对i号顶点的每个邻接点的入度减1
   if(!(--indegree[k]))Push(S,k);//若入度减为0,则入栈
  }//for
 }//while
 if(count<G.vexnum) return ERROR; //该有向图有回路
 else return OK;
    }//TopologicalSort

 算法 ,总的时间复杂度为O(n+e)。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏张俊红

数据结构-图

图是不同于前面两种数据结构的另一种新的数据结构,线性表中元素与元素之间是被串起来的,每个数据元素只有一个直接前驱和一个直接后继,是一种一对一的数据结构;在树的结...

3721
来自专栏李家的小酒馆

图论基本知识

图 图的基本概念 图示一个复杂的结构,节点之间的关系可以是任意的,图中的任意两个元素之间都可能相关。 ? 图分为有向图和无向图,无向图为两个节点之间互相可以到达...

2140
来自专栏C语言及其他语言

优秀题解【图的遍历——深度优先搜索】

解题思路: (1)总思路:在图中任意选取一个顶点开始(题目要求编号为0开始),访问该顶点,并把该顶点设置为已访问

902
来自专栏用户画像

5.2.4 邻接多重表

在邻接表中,容易求得顶点和边的各种信息,但在邻接表中求两个顶点之间是否存在边,或需要对边执行删除等操作时,需要分别在两个顶点的边表中遍历,效率较低。

1051
来自专栏码匠的流水账

聊聊hystrix的BucketedCounterStream

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/metric/consumer/BucketedCou...

911
来自专栏码匠的流水账

聊聊storm TridentTopology的构建

storm-core-1.2.2-sources.jar!/org/apache/storm/trident/TridentTopology.java

1903
来自专栏开发与安全

数据结构:两栈共享存储空间

数组有两个端点,两个栈有两个栈底,让一个栈的栈底为数组的始端,即下标为0处,另一个栈为栈的末端,即下标为数组长度 n-1处。这样,如果两个栈增加元素,就是两端点...

2685
来自专栏用户画像

5.3.3 图的遍历与图的连通性

对于无向图来说,如果无向图是连通的,则从任一结点出发,仅需一次遍历就能够访问图中所有顶点;

712
来自专栏数据结构与算法

UOJ #117. 欧拉回路

欧拉回路 有一天一位灵魂画师画了一张图,现在要你找出欧拉回路,即在图中找一个环使得每条边都在环上出现恰好一次。 一共两个子任务: 这张图是无向图。(50分) 这...

3806
来自专栏码匠的流水账

聊聊storm TridentTopology的构建

storm-core-1.2.2-sources.jar!/org/apache/storm/trident/TridentTopology.java

1152

扫码关注云+社区

领取腾讯云代金券