Topological Sorting 127

Question

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?

Solution

1) 计算所有点的入度，用HashMap保存。

2) 将入度为0的点加入queue中和result中，将queue中节点出队，将出队节点所有neighbor的入度减少1。

3) 重复2直到所有点都被加入result中。

需要注意的是，如果有对HashMap做删除操作，不能再用原来的迭代器继续迭代，需要从头用新的迭代器进行迭代。

代码如下：

/**
 * 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
        HashMap<DirectedGraphNode, Integer> map = new HashMap<DirectedGraphNode, Integer>();

        //计算并保存每个点的入度
        for(int i = 0; i < graph.size(); i++){
            DirectedGraphNode curt = graph.get(i);
            // if(!map.containsKey(curt)){
            //     map.put(curt, 0);
            // }
            ArrayList<DirectedGraphNode> neighborList = curt.neighbors;
            for(int j = 0; j < neighborList.size(); j++){
                DirectedGraphNode neighbor = neighborList.get(j);
                if(!map.containsKey(neighbor)){
                    map.put(neighbor, 1);
                }else{
                    map.put(neighbor, map.get(neighbor) + 1);
                }
            }
        }

        ArrayList<DirectedGraphNode> result = new ArrayList<DirectedGraphNode>();
        Queue<DirectedGraphNode> queue = new LinkedList<DirectedGraphNode>();
        for(DirectedGraphNode n : graph){
            if(!map.containsKey(n)){
                queue.offer(n);
                result.add(n);
            }
        }
        //取入度为0的节点加入queue和result中
        while(!queue.isEmpty()){
            DirectedGraphNode curt = queue.poll();
            for(DirectedGraphNode neighbor : curt.neighbors){
                map.put(neighbor, map.get(neighbor) - 1);
                if(map.get(neighbor) == 0){
                    queue.offer(neighbor);
                    result.add(neighbor);
                }
            }
        }
        return result;
    }
}