图之拓扑排序

拓扑排序

拓扑排序(Topological Order)是指，将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。

通俗的讲就是所有的有向边均从排在前面的元素指向排在后面的元素，从而确定每个顶点的先后顺序。

能进行拓扑排序的前提条件：

1. 有向图
2. 有入度in为0的结点
3. 没有环

模板

1. 从开始节点入手

从入度为0的节点开始

public static List<Node> sortedTopology(Graph graph) {  
   HashMap<Node, Integer> inMap = new HashMap<>();  
   Queue<Node> zeroInQueue = new LinkedList<>();  
   for (Node node : graph.nodes.values()) {  
      inMap.put(node, node.in);  
      if (node.in == 0) {  
         zeroInQueue.add(node);  
      }  
   }  
   
   
   List<Node> result = new ArrayList<>();  
   while (!zeroInQueue.isEmpty()) {  
      Node cur = zeroInQueue.poll();  
      result.add(cur);  
      for (Node next : cur.nexts) {  
         inMap.put(next, inMap.get(next) - 1);  
         if (inMap.get(next) == 0) {  
            zeroInQueue.add(next);  
         }  
      }  
   }  
   return result;  
}

2. DFS从结尾节点

将深度优先收缩的最后一个节点放入列表，最后倒序输出即为排序的结果

public class DFS {

    private boolean[] marked;
    private Stack<Integer> reversePost;

    public DFS(Digraph G){
        this.marked = new boolean[G.V()];
        this.reversePost = new Stack<>();

        for (int v = 0;v<G.V();v++){
            if (!marked[v]){
                dfs(G,v);
            }
        }
    }

 
    private void dfs(Digraph G, int v){
        marked[v] = true;
        for (Integer w : G.adj(v)) {
            if (!marked[w]){
                dfs(G,w);
            }
        }
        reversePost.push(v);
    }

    public Stack<Integer>  reversePost(){
        return reversePost;
    }
}