127.Topological Sorting

1.Description(Medium)

Given an directed graph, a topological order of the graph nodes is defined as follow:

• For each directed edgeA ->Bin 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.

Notice

You can assume that there is at least one topological order in the graph.

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]
...

2.Code

图搜索相关的问题较为常见的解法是用DFS进行求解，分为三步走：

1. 统计各定点的入度——只需统计节点在邻接列表中出现的次数即可知。

2. 遍历图中各节点，找到入度为0的节点。

3. 对入度为0的节点进行递归DFS，将节点加入到最终返回结果中。

拓扑排序除了可用DFS, 还可以用BFS具体方法为：

1. 获得图中各节点的入度。存放在HashMap中，但是map中存放的是入度至少为1的点。

2. BFS首先遍历得到入度为0的点（不止一个，永不存在map中点得到），入队，进行下一次BFS

3. 队列不为空时，弹出队顶元素并对其邻接节点进行BFS，现将其入度-1，如果他的入度变成0，就加入最终结果和队列中，重复此过程直至队列为空。

class DirectedGraphNode {
          int label;
          ArrayList<DirectedGraphNode> neighbors;
          DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
      };
public class Solution_127 {
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */    
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        //Indegree
        HashMap<DirectedGraphNode,Integer> map=new HashMap<>();
        for(DirectedGraphNode node: graph){
            for(DirectedGraphNode element: node.neighbors){
                if(map.containsKey(element)){
                    map.put(element,map.get(element)+1);
                }
                else{
                    map.put(element,1);
                }
            }
        }

        //队列放入度为0的点,但是入度为0的点可能不止一个,入度为0的点不存在map中
        Queue<DirectedGraphNode> queue=new LinkedList<DirectedGraphNode>();
        ArrayList<DirectedGraphNode> result=new ArrayList<DirectedGraphNode>();
        for(DirectedGraphNode node: graph){
            if(!map.containsKey(node)){
                queue.offer(node);
                result.add(node);
            }
        }

        while(!queue.isEmpty()){
            DirectedGraphNode current=queue.poll();
            for(DirectedGraphNode node:current.neighbors){
                map.put(node,map.get(node)-1);
                if(map.get(node)==0){
                    queue.offer(node);
                    result.add(node);
                }
            }
        }
        return result;
    }