Topological Sorting

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.

题意理解，给出任何一个方案的拓扑排序，拓扑排序的本质就是有顺序性，类似于工作流的模式，给定的条件是图的节点集合。

Solution 1:

可以利用每个节点的入度值，首先需要计算出每个节点的入度，开始节点的入度为0， 这样可以想象一把剪刀，每次剪开一条入度，相应的节点入度哈希表的值减1， 当入度为0 的时候证明这个节点完全没有了入度，这样就可以添加进入结果。

# 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 graph nodes in topological order.
    """
    def topSort(self, graph):
        # write your code her
        from collections import deque
        result = []
        map = {}
        q = deque()

        # build a hash table to count the indegrees

        for node in graph:
            for n in node.neighbors:
                if n in map :
                    map[n] += 1
                else:
                    map[n] = 1
        # add the first indegree is 0 to the queue, no indegree is the first node
        for node in graph:
            if node not in map:
                q.append(node)
                result.append(node)
        # if the current indegree is 0 mean it's current node. 
        while len(q) > 0:
            node = q.popleft()
            for n in node.neighbors:
                map[n] -= 1
                if map[n] == 0:
                    result.append(n)
                    q.append(n)

        return result