Directed Acyclic Graph - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

入门链接

数据结构中的图算法,拓扑排序和最短路径,它们是如何解决实际问题的呢 拓扑排序 图的拓扑排序算法 图的拓扑排序-拓扑序列(以王道数据结构课后考研真题为例)

图解

详解

有向无环图 拓扑排序(广度优先遍历) + 深度优先遍历(Java、Python) 拓扑排序-Kahn算法 拓扑排序详解与实现 深入理解拓扑排序(Topological sort) 有向无环图的最短路径 算法 - 最短路径:有向无环图 最短路径树

先序DFS -- 不能求拓扑排序


后序DFS -- O(E + V)

  • 遍历每一条边E和每一个结点V,没有重复

Kahn算法(类似BFS)-- 优先队列法 O(ElogV)

  • 该算法的关键在于需要维护一个入度incoming为0的结点的集合List
  • 要求输出时结点编号小的在前,用优先队列保存所有的结点V(优先队列使用AVL树实现,插入、搜索等操作都是O(logV)
  • 循环以下3步
    1. 优先队列中输出一个结点,将该结点放入List中 O(logV)
    2. 遍历由该结点引出的所有边,从图中移除这些边 O(E)
    3. 对于2移除的每一条边,同时获取该边的另外一个结点,该结点的入度-1 O(logV);若此时该结点的入度为0,那么也将该结点放到List中 O(1)
  • 当优先队列为空之后,检查图中是否还存在任何边,如果存在的话,说明图中至少存在一条环路。不存在的话则返回结果List,此List中的顺序就是对图进行拓扑排序的结果

要点

  • 拓扑顺序Topological Order
    • 输出的所有结点都是线性有序的
    • 每个结点的边都指向前面的结点
    • 找到一个拓扑顺序的最好的算法是DFS
  • 用拓扑排序可以求求出给定源点的最短路径,时间复杂度是O(E + V)
  • 若E为边的数量,V为结点的数量,则时间复杂度是O(E + V),空间复杂度是O(V)