一種非大小排序(先後關係排序)—拓撲排序
- 2019 年 10 月 4 日
- 筆記
拓撲排序
在以前很多人可能聽過拓撲排序，但可能認為它太難而不願接觸學習，也不清楚是排啥序的，然而拓撲排序實際很簡單，生活中也很常用，面試筆試也會遇到,所以掌握拓撲排序已是必要的！
目錄
- 介紹
- 拓撲排序演算法分析
- 拓撲排序程式碼實現
介紹
拓撲排序，很多人都可能聽說但是不了解的一種演算法。或許很多人只知道它是圖論的一種排序，至於幹什麼的不清楚。又或許很多人可能還會認為它是一種啥排序。而實質上它是對有向圖的頂點排成一個線性序列。
至於定義，百科上是這麼說的：
對一個有向無環圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊<u,v>∈E(G)，則u在線性序列中出現在v之前。通常，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列，簡稱拓撲序列。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。
為什麼會有拓撲排序？拓撲排序有何作用？
舉個例子，學習java系列的教程
代號 | 科目 | 學前需掌握 |
|---|---|---|
A1 | javaSE | |
A2 | html | |
A3 | Jsp | A1，A2 |
A4 | servlet | A1 |
A5 | ssm | A3,A4 |
A6 | springboot | A5 |
就比如學習java系類(部分)從java基礎，到jsp/servlet，到ssm，到springboot，springcloud等是個循序漸進且有依賴的過程。在jsp學習要首先掌握java基礎和html基礎。學習框架要掌握jsp/servlet和jdbc之類才行。那麼，這個學習過程即構成一個拓撲序列。當然這個序列也不唯一，你可以對不關聯的學科隨意選擇順序(比如html和java可以隨便先開始哪一個。)
那上述序列可以簡單表示為：
其中五種均為可以選擇的學習方案，對課程安排可以有參考作用，當然，五個都是拓撲序列。只是選擇的策略不同！
一些其他注意：
DGA：有向無環圖 AOV網：數據在頂點 可以理解為面向對象 AOE網：數據在邊上，可以理解為面向過程！
而我們通俗一點的說法，就是按照某種規則將這個圖的頂點取出來，這些頂點能夠表示什麼或者有什麼聯繫。
規則：
- 圖中每個頂點只出現
一次。 - A在B前面，則不存在B在A前面的路徑。(
不能成環！！！！) - 頂點的順序是保證所有指向它的下個節點在被指節點前面！(例如A—>B—>C那麼A一定在B前面，B一定在C前面)。所以，這個核心規則下只要滿足即可，所以拓撲排序序列不一定唯一！
拓撲排序演算法分析
正常步驟為(方法不一定唯一)：
- 從DGA圖中找到一個
沒有前驅的頂點輸出。(可以遍歷，也可以用優先隊列維護) - 刪除以這個點為起點的邊。(它的指向的邊刪除，為了找到下個沒有前驅的頂點)
- 重複上述，直到最後一個頂點被輸出。如果還有頂點未被輸出，則說明有環！
對於上圖的簡單序列，可以簡單描述步驟為：
- 1：刪除1或2輸出
- 2：刪除2或3以及對應邊
- 3：刪除3或者4以及對應邊
- 3：重複以上規則步驟
這樣就完成一次拓撲排序，得到一個拓撲序列，但是這個序列並不唯一！從過程中也看到有很多選擇方案，具體得到結果看你演算法的設計了。但只要滿足即是拓撲排序序列。
另外觀察 1 2 4 3 6 5 7 9這個序列滿足我們所說的有關係的節點指向的在前面，被指向的在後面。如果完全沒關係那不一定前後(例如1,2)
拓撲排序程式碼實現
對於拓撲排序，如何用程式碼實現呢？對於拓撲排序，雖然在上面詳細介紹了思路和流程，也很通俗易懂。但是實際上程式碼的實現還是很需要斟酌的，如何在空間和時間上能夠得到較好的平衡且取得較好的效率？
首先要考慮存儲。對於節點，首先他有聯通點這麼多屬性。遇到稀疏矩陣還是用鄰接表比較好。因為一個節點的指向節點較少，用鄰接矩陣較浪費資源。
另外，如果是1，2，3，4，5，6這樣的序列求拓撲排序，我們可以考慮用數組，但是如果遇到1，2，88，9999類似數據，可以考慮用map中轉一下。那麼，
我們具體的程式碼思想為：
- 新建node類，包含節點數值和它的指向(這裡直接用list集合替代鏈表了)
- 一個數組包含node(這裡默認編號較集中)。初始化，添加每個節點指向的時候同時被指的節點入度+1！(A—>C)那麼C的入度+1；
- 掃描一遍所有node。將所有入度為0的點加入一個
棧(隊列)。 - 當棧(隊列)不空的時候，拋出其中任意一個node(棧就是尾，隊就是頭，順序無所謂，上面分析了只要同時入度為零可以隨便選擇順序)。將node輸出，並且
node指向的所有元素入度減一。如果某個點的入度被減為0，那麼就將它加入棧(隊列)。 - 重複上述操作，直到棧為空。
這裡主要是利用棧或者隊列儲存入度只為0的節點，只需要初次掃描表將入度為0的放入棧(隊列)中。
- 這裡你或許會問為什麼。
- 因為節點之間是有相關性的，一個節點若想入度為零，那麼它的父節點(指向節點)肯定在它為0前入度為0，拆除關聯箭頭。從父節點角度，它的這次拆除聯繫，可能導致被指向的入讀為0，也可能不為0(還有其他節點指向兒子)
至於具體demo：
package 圖論; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.List; import java.util.Queue; import java.util.Stack; public class tuopu { static class node { int value; List<Integer> next; public node(int value) { this.value=value; next=new ArrayList<Integer>(); } public void setnext(List<Integer>list) { this.next=list; } } public static void main(String[] args) { // TODO Auto-generated method stub node []nodes=new node[9];//儲存節點 int a[]=new int[9];//儲存入度 List<Integer>list[]=new ArrayList[10];//臨時空間，為了存儲指向的集合 for(int i=1;i<9;i++) { nodes[i]=new node(i); list[i]=new ArrayList<Integer>(); } initmap(nodes,list,a); //主要流程 //Queue<node>q1=new ArrayDeque<node>(); Stack<node>s1=new Stack<node>(); for(int i=1;i<9;i++) { //System.out.print(nodes[i].next.size()+" 55 "); //System.out.println(a[i]); if(a[i]==0) {s1.add(nodes[i]);} } while(!s1.isEmpty()) { node n1=s1.pop();//拋出輸出 System.out.print(n1.value+" "); List<Integer>next=n1.next; for(int i=0;i<next.size();i++) { a[next.get(i)]--;//入度減一 if(a[next.get(i)]==0)//如果入度為0 { s1.add(nodes[next.get(i)]); } } } } private static void initmap(node[] nodes, List<Integer>[] list, int[] a) { list[1].add(3); nodes[1].setnext(list[1]); a[3]++; list[2].add(4);list[2].add(6); nodes[2].setnext(list[2]); a[4]++;a[6]++; list[3].add(5); nodes[3].setnext(list[3]); a[5]++; list[4].add(5);list[4].add(6); nodes[4].setnext(list[4]); a[5]++;a[6]++; list[5].add(7); nodes[5].setnext(list[5]); a[7]++; list[6].add(8); nodes[6].setnext(list[6]); a[8]++; list[7].add(8); nodes[7].setnext(list[7]); a[8]++; } }輸出結果
2 4 6 1 3 5 7 8
當然，上面說過用棧和隊列都可以！如果使用隊列就會得到1 2 3 4 5 6 7 8的拓撲序列
至於圖的構造，因為沒有條件可能效率並不高，演算法也可能不太好，如有優化錯誤還請大佬指正！
文章轉載自公眾號 bigsai ， 作者 bigsai