图的拓扑排序详解与实现 |
您所在的位置：网站首页 › 拓扑排序是什么排序 › 图的拓扑排序详解与实现 |
图的拓扑排序详解与实现
|
文章目录
基本概念有向无环图（DAG）拓扑排序AOV 网
DAG 拓扑排序算法广搜优先搜索实现拓扑排序深度优先搜索非递归实现拓扑排序深度优先搜索递归实现拓扑排序算法介绍算法证明
基本概念
有向无环图（DAG）
如何用有向无环图（DAG，Directed Acyclic Graph） 来表示偏序关系？ 设 R R R 是有穷集合 X X X 上的偏序关系，对 X X X 中每个 v v v，用一个以 v v v 为标号的顶点表示，由此构成顶点集 V V V；对任意 ( u , v ) ∈ R , ( u ≠ v ) ( u , v )∈R,( u ≠ v ) (u,v)∈R,(u=v)（严格偏序或反自反偏序关系），由对应两个顶点建立一条有向边，由此构成边集 E E E, 则 G = ( V , E ) G =( V , E ) G=(V,E) 是有向无环图。 拓扑排序拓扑排序（Topological Sorting）：是由某个集合上的一个偏序关系得到该集合上的一个全序的过程，所得到的线性序列称为拓扑序列（Topological order）。 在图论中，拓扑排序是一个有向无环图的所有顶点的线性序列，且该序列必须满足下面两个条件： 每个顶点出现且只出现一次；若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面； AOV 网AOV 网就是一种有向无环图。 一个较大的工程往往被划分成许多子工程，在整个工程中，有些子工程（活动）必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。 为了形象地反映出整个工程中各个子工程（活动）之间的先后关系，可用一个有向图来表示，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称 AOV 网。 AOV 网中的弧表示活动之间存在的某种制约关系。一个 AOV 网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行。其实 AOV 网就体现了各个子工程之间的一种偏序关系。在 AOV 网中所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列，由AOV网构造拓扑序列的过程叫做拓扑排序。 AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。 DAG 拓扑排序算法课程及课程间的先修关系是偏序关系，可以用 AOV 网（DAG）表示。
利用 AOV 网进行拓扑排序的基本思想: (1) 从 AOV 网中选择一个没有前驱的顶点并且输出它；(2) 从 AOV 网中删去该顶点和所有以该顶点为尾的弧；(3) 重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点； 广搜优先搜索实现拓扑排序算法过程——可以使用广度优先搜索算法（使用队列）： （1）建立入度为零的顶点队列； （2）扫描顶点表，将入度为0的顶点入队（初始化）； （3）while(队列不空) （3.1）输出队头结点；（3.2）记下输出结点的数目；（3.3）删去与之关联的出边；（3.4）若有入度为 0 的结点，入队。（4）若输出结点个数小于 n n n，则输出有环路；否则拓扑排序正常结束。 注意事项： 若图中还有未输出的顶点，但已跳出循环处理，说明图中还剩下一些顶点，它们的入度都大于 0，也就是都有直接前驱，这时网络中必存在有向环。与广度优先搜索的区别： 搜索起点是入度为 0 的顶点；需判断是否有环路，看最后输出的顶点数与图中顶点数是否相同；需删除邻接于 v 的边（引入数组 indegree[ ] 或在顶点表中增加一个属性域 indegree）伪代码如下： void Topologicalsort(AdjGraph G) { QUEUE Q ; count = 0 ; MAKENUlLL(Q) ; for(v=1; v |
【本文地址】
今日新闻 |
推荐新闻 |