拓扑排序
一,邻接表(无前驱实现)
该方法的每一步总是输出当前无前趋(即入度为零)的顶点
其抽象算法可描述为:
NonPreFirstTopSort(G){//优先输出无前趋的顶点
while(G中有入度为0的顶点)
do{
从G中选择一个入度为0的顶点v且输出之;(栈顶弹出)
从G中删去v及其所有出边;(压栈)
}
if(输出的顶点数目<|V(G)|)
//若此条件不成立,则表示所有顶点均已输出,排序成功。
Error("G中存在有向环,排序失败!");
}
注意:
无前趋的顶点优先的拓扑排序算法在具体存储结构下,为便于考察每个顶点的人度,可保存各顶点当前的人度。为避免每次选入度为0的顶点时扫描整个存储空间,可设一个栈或队列暂存所有入度为零的顶点:
在开始排序前,扫描对应的存储空间,将人度为零的顶点均入栈(队)。以后每次选人度为零的顶点时,只需做出栈(队)操作即可。
二,邻接表(DFS深度优先)
当从某顶点v出发的DFS搜索完成时,v的所有后继必定均已被访问过(想像它们均已被删除),此时的v相当于是无后继的顶点,因此在DFS算法返回之前输出顶点v即可得到 DAG的逆拓扑序列。
其中第一个输出的顶点必是无后继(出度为0)的顶点,它应是拓扑序列的最后一个顶点。若希望得到的不是逆拓扑序列,同样可增加T来保存输出的顶点。若假设T是栈,并在DFSTraverse算法的开始处将T初始化,
利用DFS求拓扑序列的抽象算法可描述为:
void DFSTopSort(G,i,T)
{
//在DisTraverse中调用此算法,i是搜索的出发点,T是栈
int j;
visited[i]=TRUE; //访问i
for(所有i的邻接点j)//即<i,j>∈E(G)
if(!visited[j])
DFSTopSort(G,j,T);
//以上语句完全类似于DFS算法
Push(&T,i); //从i出发的搜索已完成,输出i
}
只要将深度优先遍历算法DFSTraverse中对DFS的调用改为对DFSTopSort的调用,即可求得拓扑序列T。其具体算法不难从上述抽象算法求精后得到。
若G是一个DAG,则用DFS遍历实现的拓扑排序与NonSuccFirstTopSort算法完全类似;但若C中存在有向环,则前者不能正常工作。
综合源码
分享到:
相关推荐
1.4 拓扑排序 1.5 强连通分量 2 最小生成树 2.1 最小生成树的形成 2.2 Kruskal算法和Prim算法 3 单源最短路径 3.1 Bellman-Ford算法 3.2 有向无环图(DAG图)中单源最短路径问题 3.3 Dijkstra算法 3.4 差分约束和...
算法导论实验,有向图,DAG,强连通分量,拓扑排序,负权重图,割点等等
假设给我们一个任意的图,它可能是也可能不是DAG(有向无圈图),推广拓扑排序算法,以使得给定有向图G的输入,它的输出是以下两者之一: (a) 一个拓扑排序,于是确定了G为DAG; 或者 (b) G中的一个圈,于是确定了G...
22.4 拓扑排序 22.5 强连通分量 思考题 本章注记 第23章 最小生成树 23.1 最小生成树的形成 23.2 Kruskal算法和Prim算法 思考题 本章注记 第24章 单源最短路径 24.1 Bellman?Ford算法 ...
·快速排序(第7.1节)中用到的划分方法与期望线性时间顺序统计算法(expected linear-time order-statistic algorithm,第9.2节)有所变化。现在,我们采用了Lomuto提出的方法,并将该方法与指示器随机变量一起使用,...
·快速排序(第7.1节)中用到的划分方法与期望线性时间顺序统计算法(expected linear-time order-statistic algorithm,第9.2节)有所变化。现在,我们采用了Lomuto提出的方法,并将该方法与指示器随机变量一起使用,...
OpenSAL1.1 包含了算法导论中所有数据结构和算法以及其他内容,本资源为该算法库的静态链接库 内容如下(*号表示1.1版本新增内容): 数据结构:一般堆、二项堆、斐波那契堆、红黑树、通用散列(采用全域散列和完全...
引言* 4•# •# #第 2 2 章 圈 的 基 本 算 法22. 1at的 表 示 ⋯ ⋯2 2 . 2广 度 优 先 搜 索深度优先搜索拓扑排序22
分类算法导论 以下是编码面试中的常见主题。 由于理解这些概念需要更多的努力,本教程仅作为介绍。 涵盖的主题包括: 字符串/数组/矩阵 链表 树 堆 图形 排序 动态规划 位操作 组合和排列 数学题 一个算法问题包含三...
图论算法(兼容有向图,无向图)包括:广度和深度优先遍历、确定图是否存在回路、拓扑排序、强连通分支、欧拉环(欧拉路径)、最小生成树(Kruskal、Prim)、单源最短路径(3种)、每对顶点间最短路径(2种)、最大...
OpenSAL1.1 包含了算法导论中所有数据结构和算法以及其他内容,本资源为该算法库的静态链接库 内容如下(*号表示1.1版本新增内容): 数据结构:一般堆、二项堆、斐波那契堆、红黑树、通用散列(采用全域散列和完全...
OpenSAL1.1 包含了算法导论中所有数据结构和算法以及其他内容,本资源为该算法库的动态链接库 内容如下(*号表示1.1版本新增内容): 数据结构:一般堆、二项堆、斐波那契堆、红黑树、通用散列(采用全域散列和完全...
数据结构与一些算法,来自算法导论,数据结构与算法分析-C语言描述,C Primer Plus, 数据结构-python描述,博客 ADT链表(c)-抽象链表实现 geometry(c++)-Andrew's Monotone Chain Algorithm Graph (python)-拓扑...
9.6 其他排序算法 9.6.1 枚举排序 9.6.2 基数排序 9.7 书目评注 习题 第10章 图算法 10.1 定义和表示 10.2 最小生成树:Prim算法 10.3 单源最短路径:Dijkstra算法 10.4 全部顶点对间的最短路径 10.4.1 ...
排序 3.6 分布式控制算法的分类 3.7 分布式算法的复杂性 第4章 互斥和选举算法 4.1 互斥 4.2 非基于令牌的解决方案 4.2.1 Lamport算法的简单扩展 4.2.2 Ricart和Agrawala的第一个算法 4.2.3 Maekawa的算法 ...
排序 3.6 分布式控制算法的分类 3.7 分布式算法的复杂性 第4章 互斥和选举算法 4.1 互斥 4.2 非基于令牌的解决方案 4.2.1 Lamport算法的简单扩展 4.2.2 Ricart和Agrawala的第一个算法 4.2.3 Maekawa的算法 ...