Lintcode 127. 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.

Example

For graph as follow:

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?

算法流程

拓扑排序的算法是典型的宽度优先搜索算法，其大致流程如下：

1. 统计所有点的入度，并初始化拓扑序列为空。
2. 将所有入度为 0 的点，也就是那些没有任何依赖的点，放到宽度优先搜索的队列中
3. 将队列中的点一个一个的释放出来，放到拓扑序列中，每次释放出某个点 A 的时候，就访问 A 的相邻点（所有A指向的点），并把这些点的入度减去 1。
4. 如果发现某个点的入度被减去 1 之后变成了 0，则放入队列中。
5. 直到队列为空时，算法结束，

深度优先搜索的拓扑排序

深度优先搜索也可以做拓扑排序，不过因为不容易理解，也并不推荐作为拓扑排序的主流算法。

Code (Java):

/**
 * 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) {
        // write your code here
        ArrayList<DirectedGraphNode> ans = new ArrayList<>();
        if (graph == null || graph.size() == 0) {
            return ans;
        }
        
        // step 1: get all indegrees for all nodes of the graph
        //
        Map<DirectedGraphNode, Integer> nodeToIndegreeMap = new HashMap<>();
        for (DirectedGraphNode node : graph) {
            if (!nodeToIndegreeMap.containsKey(node)) {
                nodeToIndegreeMap.put(node, 0);
            }
            for (DirectedGraphNode neighbor : node.neighbors) {
                int inDegree = nodeToIndegreeMap.getOrDefault(neighbor, 0);
                inDegree += 1;
                nodeToIndegreeMap.put(neighbor, inDegree);
            }
        }
        
        // step 2: put all node with 0 indegree value to the Queue
        //
        Queue<DirectedGraphNode> queue = new LinkedList<>();
        for (DirectedGraphNode node : nodeToIndegreeMap.keySet()) {
            int indegree = nodeToIndegreeMap.get(node);
            if (indegree == 0) {
                queue.offer(node);
            }
        }
        
        // step 3: get all nodes from the queue, remove all edges from the node
        //
        while (!queue.isEmpty()) {
            DirectedGraphNode curNode = queue.poll();
            ans.add(curNode);
            
            for (DirectedGraphNode neighbor : curNode.neighbors) {
                int indegree = nodeToIndegreeMap.get(neighbor) - 1;
                nodeToIndegreeMap.put(neighbor, indegree);
                if (indegree == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        return ans;
    }
}