拓扑排序
发布网友
共1个回答
热心网友
通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义： 若集合X上的关系是R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。 设R是集合X上的偏序（Partial Order）,如果对每个x,y属于X必有xRy 或 yRx，则称R是集合X上的全序关系。 注意： ①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。 ②若图中存在有向环，则不可能使顶点满足拓扑次序。 ③一个DAG的拓扑序列通常表示某种方案切实可行。
举例
【例】对学生选课工程图进行拓扑排序, 得到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7 或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 【例】一本书的作者将书本中的各章节学习作为顶点，各章节的先学后修关系作为边，构成一个有向图。按有向图的拓扑次序安排章节，才能保证读者在学习某章节时，其预备知识已在前面的章节里介绍过。 ④一个DAG可能有多个拓扑序列。 【例】对图G9进行拓扑排序，至少可得到如下的两个(实际远不止两个)拓扑序列：C0，C1，C2，C4，C3，C5，C7，C8，C6和C0，C7，C9，C1，C4，C2，C3，C6，C5。 ⑤当有向图中存在有向环时，拓扑序列不存在 【例】下面(a)图中的有向环重排后如(b)所示，有向边<v3，vl>和其它边反向。若有向图被用来表示某项工程实施方案或某项工作计划，则找不到该图的拓扑序列(即含有向环)，就意味着该方案或计划是不可行的。 无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输出当前无前趋(即入度为零)的顶点，其抽象算法可描述为： NonPreFirstTopSort(G){//优先输出无前趋的顶点 while(G中有入度为0的顶点)do{ 从G中选择一个入度为0的顶点v且输出之； 从G中删去v及其所有出边； } if(输出的顶点数目<|V(G)|) //若此条件不成立，则表示所有顶点均已输出，排序成功。 Error("G中存在有向环，排序失败！")； } 对G9执行上述算法的执行过程【参见动画演示】和得到的拓扑序列是C0，C1，C2，C4，C3，C5，C7，C9，C6。 注意： 无前趋的顶点优先的拓扑排序算法在具体存储结构下，为便于考察每个顶点的入度，可保存各顶点当前的入度。为避免每次选入度为0的顶点时扫描整个存储空间，可设一个栈或队列暂存所有入度为零的顶点： 在开始排序前，扫描对应的存储空间，将入度为零的顶点均入栈(队)。以后每次选入度为零的顶点时，只需做出栈(队)操作即可。 拓扑排序是有向图的一个重要操作。在给定的有向图G中，若顶点序列vi1,vi2,...,vin满足下列条件：若在有向图G中从顶点vi到顶点vj有一条路径，则在序列中顶点vi必在顶点vj之前，便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。
实现的基本方法
拓扑排序方法如下: (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它. (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边. (3)重复上述两步,直到剩余的网中不再存在没有前驱的顶点为止.
