图-拓补排序
2021-09-24 09:23:50 0 举报AI智能生成
拓补排序
作者其他创作
大纲/内容
基础概念
在图论中，拓扑排序（Topological Sorting）是一个有向无环图的所有顶点的线性序列。
且该序列必须满足下面两个条件：
且该序列必须满足下面两个条件：
- 每个顶点出现且只出现一次。
- 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
有向无环图（DAG）才有拓扑排序
0驱顶点：没有前驱的顶点
实现步骤
从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出。
从图中删除该顶点和所有以它为起点的有向边。
重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。
当存在多个0驱顶点 -> 无法获得拓补排序后的线性序列
当不存在0驱顶点 -> 存在环
拓扑排序的应用
拓扑排序通常用来“排序”具有依赖关系的任务。
拓扑排序的实现
0 条评论
下一页
为你推荐
查看更多
