拓扑排序 §

关联数据结构：有向无环图

public class Graph{
 
   // 顶点个数
   private int v;
    
   // 邻接表
   private LinkedList<Integer> adj[];
    
   public Graph(int v) {
       this.v = v;
       adj = new LinkedList[v];
       for(int i = 0; i < v; ++i) {
           adj[i] = new LinkedList<>();
       }
   }
    
   // 顶点s指向顶点t 
   public void addEdge(int s, int t) {
       adj[s].add(t);
   }
}

拓扑排序有两种实现方式：Kahn算法和DFS深度优先搜索算法

Kahn算法 §

Kahn算法使用的是贪心算法的思路。

如果一个顶点的入度为0，即该顶点没有依赖于任何其他顶点，那么就可以先执行该顶点。

Kahn算法不断在图中寻找入度为0的顶点，将其加入到结果序列中，然后将该顶点删除；循环执行上述过程，直至图中所有顶点被删除。

public void topoSortByKahnn() {
    // 统计每个顶点的入度
    int[] inDegree = new int[v];
    for(int i = 0; i < v; ++i) {
        for(int j = 0; j < adj[i].size(); ++j) {
            int w = adj[i].get(j);
            inDegree[w]++;
        }
    }
    
    LinkedList<Integer> queue = new LinkedList<>();
    for(int i = 0; i < v; ++i) {
        if(inDegree[i] == 0) {
            queue.add(i);
        }
    }
    
    while(!queue.isEmpty()) {
        int i = queue.remove();
        System.out.print("->" + i);
        for(int j = 0; j < adj[i].size(); ++j) {
            int k = adj[i].get(j);
            inDegree[k]--;
            if(inDegree[k] == 0) {
                queue.add(k);
            }
        }
    }
    
}

DFS算法 §

f