Topological Sorting 08/01

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.

You can assume that there is at least one topological order in the graph.Have you met this question in a real interview? Yes

Clarification

Learn more about representation of graphs

Example

For graph as follow:

picture

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?

BFS:先把所有点的邻居存到map里，map的value就是income edges。然后再循环graph list，map里这时候没有的点，就是要在开始的时候push进queue里的点，然后就是bfs的方法，在while循环里，poll 一个出来，检查他的邻居，每个邻居在map里的value都要-1，然后如果此时这个邻居map里的值是0的话，说明可以加到queue里了，因为没有income edge了

/**
 * 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
        //BFS
        ArrayList<DirectedGraphNode> res = new ArrayList<>();
        HashMap<DirectedGraphNode,Integer> map = new HashMap<>();
        
        for(DirectedGraphNode d : graph){
            for(DirectedGraphNode n : d.neighbors){
                if(!map.containsKey(n)){
                    map.put(n,1);
                }else{
                    map.put(n,map.get(n)+1);
                }
            }
        }
        
        Queue<DirectedGraphNode> queue = new LinkedList<>();
        
        for(DirectedGraphNode d : graph){
            if(!map.containsKey(d)){
                queue.offer(d);
                res.add(d);
            }
        }
        
        while(!queue.isEmpty()){
            DirectedGraphNode node = queue.poll();
            
            for(DirectedGraphNode d : node.neighbors){
                
                map.put(d,map.get(d)-1);
                
                if(map.get(d) == 0){
                    queue.offer(d);
                    res.add(d);
                }
            }
        }
        
        return res;
        
    }
}

DFS: