|
拓扑排序(Topological Sort) 对一个 有向无环图 (Directed Acyclic Graph简称 DAG )G进行拓扑排序是将G中所有顶点排成一个线性序列使得图中任 意一对顶点u和v若 ∈E(G)则u在线性序列中出现在v之前 通常这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列简称 拓扑序列 注意 ①若将图中顶点按拓扑次序排成一行则图中所有的有向边均是从左指向右的 ②若图中存在有向环则不可能使顶点满足拓扑次序 ③一个DAG的拓扑序列通常表示某种方案切实可行 【例】一本书的作者将书本中的各章节学习作为顶点各章节的先学后修关系作为边构成一个有向图按有向图的拓扑次序安 排章节才能保证读者在学习某章节时其预备知识已在前面的章节里介绍过 ④一个DAG可能有多个拓扑序列 【例】对图G 进行拓扑排序至少可得到如下的两个(实际远不止两个)拓扑序列C C C C C C C C C 和C C C C C C C C C ⑤当有向图中存在有向环时拓扑序列不存在 【例】下面(a)图中的有向环重排后如(b)所示有向边和其它边反向若有向图被用来表示某项工程实施方案或某项 工作计划则找不到该图的拓扑序列(即含有向环)就意味着该方案或计划是不可行的 无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输出当前无前趋(即人度为零)的顶点其抽象算法可描述为 NonPreFirstTopSort(G){//优先输出无前趋的顶点 while(G中有人度为的顶点)do{ 从G中选择一个人度为的顶点v且输出之; 从G中删去v及其所有出边; } if(输出的顶点数目<|V(G)|) //若此条件不成立则表示所有顶点均已输出排序成功 Error(G中存在有向环排序失败!); } 对G执行上述算法的执行过程和得到的拓扑序列是C C C C C C C C C 注意 无前趋的顶点优先的拓扑排序算法在具体存储结构下为便于考察每个顶点的人度可保存各顶点当前的人度为避免每次选入 度为的顶点时扫描整个存储空间可设一个栈或队列暂存所有入度为零的顶点 在开始排序前扫描对应的存储空间将人度为零的顶点均入栈(队)以后每次选人度为零的顶点时只需做出栈(队)操作即可 |
