詳解Java實現(xiàn)拓?fù)渑判蛩惴?/h1>
更新時間：2021年06月16日 10:44:54 作者：bigsai
拓?fù)渑判颍芏嗳硕伎赡苈犝f但是不了解的一種算法?；蛟S很多人只知道它是圖論的一種排序，至于干什么的不清楚。又或許很多人可能還會認(rèn)為它是一種啥排序。而實質(zhì)上它是對有向圖的頂點排成一個線性序列
一、介紹
百科上這么定義的：
對一個有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進(jìn)行拓?fù)渑判?，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊<u,v>∈E(G)，則u在線性序列中出現(xiàn)在v之前。通常，這樣的線性序列稱為滿足拓?fù)浯涡?Topological Order)的序列，簡稱拓?fù)湫蛄小：唵蔚恼f，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓?fù)渑判颉?/p>
為什么會有拓?fù)渑判?？拓?fù)渑判蛴泻巫饔茫?/p>
舉個例子，學(xué)習(xí)java系列的教程
代號
科目
學(xué)前需掌握
A1
javaSE
A2
html
A3
Jsp
A1，A2
A4
servlet
A1
A5
ssm
A3,A4
A6
springboot
A5
就比如學(xué)習(xí)java系類(部分)從java基礎(chǔ)，到j(luò)sp/servlet，到ssm，到springboot，springcloud等是個循序漸進(jìn)且有依賴的過程。在jsp學(xué)習(xí)要首先掌握java基礎(chǔ)和html基礎(chǔ)。學(xué)習(xí)框架要掌握jsp/servlet和jdbc之類才行。那么，這個學(xué)習(xí)過程即構(gòu)成一個拓?fù)湫蛄?。?dāng)然這個序列也不唯一，你可以對不關(guān)聯(lián)的學(xué)科隨意選擇順序(比如html和java可以隨便先開始哪一個。)
那上述序列可以簡單表示為：
其中五種均為可以選擇的學(xué)習(xí)方案，對課程安排可以有參考作用，當(dāng)然，五個都是拓?fù)湫蛄?。只是選擇的策略不同！
一些其他注意：
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)！?。?！)
- 頂點的順序是保證所有指向它的下個節(jié)點在被指節(jié)點前面！(例如A—>B—>C那么A一定在B前面，B一定在C前面)。所以，這個核心規(guī)則下只要滿足即可，所以拓?fù)渑判蛐蛄胁灰欢ㄎㄒ唬?/li>
二、拓?fù)渑判蛩惴ǚ治?/h2>
正常步驟為(方法不一定唯一)：
- 從DGA圖中找到一個
沒有前驅(qū)的頂點輸出。(可以遍歷，也可以用優(yōu)先隊列維護)
- 刪除以這個點為起點的邊。(它的指向的邊刪除，為了找到下個沒有前驅(qū)的頂點)
- 重復(fù)上述，直到最后一個頂點被輸出。如果還有頂點未被輸出，則說明有環(huán)！
對于上圖的簡單序列，可以簡單描述步驟為：
1：刪除1或2輸出
2：刪除2或3以及對應(yīng)邊
3：刪除3或者4以及對應(yīng)邊
4：重復(fù)以上規(guī)則步驟
這樣就完成一次拓?fù)渑判?，得到一個拓?fù)湫蛄?，但是這個序列并不唯一！從過程中也看到有很多選擇方案，具體得到結(jié)果看你算法的設(shè)計了。但只要滿足即是拓?fù)渑判蛐蛄小?/p>
另外觀察 1 2 4 3 6 5 7 9這個序列滿足我們所說的有關(guān)系的節(jié)點指向的在前面，被指向的在后面。如果完全沒關(guān)系那不一定前后(例如1,2)
三、拓?fù)渑判虼a實現(xiàn)
對于拓?fù)渑判颍绾斡么a實現(xiàn)呢？對于拓?fù)渑判颍m然在上面詳細(xì)介紹了思路和流程，也很通俗易懂。但是實際上代碼的實現(xiàn)還是很需要斟酌的，如何在空間和時間上能夠得到較好的平衡且取得較好的效率？
首先要考慮存儲。對于節(jié)點，首先他有聯(lián)通點這么多屬性。遇到稀疏矩陣還是用鄰接表比較好。因為一個節(jié)點的指向節(jié)點較少，用鄰接矩陣較浪費資源。
另外，如果是1，2，3，4，5，6這樣的序列求拓?fù)渑判?，我們可以考慮用數(shù)組，但是如果遇到1，2，88，9999類似數(shù)據(jù)，可以考慮用map中轉(zhuǎn)一下。
我們具體的代碼思想為：
- 新建node類，包含節(jié)點數(shù)值和它的指向(這里直接用list集合替代鏈表了)
- 一個數(shù)組包含node(這里默認(rèn)編號較集中)。初始化，添加每個節(jié)點指向的時候同時被指的節(jié)點入度+1！(A—>C)那么C的入度+1；
- 掃描一遍所有node。將所有入度為0的點加入一個
棧(隊列)。
- 當(dāng)棧(隊列)不空的時候，拋出其中任意一個node(棧就是尾，隊就是頭，順序無所謂，上面分析了只要同時入度為零可以隨便選擇順序)。將node輸出，并且
node指向的所有元素入度減一。如果某個點的入度被減為0，那么就將它加入棧(隊列)。
- 重復(fù)上述操作，直到棧為空。
這里主要是利用?；蛘哧犃袃Υ嫒攵戎粸?的節(jié)點，只需要初次掃描表將入度為0的放入棧(隊列)中。
- 這里你或許會問為什么。
- 因為節(jié)點之間是有相關(guān)性的，一個節(jié)點若想入度為零，那么它的父節(jié)點(指向節(jié)點)肯定在它為0前入度為0，拆除關(guān)聯(lián)箭頭。從父節(jié)點角度，它的這次拆除聯(lián)系，可能導(dǎo)致被指向的入讀為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
當(dāng)然，上面說過用棧和隊列都可以！如果使用隊列就會得到1 2 3 4 5 6 7 8 的拓?fù)湫蛄?/p>
以上就是詳解Java實現(xiàn)拓?fù)渑判蛩惴ǖ脑敿?xì)內(nèi)容，更多關(guān)于Java實現(xiàn)拓?fù)渑判蛩惴ǖ馁Y料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
-
Java幸運28系統(tǒng)搭建數(shù)組的使用實例詳解
在本篇文章里小編給大家整理了關(guān)于Java幸運28系統(tǒng)搭建數(shù)組的使用實例內(nèi)容，有需要的朋友們可以參考學(xué)習(xí)下。 2019-09-09
-
這篇文章主要介紹了基于JavaMail API收發(fā)郵件的方法,實例分析了javamail的使用方法與相關(guān)注意事項,非常具有實用價值,需要的朋友可以參考下 2015-07-07
-
jdk17?SpringBoot?JPA集成多數(shù)據(jù)庫的示例詳解
這篇文章主要介紹了jdk17?SpringBoot?JPA集成多數(shù)據(jù)庫的示例代碼，包括配置類、請求攔截器、線程上下文等相關(guān)知識，代碼簡單易懂，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下 2023-08-08
-
這篇文章主要介紹了Java反射技術(shù)詳解及實例解析，反射可以說是Java中最強大的技術(shù)了，它可以做的事情太多太多，很多優(yōu)秀的開源框架都是通過反射完成的。如果對JAVA感興趣來可以學(xué)習(xí)一下 2020-07-07
-
這篇文章主要介紹了Java集合中contains方法的效率對比分析，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教 2021-05-05
-
這篇文章主要介紹了Java日期操作類常見用法,結(jié)合實例形式分析了java針對日期時間的獲取、轉(zhuǎn)換常見操作技巧,需要的朋友可以參考下 2019-07-07
-
SpringBoot使用@EnableAutoConfiguration實現(xiàn)自動配置詳解
你有想過SpringBoot為什么能夠自動的幫我們創(chuàng)建一個Bean對象么？或許在我們使用的時候只需要在自己自定義的配置文件中加入@Bean對象就可以，但SpringBoot是如何來創(chuàng)建的呢 2022-08-08
-
Spring RedisTemplate 批量獲取值的2種方式小結(jié)
這篇文章主要介紹了Spring RedisTemplate 批量獲取值的2種方式小結(jié)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教 2022-06-06
-
基于SpringBoot整合SSMP案例(開啟日志與分頁查詢條件查詢功能實現(xiàn))
這篇文章主要介紹了基于SpringBoot整合SSMP案例(開啟日志與分頁查詢條件查詢功能實現(xiàn)),本文通過實例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋參考下吧 2023-11-11
-
這篇文章主要介紹了Java中的隱式參數(shù)和顯示參數(shù)是什么，另外還有兩個小例子幫助大家理解,需要的朋友可以參考下。 2017-08-08
最新評論
一、介紹
百科上這么定義的：
對一個有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進(jìn)行拓?fù)渑判?，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊<u,v>∈E(G)，則u在線性序列中出現(xiàn)在v之前。通常，這樣的線性序列稱為滿足拓?fù)浯涡?Topological Order)的序列，簡稱拓?fù)湫蛄小：唵蔚恼f，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓?fù)渑判颉?/p>
為什么會有拓?fù)渑判?？拓?fù)渑判蛴泻巫饔茫?/p>
舉個例子，學(xué)習(xí)java系列的教程
| 代號 | 科目 | 學(xué)前需掌握 |
|---|---|---|
| A1 | javaSE | |
| A2 | html | |
| A3 | Jsp | A1，A2 |
| A4 | servlet | A1 |
| A5 | ssm | A3,A4 |
| A6 | springboot | A5 |
就比如學(xué)習(xí)java系類(部分)從java基礎(chǔ)，到j(luò)sp/servlet，到ssm，到springboot，springcloud等是個循序漸進(jìn)且有依賴的過程。在jsp學(xué)習(xí)要首先掌握java基礎(chǔ)和html基礎(chǔ)。學(xué)習(xí)框架要掌握jsp/servlet和jdbc之類才行。那么，這個學(xué)習(xí)過程即構(gòu)成一個拓?fù)湫蛄?。?dāng)然這個序列也不唯一，你可以對不關(guān)聯(lián)的學(xué)科隨意選擇順序(比如html和java可以隨便先開始哪一個。)
那上述序列可以簡單表示為：
其中五種均為可以選擇的學(xué)習(xí)方案，對課程安排可以有參考作用，當(dāng)然，五個都是拓?fù)湫蛄?。只是選擇的策略不同！
一些其他注意：
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)！?。?！) - 頂點的順序是保證所有指向它的下個節(jié)點在被指節(jié)點前面！(例如A—>B—>C那么A一定在B前面，B一定在C前面)。所以，這個核心規(guī)則下只要滿足即可，所以拓?fù)渑判蛐蛄胁灰欢ㄎㄒ唬?/li>
二、拓?fù)渑判蛩惴ǚ治?/h2>
正常步驟為(方法不一定唯一)：
- 從DGA圖中找到一個
沒有前驅(qū)的頂點輸出。(可以遍歷，也可以用優(yōu)先隊列維護) - 刪除以這個點為起點的邊。(它的指向的邊刪除，為了找到下個沒有前驅(qū)的頂點)
- 重復(fù)上述，直到最后一個頂點被輸出。如果還有頂點未被輸出，則說明有環(huán)！
對于上圖的簡單序列，可以簡單描述步驟為：
1：刪除1或2輸出
2：刪除2或3以及對應(yīng)邊
3：刪除3或者4以及對應(yīng)邊
4：重復(fù)以上規(guī)則步驟
這樣就完成一次拓?fù)渑判?，得到一個拓?fù)湫蛄?，但是這個序列并不唯一！從過程中也看到有很多選擇方案，具體得到結(jié)果看你算法的設(shè)計了。但只要滿足即是拓?fù)渑判蛐蛄小?/p>
另外觀察 1 2 4 3 6 5 7 9這個序列滿足我們所說的有關(guān)系的節(jié)點指向的在前面，被指向的在后面。如果完全沒關(guān)系那不一定前后(例如1,2)
三、拓?fù)渑判虼a實現(xiàn)
對于拓?fù)渑判颍绾斡么a實現(xiàn)呢？對于拓?fù)渑判颍m然在上面詳細(xì)介紹了思路和流程，也很通俗易懂。但是實際上代碼的實現(xiàn)還是很需要斟酌的，如何在空間和時間上能夠得到較好的平衡且取得較好的效率？
首先要考慮存儲。對于節(jié)點，首先他有聯(lián)通點這么多屬性。遇到稀疏矩陣還是用鄰接表比較好。因為一個節(jié)點的指向節(jié)點較少，用鄰接矩陣較浪費資源。
另外，如果是1，2，3，4，5，6這樣的序列求拓?fù)渑判?，我們可以考慮用數(shù)組，但是如果遇到1，2，88，9999類似數(shù)據(jù)，可以考慮用map中轉(zhuǎn)一下。
我們具體的代碼思想為：
- 新建node類，包含節(jié)點數(shù)值和它的指向(這里直接用list集合替代鏈表了)
- 一個數(shù)組包含node(這里默認(rèn)編號較集中)。初始化，添加每個節(jié)點指向的時候同時被指的節(jié)點入度+1！(A—>C)那么C的入度+1；
- 掃描一遍所有node。將所有入度為0的點加入一個
棧(隊列)。 - 當(dāng)棧(隊列)不空的時候，拋出其中任意一個node(棧就是尾，隊就是頭，順序無所謂，上面分析了只要同時入度為零可以隨便選擇順序)。將node輸出，并且
node指向的所有元素入度減一。如果某個點的入度被減為0，那么就將它加入棧(隊列)。 - 重復(fù)上述操作，直到棧為空。
這里主要是利用?；蛘哧犃袃Υ嫒攵戎粸?的節(jié)點，只需要初次掃描表將入度為0的放入棧(隊列)中。
- 這里你或許會問為什么。
- 因為節(jié)點之間是有相關(guān)性的，一個節(jié)點若想入度為零，那么它的父節(jié)點(指向節(jié)點)肯定在它為0前入度為0，拆除關(guān)聯(lián)箭頭。從父節(jié)點角度，它的這次拆除聯(lián)系，可能導(dǎo)致被指向的入讀為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
當(dāng)然，上面說過用棧和隊列都可以！如果使用隊列就會得到1 2 3 4 5 6 7 8 的拓?fù)湫蛄?/p>
以上就是詳解Java實現(xiàn)拓?fù)渑判蛩惴ǖ脑敿?xì)內(nèi)容，更多關(guān)于Java實現(xiàn)拓?fù)渑判蛩惴ǖ馁Y料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
-
Java幸運28系統(tǒng)搭建數(shù)組的使用實例詳解
在本篇文章里小編給大家整理了關(guān)于Java幸運28系統(tǒng)搭建數(shù)組的使用實例內(nèi)容，有需要的朋友們可以參考學(xué)習(xí)下。2019-09-09 - 這篇文章主要介紹了基于JavaMail API收發(fā)郵件的方法,實例分析了javamail的使用方法與相關(guān)注意事項,非常具有實用價值,需要的朋友可以參考下2015-07-07
-
jdk17?SpringBoot?JPA集成多數(shù)據(jù)庫的示例詳解
這篇文章主要介紹了jdk17?SpringBoot?JPA集成多數(shù)據(jù)庫的示例代碼，包括配置類、請求攔截器、線程上下文等相關(guān)知識，代碼簡單易懂，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-08-08 - 這篇文章主要介紹了Java反射技術(shù)詳解及實例解析，反射可以說是Java中最強大的技術(shù)了，它可以做的事情太多太多，很多優(yōu)秀的開源框架都是通過反射完成的。如果對JAVA感興趣來可以學(xué)習(xí)一下2020-07-07
- 這篇文章主要介紹了Java集合中contains方法的效率對比分析，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-05-05
- 這篇文章主要介紹了Java日期操作類常見用法,結(jié)合實例形式分析了java針對日期時間的獲取、轉(zhuǎn)換常見操作技巧,需要的朋友可以參考下2019-07-07
-
SpringBoot使用@EnableAutoConfiguration實現(xiàn)自動配置詳解
你有想過SpringBoot為什么能夠自動的幫我們創(chuàng)建一個Bean對象么？或許在我們使用的時候只需要在自己自定義的配置文件中加入@Bean對象就可以，但SpringBoot是如何來創(chuàng)建的呢2022-08-08 -
Spring RedisTemplate 批量獲取值的2種方式小結(jié)
這篇文章主要介紹了Spring RedisTemplate 批量獲取值的2種方式小結(jié)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-06-06 -
基于SpringBoot整合SSMP案例(開啟日志與分頁查詢條件查詢功能實現(xiàn))
這篇文章主要介紹了基于SpringBoot整合SSMP案例(開啟日志與分頁查詢條件查詢功能實現(xiàn)),本文通過實例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋參考下吧2023-11-11 - 這篇文章主要介紹了Java中的隱式參數(shù)和顯示參數(shù)是什么，另外還有兩個小例子幫助大家理解,需要的朋友可以參考下。2017-08-08