Topological Sorting

if the graph G contains an edge (v,w) then the vertex v comes before the vertex w in the ordering.

DFS

Topological sort is a simple but useful adaptation of a DFS.

• call dfs(g) for some graph g
• store the vertices in a list in the decreasing order of visited time(stack)
• return the ordered list as result of topological sort

要track哪些点visit过了

def topological_sort(g):
    visited = {}
    stack = []

    for node in g:
        if node not in visited:
            dfs(node, stack, visited)

    stack.reverse()

    return stack

def dfs(node, stack, visited)
    visited[node] = True
    for n in node.getNeighbors():
        if n not in visited:
            dfs(n, stack, visited)
    stack.append(node)