拓扑排序

描述：

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

样例：

Topological Sorting.png

拓扑排序后可以是以下任意一种情况:

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

代码实现：

/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 * };
 */
public class Solution {
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */    
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        ArrayList<DirectedGraphNode> result = new ArrayList<DirectedGraphNode>();
        if (graph == null) {
            return result;
        }
        HashMap<DirectedGraphNode, Integer> map = new HashMap<>();
        Queue<DirectedGraphNode> queue = new LinkedList<DirectedGraphNode>();
        // 1.统计入度
        for (DirectedGraphNode node : graph) {
            for (DirectedGraphNode neighbor : node.neighbors) {
                if (map.containsKey(neighbor)) {
                    map.put(neighbor, map.get(neighbor) + 1);
                } else {
                    map.put(neighbor, 1);
                }
            }
        }
        //2.找到入度为0 的节点,加入队列
        for (DirectedGraphNode node : graph) {
            if (!map.containsKey(node)) {
                queue.offer(node);
                result.add(node);
            } 
        }
        //bfs依次将入度最小到最大的点加到队列
        while (!queue.isEmpty()) {
            DirectedGraphNode head = queue.poll();
            for (DirectedGraphNode n : head.neighbors) {
                map.put(n, map.get(n) - 1);
                if (map.get(n) == 0) {
                    result.add(n);
                    queue.offer(n);
                }
            }
        }
         return result;
    }
}