詳解Java實(shí)現(xiàn)拓?fù)渑判蛩惴?/h1>

瀏覽：73日期：2022-08-10 14:27:20

目錄一、介紹二、拓?fù)渑判蛩惴ǚ治鋈⑼負(fù)渑判虼a實(shí)現(xiàn)一、介紹

百科上這么定義的：

對(duì)一個(gè)有向無(wú)環(huán)圖(Directed Acyclic Graph簡(jiǎn)稱(chēng)DAG)G進(jìn)行拓?fù)渑判颍菍中所有頂點(diǎn)排成一個(gè)線(xiàn)性序列，使得圖中任意一對(duì)頂點(diǎn)u和v，若邊<u,v>∈E(G)，則u在線(xiàn)性序列中出現(xiàn)在v之前。通常，這樣的線(xiàn)性序列稱(chēng)為滿(mǎn)足拓?fù)浯涡?Topological Order)的序列，簡(jiǎn)稱(chēng)拓?fù)湫蛄小：?jiǎn)單的說(shuō)，由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱(chēng)之為拓?fù)渑判颉?/p>

為什么會(huì)有拓?fù)渑判颍客負(fù)渑判蛴泻巫饔茫?/p>

舉個(gè)例子，學(xué)習(xí)java系列的教程

代號(hào) 科目 學(xué)前需掌握 A1 javaSEA2 htmlA3 Jsp A1，A2 A4 servlet A1 A5 ssm A3,A4 A6 springboot A5

就比如學(xué)習(xí)java系類(lèi)(部分)從java基礎(chǔ)，到j(luò)sp/servlet，到ssm，到springboot，springcloud等是個(gè)循序漸進(jìn)且有依賴(lài)的過(guò)程。在jsp學(xué)習(xí)要首先掌握java基礎(chǔ)和html基礎(chǔ)。學(xué)習(xí)框架要掌握jsp/servlet和jdbc之類(lèi)才行。那么，這個(gè)學(xué)習(xí)過(guò)程即構(gòu)成一個(gè)拓?fù)湫蛄小．?dāng)然這個(gè)序列也不唯一，你可以對(duì)不關(guān)聯(lián)的學(xué)科隨意選擇順序(比如html和java可以隨便先開(kāi)始哪一個(gè)。)

那上述序列可以簡(jiǎn)單表示為：

其中五種均為可以選擇的學(xué)習(xí)方案，對(duì)課程安排可以有參考作用，當(dāng)然，五個(gè)都是拓?fù)湫蛄小Ｖ皇沁x擇的策略不同！

一些其他注意：

DGA：有向無(wú)環(huán)圖AOV網(wǎng)：數(shù)據(jù)在頂點(diǎn) 可以理解為面向?qū)ο驛OE網(wǎng)：數(shù)據(jù)在邊上，可以理解為面向過(guò)程！

而我們通俗一點(diǎn)的說(shuō)法，就是按照某種規(guī)則將這個(gè)圖的頂點(diǎn)取出來(lái)，這些頂點(diǎn)能夠表示什么或者有什么聯(lián)系。

規(guī)則：

圖中每個(gè)頂點(diǎn)只出現(xiàn)一次。 A在B前面，則不存在B在A前面的路徑。(不能成環(huán)！！！！) 頂點(diǎn)的順序是保證所有指向它的下個(gè)節(jié)點(diǎn)在被指節(jié)點(diǎn)前面！(例如A—>B—>C那么A一定在B前面，B一定在C前面)。所以，這個(gè)核心規(guī)則下只要滿(mǎn)足即可，所以拓?fù)渑判蛐蛄胁灰欢ㄎㄒ唬《⑼負(fù)渑判蛩惴ǚ治?p>

正常步驟為(方法不一定唯一)：

從DGA圖中找到一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)輸出。(可以遍歷，也可以用優(yōu)先隊(duì)列維護(hù)) 刪除以這個(gè)點(diǎn)為起點(diǎn)的邊。(它的指向的邊刪除，為了找到下個(gè)沒(méi)有前驅(qū)的頂點(diǎn)) 重復(fù)上述，直到最后一個(gè)頂點(diǎn)被輸出。如果還有頂點(diǎn)未被輸出，則說(shuō)明有環(huán)！

對(duì)于上圖的簡(jiǎn)單序列，可以簡(jiǎn)單描述步驟為：

1：刪除1或2輸出

2：刪除2或3以及對(duì)應(yīng)邊

3：刪除3或者4以及對(duì)應(yīng)邊

4：重復(fù)以上規(guī)則步驟

這樣就完成一次拓?fù)渑判颍玫揭粋€(gè)拓?fù)湫蛄校沁@個(gè)序列并不唯一！從過(guò)程中也看到有很多選擇方案，具體得到結(jié)果看你算法的設(shè)計(jì)了。但只要滿(mǎn)足即是拓?fù)渑判蛐蛄小?/p>

