詳解Java實現(xiàn)拓撲排序算法
一、介紹
百科上這么定義的:
對一個有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序,是將G中所有頂點排成一個線性序列,使得圖中任意一對頂點u和v,若邊<u,v>∈E(G),則u在線性序列中出現(xiàn)在v之前。通常,這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列,簡稱拓撲序列。簡單的說,由某個集合上的一個偏序得到該集合上的一個全序,這個操作稱之為拓撲排序。
為什么會有拓撲排序?拓撲排序有何作用?
舉個例子,學習java系列的教程
代號 | 科目 | 學前需掌握 |
---|---|---|
A1 | javaSE | |
A2 | html | |
A3 | Jsp | A1,A2 |
A4 | servlet | A1 |
A5 | ssm | A3,A4 |
A6 | springboot | A5 |
就比如學習java系類(部分)從java基礎(chǔ),到jsp/servlet,到ssm,到springboot,springcloud等是個循序漸進
且有依賴的過程。在jsp
學習要首先掌握java基礎(chǔ)
和html
基礎(chǔ)。學習框架要掌握jsp/servlet和jdbc之類才行。那么,這個學習過程即構(gòu)成一個拓撲序列。當然這個序列也不唯一,你可以對不關(guān)聯(lián)的學科隨意選擇順序(比如html和java可以隨便先開始哪一個。)
那上述序列可以簡單表示為:
其中五種均為可以選擇的學習方案,對課程安排可以有參考作用,當然,五個都是拓撲序列。只是選擇的策略不同!
一些其他注意:
DGA:有向無環(huán)圖
AOV網(wǎng):數(shù)據(jù)在頂點 可以理解為面向?qū)ο?br /> AOE網(wǎng):數(shù)據(jù)在邊上,可以理解為面向過程!
而我們通俗一點的說法,就是按照某種規(guī)則
將這個圖的頂點取出來,這些頂點能夠表示什么或者有什么聯(lián)系。
規(guī)則:
- 圖中每個頂點只出現(xiàn)
一次
。 - A在B前面,則不存在B在A前面的路徑。(
不能成環(huán)?。。。?/code>)
- 頂點的順序是保證所有指向它的下個節(jié)點在被指節(jié)點前面!(例如A—>B—>C那么A一定在B前面,B一定在C前面)。所以,這個核心規(guī)則下只要滿足即可,所以拓撲排序序列不一定唯一!
二、拓撲排序算法分析
正常步驟為(方法不一定唯一):
- 從DGA圖中找到一個
沒有前驅(qū)
的頂點輸出。(可以遍歷,也可以用優(yōu)先隊列維護) - 刪除以這個點為起點的邊。(它的指向的邊刪除,為了找到下個沒有前驅(qū)的頂點)
- 重復上述,直到最后一個頂點被輸出。如果還有頂點未被輸出,則說明有環(huán)!
對于上圖的簡單序列,可以簡單描述步驟為:
1:刪除1或2輸出
2:刪除2或3以及對應邊
3:刪除3或者4以及對應邊
4:重復以上規(guī)則步驟
這樣就完成一次拓撲排序,得到一個拓撲序列,但是這個序列并不唯一!從過程中也看到有很多選擇方案
,具體得到結(jié)果看你算法的設(shè)計了。但只要滿足即是拓撲排序序列。
另外觀察 1 2 4 3 6 5 7 9
這個序列滿足我們所說的有關(guān)系的節(jié)點指向的在前面,被指向的在后面。如果完全沒關(guān)系那不一定前后(例如1,2)
三、拓撲排序代碼實現(xiàn)
對于拓撲排序,如何用代碼實現(xiàn)呢?對于拓撲排序,雖然在上面詳細介紹了思路和流程,也很通俗易懂。但是實際上代碼的實現(xiàn)還是很需要斟酌的,如何在空間和時間上能夠得到較好的平衡且取得較好的效率?
首先要考慮存儲
。對于節(jié)點,首先他有聯(lián)通點這么多屬性。遇到稀疏矩陣還是用鄰接表比較好。因為一個節(jié)點的指向節(jié)點較少,用鄰接矩陣較浪費資源
。
另外,如果是1,2,3,4,5,6這樣的序列求拓撲排序,我們可以考慮用數(shù)組,但是如果遇到1,2,88,9999類似數(shù)據(jù),可以考慮用map中轉(zhuǎn)一下。
我們具體的代碼思想為:
- 新建node類,包含節(jié)點數(shù)值和它的指向(這里直接用list集合替代鏈表了)
- 一個數(shù)組包含node(這里默認編號較集中)。初始化,添加每個節(jié)點指向的時候同時被指的節(jié)點入度+1!(A—>C)那么C的入度+1;
- 掃描一遍所有node。將所有入度為0的點加入一個
棧(隊列)
。 - 當棧(隊列)不空的時候,拋出其中任意一個node(棧就是尾,隊就是頭,順序無所謂,上面分析了只要同時入度為零可以隨便選擇順序)。將node輸出,并且
node指向的所有元素入度減一
。如果某個點的入度被減為0,那么就將它加入棧(隊列)。 - 重復上述操作,直到棧為空。
這里主要是利用棧或者隊列儲存入度只為0的節(jié)點,只需要初次掃描表將入度為0的放入棧(隊列)中。
- 這里你或許會問為什么。
- 因為節(jié)點之間是有相關(guān)性的,一個節(jié)點若想入度為零,那么它的父節(jié)點(指向節(jié)點)肯定在它為0前入度為0,拆除關(guān)聯(lián)箭頭。從父節(jié)點角度,它的這次拆除聯(lián)系,可能導致被指向的入讀為0,也可能不為0(還有其他節(jié)點指向兒子)
至于具體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];//儲存節(jié)點 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]++; } }
輸出結(jié)果
2 4 6 1 3 5 7 8
當然,上面說過用棧和隊列都可以!如果使用隊列就會得到1 2 3 4 5 6 7 8
的拓撲序列
以上就是詳解Java實現(xiàn)拓撲排序算法的詳細內(nèi)容,更多關(guān)于Java實現(xiàn)拓撲排序算法的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
Java幸運28系統(tǒng)搭建數(shù)組的使用實例詳解
在本篇文章里小編給大家整理了關(guān)于Java幸運28系統(tǒng)搭建數(shù)組的使用實例內(nèi)容,有需要的朋友們可以參考學習下。2019-09-09jdk17?SpringBoot?JPA集成多數(shù)據(jù)庫的示例詳解
這篇文章主要介紹了jdk17?SpringBoot?JPA集成多數(shù)據(jù)庫的示例代碼,包括配置類、請求攔截器、線程上下文等相關(guān)知識,代碼簡單易懂,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-08-08SpringBoot使用@EnableAutoConfiguration實現(xiàn)自動配置詳解
你有想過SpringBoot為什么能夠自動的幫我們創(chuàng)建一個Bean對象么?或許在我們使用的時候只需要在自己自定義的配置文件中加入@Bean對象就可以,但SpringBoot是如何來創(chuàng)建的呢2022-08-08Spring RedisTemplate 批量獲取值的2種方式小結(jié)
這篇文章主要介紹了Spring RedisTemplate 批量獲取值的2種方式小結(jié),具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-06-06基于SpringBoot整合SSMP案例(開啟日志與分頁查詢條件查詢功能實現(xiàn))
這篇文章主要介紹了基于SpringBoot整合SSMP案例(開啟日志與分頁查詢條件查詢功能實現(xiàn)),本文通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋參考下吧2023-11-11