Topological Sort

题目描述

解题方法

用DFS实现，将DFS的code改一下，不要打印出来，而是push到一个stack里， 只有当所有的child都call过topological sort之后，才将现在的node push到stack里。

Solution

stack = []
visited = {}

def topological_sort(graph):
    for head in graph:
        if head not in visited:
            top_sort_helper(head)
    stack.reverse()
    return stack

def top_sort_helper(node):
    visited[node] = true
    for n in node.neighbours:
        if n not in visited:
            top_sort_helper(n)
    stack.append(node)

Reference

• Topological Sort
• Topological Sorting