文章出處：極客時間《數(shù)據(jù)結(jié)構(gòu)和算法之美》-作者：王爭。該系列文章是本人的學(xué)習(xí)筆記。

拓?fù)渑判蚰芙鉀Q的問題

在一個項目中會有很多源代碼文件。編譯器在編譯代碼的時候需要按照依賴關(guān)系，依次編譯每個源文件。例如A.java依賴B.java，那就需要先編譯B.java，再編譯A.java。要想完整編譯整個項目就需要確定一個全局的編譯順序。確定這樣一個全局的編譯順序就用到拓?fù)渑判颉?/p>

拓?fù)渑判蚓褪墙鉀Q有向無環(huán)圖的圖中所有頂點的滿足依賴條件的頂點順序。

解決思路

可以將每個源文件看做一個頂點，源文件和源文件之間的依賴關(guān)系看做一條邊。圖的基本結(jié)構(gòu)如下。

public class Graph {private int v; // 頂點的個數(shù)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<>();}}public void addEdge(int s, int t) { // s先于t，邊s->tadj[s].add(t);} }

排序算法有兩種方式BFS和DFS。

BFS遍歷

BFS遍歷，也稱為Khan算法。在構(gòu)建圖的時候如果A.java依賴B.java，那就從B到A有一條邊：B->A。那入度為0的點就是最先編譯的。 找到入度為0的頂點X，將其輸出到拓?fù)渑判蚪Y(jié)果列表中，然后刪除以X為起點的所有的邊。繼續(xù)查找入度為0的頂點，添加到結(jié)果列表中。

public List<Integer> topSortByKahn(){int[] inDegree = new int[v];for(int i = 0; i< adjacency.length; i++){for(Edge edge : adjacency[i]){inDegree[edge.tid] ++;}}Queue<Integer> queue = new LinkedList<>();for(int i=0;i<inDegree.length;i++){if(inDegree[i] == 0){queue.add(i);}}List<Integer> path = new ArrayList<>();while(! queue.isEmpty()){int node = queue.poll();path.add(node);for(Edge edge : adjacency[node]){inDegree[edge.tid]--;if(inDegree[edge.tid] == 0){queue.offer(edge.tid);}}}return path;}

DFS遍歷

按照深度優(yōu)先搜索的方式，遍歷每個頂點。假如有條路徑是：A->B->C->E、A->D->C。
DFS的時候，如果先走的是第一條要先訪問了C、E才會訪問D->C這條路線。這樣的話，就不能找到C什么時候可以執(zhí)行。所以需要將鄰接矩陣轉(zhuǎn)為逆鄰接矩陣。
E->C->B->A、C->D->A。
說明A先執(zhí)行了才能執(zhí)行B，B、D先執(zhí)行才能執(zhí)行C，C執(zhí)行了才能執(zhí)行 E。這個順序符合要求。

在DFS處理環(huán)節(jié)，把一個頂點所依賴的所有節(jié)點先輸出，再輸出本節(jié)點。

public List<Integer> topSortByDFS(){LinkedList<Integer>[] inverseAdg = new LinkedList[this.v];for(int i = 0; i< adjacency.length; i++){inverseAdg[i] = new LinkedList<>();}for(int i = 0; i< adjacency.length; i++){for(Edge edge : adjacency[i]){inverseAdg[edge.tid].add(edge.sid);}}boolean[] visited = new boolean[v];List<Integer> path = new ArrayList<>();for(int i=0;i<this.v;i++){if(visited[i] == false){dfs(i,inverseAdg,visited,path);}}return path;}private void dfs(int sid, LinkedList<Integer>[] inverseAdg, boolean[] visited,List<Integer> path) {visited[sid] = true;for(int tid : inverseAdg[sid]){if(visited[tid] == false){dfs(tid,inverseAdg,visited,path);}}path.add(sid);}

完整代碼

總結(jié)

以上是生活随笔為你收集整理的拓扑排序两种实现方式的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。