另外觀察 1 2 4 3 6 5 7 9這個(gè)序列滿(mǎn)足我們所說(shuō)的有關(guān)系的節(jié)點(diǎn)指向的在前面，被指向的在后面。如果完全沒(méi)關(guān)系那不一定前后(例如1,2)

三、拓?fù)渑判虼a實(shí)現(xiàn)

對(duì)于拓?fù)渑判颍绾斡么a實(shí)現(xiàn)呢？對(duì)于拓?fù)渑判颍m然在上面詳細(xì)介紹了思路和流程，也很通俗易懂。但是實(shí)際上代碼的實(shí)現(xiàn)還是很需要斟酌的，如何在空間和時(shí)間上能夠得到較好的平衡且取得較好的效率？

首先要考慮存儲(chǔ)。對(duì)于節(jié)點(diǎn)，首先他有聯(lián)通點(diǎn)這么多屬性。遇到稀疏矩陣還是用鄰接表比較好。因?yàn)橐粋€(gè)節(jié)點(diǎn)的指向節(jié)點(diǎn)較少，用鄰接矩陣較浪費(fèi)資源。

另外，如果是1，2，3，4，5，6這樣的序列求拓?fù)渑判颍覀兛梢钥紤]用數(shù)組，但是如果遇到1，2，88，9999類(lèi)似數(shù)據(jù)，可以考慮用map中轉(zhuǎn)一下。

我們具體的代碼思想為：

新建node類(lèi)，包含節(jié)點(diǎn)數(shù)值和它的指向(這里直接用list集合替代鏈表了) 一個(gè)數(shù)組包含node(這里默認(rèn)編號(hào)較集中)。初始化，添加每個(gè)節(jié)點(diǎn)指向的時(shí)候同時(shí)被指的節(jié)點(diǎn)入度+1！(A—>C)那么C的入度+1； 掃描一遍所有node。將所有入度為0的點(diǎn)加入一個(gè)棧(隊(duì)列)。 當(dāng)棧(隊(duì)列)不空的時(shí)候，拋出其中任意一個(gè)node(棧就是尾，隊(duì)就是頭，順序無(wú)所謂，上面分析了只要同時(shí)入度為零可以隨便選擇順序)。將node輸出，并且node指向的所有元素入度減一。如果某個(gè)點(diǎn)的入度被減為0，那么就將它加入棧(隊(duì)列)。 重復(fù)上述操作，直到棧為空。

這里主要是利用棧或者隊(duì)列儲(chǔ)存入度只為0的節(jié)點(diǎn)，只需要初次掃描表將入度為0的放入棧(隊(duì)列)中。

這里你或許會(huì)問(wèn)為什么。 因?yàn)楣?jié)點(diǎn)之間是有相關(guān)性的，一個(gè)節(jié)點(diǎn)若想入度為零，那么它的父節(jié)點(diǎn)(指向節(jié)點(diǎn))肯定在它為0前入度為0，拆除關(guān)聯(lián)箭頭。從父節(jié)點(diǎn)角度，它的這次拆除聯(lián)系，可能導(dǎo)致被指向的入讀為0，也可能不為0(還有其他節(jié)點(diǎn)指向兒子)

至于具體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 stubnode []nodes=new node[9];//儲(chǔ)存節(jié)點(diǎn)int a[]=new int[9];//儲(chǔ)存入度List<Integer>list[]=new ArrayList[10];//臨時(shí)空間，為了存儲(chǔ)指向的集合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

當(dāng)然，上面說(shuō)過(guò)用棧和隊(duì)列都可以！如果使用隊(duì)列就會(huì)得到1 2 3 4 5 6 7 8 的拓?fù)湫蛄?/p>

以上就是詳解Java實(shí)現(xiàn)拓?fù)渑判蛩惴ǖ脑敿?xì)內(nèi)容，更多關(guān)于Java實(shí)現(xiàn)拓?fù)渑判蛩惴ǖ馁Y料請(qǐng)關(guān)注好吧啦網(wǎng)其它相關(guān)文章！

標(biāo)簽： Java

上一條：基于javaMybatis存進(jìn)時(shí)間戳的問(wèn)題下一條：詳解Java實(shí)現(xiàn)分治算法

相關(guān)文章：

1. Python中Anaconda3 安裝gdal庫(kù)的方法2. PHP AOP教程案例3. python用zip壓縮與解壓縮4. python公司內(nèi)項(xiàng)目對(duì)接釘釘審批流程的實(shí)現(xiàn)5. Notepad++如何配置python？配置python操作流程詳解6. Python 簡(jiǎn)介7. Python操作Excel工作簿的示例代碼(*.xlsx)8. JAVA如何轉(zhuǎn)換樹(shù)結(jié)構(gòu)數(shù)據(jù)代碼實(shí)例9. Python importlib模塊重載使用方法詳解10. Python自動(dòng)化之定位方法大殺器xpath