LintCode 127 [Topological Sortin

原题

给定一个有向图，图节点的拓扑排序被定义为：
对于每条有向边A--> B，则A必须排在B之前　　
拓扑排序的第一个节点可以是任何在图中没有其他节点指向它的节点　　
找到给定图的任一拓扑排序

样例
对于下列图：

这个图的拓扑排序可能是：
[0, 1, 2, 3, 4, 5]
或者
[0, 2, 3, 1, 5, 4]
或者
....

解题思路

• 关于拓扑排序：

• 出度：当前Node指向多少Node

• 入度：有多少Node指向当前的Node，先现实世界，可以把它理解为一个任务依赖于多少其他的任务，比如入度为0则表示完成该任务可立即执行，不依赖与其他的

• 拓扑排序就是不停的找入度为零的Node，把它从图中删除，再把它指向的Node的入度 -1

• 当然，若想要获得每一个Node入度和出度的信息，要首先自己构造。

• 有向图会给出所有的Node，扫面一遍，通过Hash Map记录每一个Node的入度

• 若Node不在Hash Map中，表明其入度为0，先加入到Queue中，然后BFS

• 若最终还有入度不为零的Node存在，表明这是一个不能够拓扑排序的图。图中有环，相互依赖。

完整代码

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

class Solution:
    """
    @param graph: A list of Directed graph node
    @return: A list of integer
    """
    def topSort(self, graph):
        result = []
        visited = {}
        # BFS - calculate the in-degree for each node
        for node in graph:
            for neighbor in node.neighbors:
                if neighbor in visited:
                    visited[neighbor] += 1
                else:
                    visited[neighbor] = 1
                
        q = Queue.Queue()
        # enqueue the node which in-degree == 0
        for node in graph:
            if node not in visited:
                q.put(node)
                result.append(node)
        
        while not q.empty():
            node = q.get()
            for neighbor in node.neighbors:
                visited[neighbor] -= 1
                if visited[neighbor] == 0:
                    q.put(neighbor)
                    result.append(neighbor)
                    
        return result