Topological Sorting

Question

• lintcode: (127) Topological Sorting
• Topological Sorting - GeeksforGeeks

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.

Example For graph as follow:

The topological order can be:

[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
...
Note
You can assume that there is at least one topological order in the graph.

Challenge
Can you do it in both BFS and DFS?

题解1 - DFS and BFS

图搜索相关的问题较为常见的解法是用 DFS，这里结合 BFS 进行求解，分为三步走：

1. 统计各定点的入度——只需统计节点在邻接列表中出现的次数即可知。
2. 遍历图中各节点，找到入度为0的节点。
3. 对入度为0的节点进行递归 DFS，将节点加入到最终返回结果中。

题解2 - BFS

拓扑排序除了可用 DFS 求解外，也可使用 BFS, 具体方法为：

1. 获得图中各节点的入度。
2. BFS 首先遍历求得入度数为0的节点，入队，便于下一次 BFS。
3. 队列不为空时，弹出队顶元素并对其邻接节点进行 BFS，将入度为0的节点加入到最终结果和队列中，重复此过程直至队列为空。

• reference

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

class Solution:
    def dfs(self, i, countrd, ans):
        ans.append(i)
        countrd[i] -= 1
        for j in i.neighbors:
            countrd[j] = countrd[j] - 1
            if countrd[j] == 0:
                self.dfs(j, countrd, ans)
    """
    @param graph: A list of Directed graph node
    @return: A list of integer
    """
    def topSort(self, graph):
        # write your code here
        countrd = {}
        for x in graph:
            countrd[x] = 0

        for i in graph:
            for j in i.neighbors:
                countrd[j] = countrd[j] + 1

        ans = []
        for i in graph:
            if countrd[i] == 0:
                self.dfs(i, countrd, ans)
        return ans

sol=Solution()
A=UndirectedGraphNode('0')
B=UndirectedGraphNode('1')
C=UndirectedGraphNode('2')
D=UndirectedGraphNode('3')
E=UndirectedGraphNode('4')
F=UndirectedGraphNode('5')

A.neighbors=[B,C,D]
B.neighbors=[E]
C.neighbors=[E,F]
D.neighbors=[E,F]
E.neighbors=[]
F.neighbors=[]
graph=[A,B,C,D,E,F]

for i in sol.topSort(graph):
    print i.label