https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
此问题的 DFS 解决方案具有 O(V+E( 时间复杂度。但为什么不只是O(V(呢？是的，我们访问每个顶点和每个边，但每个边都通向另一个顶点，这不是一个额外的步骤。例如，如果我们有 2 个顶点，它们之间有一个边，那么我们访问 2 个顶点，周期。我们不访问 3 件事(2 顶点 + 边(。给我一个DAG的例子，其中"V+E"导致更多的访问，而不仅仅是"V">
为了加强我的论点，二叉树上DFS的时间复杂度为O(N(，其中N是节点数。没有人说它是O(N+E(。
考虑一个具有 V 顶点的有向图，分为两组大小为V/2，从组 #1 中的每个顶点到组 #2 中的每个顶点都有一个边。然后是V2/4 边缘，您需要检查所有边缘。