Topological Sort

题目列表

• alien dictionary
• course schedule

解题方法

DFS + stack的方法

Solution

stack = []
visited = {}

def topSort(graph):
    global stack
    global visited
    for head in graph:
        if head not in visited:
            topSortHelper(head)
    stack.reverse()
    return stack

def topSortHelper(node):
    global visited
    global stack
    visited[node] = True
    for n in node.neighbors:
        if n not in visited:
            topSortHelper(n)
    stack.append(node) # after all neighbor are taken care, push to stack

Reference