`
wangxiaohigh
  • 浏览: 1459289 次
文章分类
社区版块
存档分类
最新评论

【算法导论】拓扑排序

 
阅读更多

拓扑排序

一,邻接表(无前驱实现)

该方法的每一步总是输出当前无前趋(即入度为零)的顶点

其抽象算法可描述为:
    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中存在有向环,则前者不能正常工作。

综合源码


分享到:
评论

相关推荐

    算法导论 中英文高清版本

    此外,书中也讲解了图论中的核心算法,如最短路径算法(Dijkstra、Floyd-Warshall、Bellman-Ford)、最小生成树(Prim、Kruskal)以及拓扑排序。 在数据结构方面,《算法导论》详尽介绍了数组、链表、栈、队列、堆...

    算法导论第三版答案(完整版)

    2. **图算法**:如最短路径问题(Dijkstra算法、Floyd-Warshall算法)、最小生成树(Prim算法、Kruskal算法)以及拓扑排序等。 3. **动态规划**:解决最优化问题,如背包问题、最长公共子序列、矩阵链乘法等。 4. ...

    算法导论课后习题答案

    5. **第6章:图算法** - 图是表示对象间关系的有力工具,本章涵盖了最短路径、最小生成树、拓扑排序等算法。习题可能需要解决实际的图论问题,如Dijkstra算法、Prim算法或Kruskal算法的应用。 6. **第7章:动态规划...

    算法导论第十九章习题解答

    《算法导论》是计算机科学领域的一本经典著作,它深入浅出地介绍了各种重要的算法,并提供了详尽的分析和实现。第十九章通常聚焦于图算法,因为图在计算机科学中有广泛的应用,如网络路由、社交网络分析、最短路径...

    算法导论章节答案(31~35章)

    1. 深度优先搜索(DFS)和广度优先搜索(BFS):遍历图的两种基本策略,DFS用于查找环和构建拓扑排序,BFS用于找到最短路径。 2. 强连通组件和二分图检测:识别图中的强连通部分以及能否分割为两个互不相交的子集。 ...

    算法导论章节答案(16~20章)

    《算法导论》是计算机科学领域的一本经典教材,涵盖了广泛的算法理论与实践知识。针对16至20章的内容,我们将深入探讨以下几个关键知识点: 第16章:图算法 这一章主要介绍图的基本概念,包括有向图、无向图、树...

    算法导论第九章习题解答

    在这一章中,读者会学习到如最短路径算法(如Dijkstra算法和Floyd-Warshall算法)、最小生成树算法(如Prim算法和Kruskal算法)以及拓扑排序等相关概念。 "算法导论第九章习题解答"提供的是对这一章练习题的解答,...

    算法导论第十七章习题解答

    《算法导论》是计算机科学领域的一本经典著作,它深入浅出地介绍了各种重要的算法,包括排序、搜索、图论、动态规划等。第十七章通常涉及的是图算法,这部分内容在实际编程中有着广泛的应用,比如网络路由、最短路径...

    算法导论讲义\算法导论讲义算法导论讲义\算法导论讲义

    《算法导论》是计算机科学领域的一本经典教材,它深入浅出地介绍了算法的设计、分析和实现。这些讲义来自于MIT(麻省理工学院)的教师,具有极高的学术价值和教学价值,适合计算机科学的学生和专业人士学习。以下是...

    算法导论-算法导论-算法导论

    图算法部分,书中涵盖了图的表示方法、最短路径算法(Dijkstra、Floyd-Warshall、Bellman-Ford)、最小生成树(Prim、Kruskal)以及拓扑排序等。这些内容在网络分析、路由设计和优化问题中广泛应用。 动态规划是...

    算法导论,acm算法

    图算法如最短路径问题(Dijkstra算法、Floyd-Warshall算法)、最小生成树(Prim算法、Kruskal算法)和拓扑排序,广泛应用于网络设计、交通规划等领域。 动态规划是解决多阶段决策问题的强大工具,如背包问题、最长...

    算法导论习题解答

    3. **图算法**:如最短路径算法(Dijkstra算法、Floyd-Warshall算法)、拓扑排序、最小生成树(Prim算法、Kruskal算法)等。这些算法在网络优化、交通规划等领域有实际应用。 4. **动态规划**:用于解决具有重叠子...

    算法导论章节答案(21~25章)

    《算法导论》是计算机科学领域的一本经典教材,涵盖了广泛的算法理论和实践知识。21至25章是该书的重要部分,涉及到许多关键的算法设计和分析方法。以下是对这五章主要内容的详细解释: 第21章:图算法 在这一章中...

    算法导论习题解答 4-4

    首先,第四章往往讨论图算法,如最短路径、最小生成树、拓扑排序等。在图算法中,Dijkstra算法和Floyd-Warshall算法常用于求解单源最短路径问题,而Prim或Kruskal算法则是解决最小生成树问题的常用方法。如果习题4-4...

    算法导论第二十四章习题解答

    本章可能涉及最小生成树(如Prim或Kruskal算法)、最短路径问题(如Dijkstra算法或Floyd-Warshall算法)、拓扑排序、强连通分量等。理解图的性质和如何在图上执行搜索是解决这些问题的关键。 3. **贪心算法**:贪心...

    算法导论上机代码和报告

    在西电的算法导论上机练习中,图论算法可能包括最小生成树(如Prim算法和Kruskal算法)、最短路径算法(如Dijkstra算法和Floyd-Warshall算法)以及拓扑排序等。这些算法广泛应用于网络设计、物流调度等领域。 五、...

    算法导论试卷

    2. **图算法**:图论是算法导论中的重要部分,可能涉及的题目包括最短路径算法(如Dijkstra算法和Floyd-Warshall算法)、最小生成树算法(如Prim算法和Kruskal算法)以及拓扑排序等。 3. **搜索算法**:深度优先...

    算法导论-java

    6. **图论算法**:包括Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法、拓扑排序和Kruskal最小生成树算法。这些算法在Java中可以通过邻接矩阵或邻接表来实现。 7. **数据结构**:算法的高效实现离不开...

    算法导论第四章习题解答

    《算法导论》是计算机科学领域的一本经典教材,它深入浅出地介绍了算法的设计、分析和实现。第四章通常涉及图算法,这是计算机科学中一个至关重要的主题,因为图模型广泛应用于网络、数据结构、操作系统等多个方面。...

    Java 算法导论 电子书

    书中会涵盖Dijkstra最短路径算法、Floyd-Warshall算法以及拓扑排序等。 7. **字符串处理**:Java在处理字符串方面提供了强大的支持,书中会涉及字符串匹配算法,如KMP算法和Boyer-Moore算法,以及DNA序列比对等生物...

Global site tag (gtag.js) - Google Analytics