31｜图的应用：如何通过拓扑排序找到合理的先后顺序？
王健伟
你好，我是王健伟。
在我和你分享了两个图的应用，最小生成树和最短路径相关的算法之后，我们来说说拓扑排序。
拓扑排序主要是解决一个工程能否按顺序进行的问题。在正式讲解之前，我们首先来一起认识一下几个基本概念。
拓扑排序基本概念
首先，有向无环图（Directed Acyclic Graph，简称 DAG），这是一种特殊的有向图。如果一个有向图中不存在环，那就叫做有向无环图。
其次，AOV 网（Activity On Vertex Network）。在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程。一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity）。
在有向图中，如果以顶点表示活动，有向边（弧）表示活动之间的先后关系，那么这样的有向图就叫做顶点表示活动的网，简称为 AOV 网。AOV 网就是我们刚刚说的有向无环图。AOV 网的边不设权值，如果存在两个顶点之间的边 <vi,vj>，那就表示活动 i 必然发生在活动 j 之前。你可以理解为活动之间存在制约关系。
最后，拓扑排序。对于一个有向无环图，满足若从顶点 vi 到顶点 vj 有一条路径，则在顶点序列中顶点 vi 必然在顶点 vj 之前，这样的顶点序列称为一个拓扑序列。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
拓扑排序是解决工程顺序进行问题的重要方法，适用于有向无环图，通过构造拓扑序列来确定合理的先后顺序。本文首先介绍了有向无环图和AOV网的概念，以及拓扑排序的关键要点。通过生动的做菜例子，深入浅出地解释了拓扑排序的应用。在实现方法方面，文章提到了从AOV网中选择入度为0的顶点并输出，然后删除相关边的步骤。同时，也指出了当图中存在环时，无法完全输出所有顶点的情况。文章还提供了拓扑排序的实现代码，并讨论了不同存储结构对算法时间复杂度的影响。此外，还介绍了逆拓扑排序算法的实现思路。总之，本文通过实例和代码演示，全面介绍了拓扑排序的概念、应用和实现方法，对于想要了解工程顺序安排的读者具有很高的参考价值。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。
收起评论