algorithm - Tarjan算法和Kahn算法拓扑排序的区别

Question

Tarjan 算法和 Kahn 的拓扑排序算法有什么区别？哪个效率更高？

标签： algorithmtopological-sort

Answer 1

Tarjan 的强连通分量算法，顾名思义，并不是一种拓扑排序算法。它只产生强连接组件的反向拓扑排序。

拓扑排序的常用算法，包括卡恩算法，其复杂度为O(|V|+|E|).