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拓扑排序