Topological Sorting

Question

Given an directed graph, a topological order of the graph nodes is defined as follow:

For each directed edge A -> B in graph, A must before B in the order list. The first node in the order can be any node in the graph with no nodes direct to it. Find any topological order for the given graph.

For example !image

The topological order can be:

[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
...

Challenge Can you do it in both BFS and DFS?

Thoughts

DFS

DFS遍历 geeksforgeeks dfs

In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.

BFS

Solution

DFS解法

# Definition for a Directed graph node
# class DirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []

class Solution:
    """
    @param graph: A list of Directed graph node
    @return: A list of integer
    """
    def __init__(self):
        self.stack = []
        self.visited = {}

    def topSort(self, graph):
        #directed graph, may not be conn
        for head in graph:
            if head not in self.visited:
                self.topSortHelper(head)
        result = []
        while self.stack:
            node = self.stack.pop()
            result.append(node)
        return result

    def topSortHelper(self, node):
        self.visited[node] = True
        for n in node.neighbors:
            if n not in self.visited:
                self.topSortHelper(n)
        self.stack.append(node)