Topological Sorting拓扑排序

定义：

Topological Sorting is a method of arranging the vertices in a directed acyclic graph (DAG有向无环图) as a sequence, such that for every directed edge(u,v), 即u-> v, vertex u comes before v in the ordering

注意：

A topological ordering is possible if and only if the graph has no directed cycles
Topological orderings are NOT unique

Topological Sorting拓扑排序

应用场景：

build systems: a program cannot be built unless its dependencies are first built
pre-requisite problems: a course cannot be selected unless its pre-requisite courses are taken
dependency problems
task schedule

时间复杂度:

O(V+E)

Topological Sort(){

    1. Call DFS to compute finish time f[v] for each vertex

    2. At each vertex is finished, insert it onto the front of a linked list

    3. Return the linked list of vertices

}

内部原理：

Topological Sorting拓扑排序

比如从任意一个vertex出发（比如，随便选个NodeH），来DFS搜索

Topological Sorting拓扑排序

从NodeH出发，DFS可以走 NodeH-> NodeJ

Topological Sorting拓扑排序

从NodeJ出发， DFS可以 NodeJ -> NodeM

发现NodeM后面没有元素了，我们把NodeM放到Stack里面（基于Stack的FILO特性）

Topological Sorting拓扑排序

从NodeM往回走，到NodeJ，从NodeJ出发，DFS可以NodeJ-> NodeL

发现NodeL后面没有元素了，我们把NodeL放到Stack里面

Topological Sorting拓扑排序

以此类推，DFS走完整个有向无环图，并用Stack保证了u-> v, vertex u comes before v in the ordering

综上，

1. 从有向无环图的任意点出发

2. 进行DFS搜索，直到搜到当前元素已经"nowhere left to go"了

3. 将该元素放到Stack里，并将该元素mark为visited

4. 从该元素backtrack，继续DFS

秒客网

Topological Sorting拓扑排序

相关文章