大家好，我是bigsai。

拓?fù)渑判颍芏嗳硕伎赡苈?tīng)說(shuō)但是不了解的一種算法。不知者大多會(huì)提出這樣的疑問(wèn)：

這是某種排序算法？這好像是一種圖論算法？圖也能排序？

非線性結(jié)構(gòu)在傳統(tǒng)意義上確實(shí)不太好排序，而拓?fù)渑判蛩菍?duì)有向圖的頂點(diǎn)排成一個(gè)線性序列。并且不一定唯一。

什么是拓?fù)渑判颍?/p>

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

拓?fù)渑判蛴泻巫饔茫?/p>

拓?fù)渑判虻膽?yīng)用其實(shí)還是蠻多的，拓?fù)渑判蛟谝恍┕こ逃卸嗟拦ば驎r(shí)候可以獲取一個(gè)有效的加工順序、還有些游戲里的任務(wù)成就必須滿足一個(gè)符合的拓?fù)渑判虿拍芙怄i下一關(guān)、還有一些項(xiàng)目或者環(huán)境的依賴關(guān)系集……

當(dāng)然上面的例子可能不夠具體，離我們稍微近一點(diǎn)的就是課程學(xué)習(xí)上，比如你學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)之前基本要學(xué)習(xí)C或者C++這門課，因?yàn)閿?shù)據(jù)結(jié)構(gòu)中需要懂和會(huì)用C++的代碼；學(xué)習(xí)操作系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)之前要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)這門課，因?yàn)槔锩嫔婕暗胶芏鄶?shù)據(jù)結(jié)構(gòu)和算法；學(xué)習(xí)Java Web開(kāi)發(fā)前要學(xué)習(xí)JavaSE和HTML這兩門課；不同院校課程安排截然不同但均能很好的連接起來(lái)，就是因?yàn)榘才诺恼n程滿足一個(gè)拓?fù)渑判颉?/p>

拓?fù)渑判蜻€是不能理解？我舉個(gè)更詳細(xì)的例子，學(xué)習(xí)Java系列的教程部分，可能有下面這個(gè)順序：

就比如學(xué)習(xí)Java系類（部分）從Java基礎(chǔ)，到JSP/Servlet，到SSM，到SpringBoot，SpringCloud等是個(gè)循序漸進(jìn)、且有前提依賴的過(guò)程。在JSP學(xué)習(xí)要首先掌握J(rèn)ava基礎(chǔ)和HTML基礎(chǔ)。學(xué)習(xí)框架要掌握J(rèn)SP/Servlet和JDBC之類才行。那么，這個(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ì)課程安排可以有參考作用，這五個(gè)都是上面有向無(wú)環(huán)圖（DAG）的拓?fù)湫蛄校皇切〉倪x擇的策略不同（先學(xué)Java或者先學(xué)HTML不要緊，但是要滿足整個(gè)順序要求），不影響滿足規(guī)則順序！

對(duì)于拓?fù)渑判颍€有一些比較專業(yè)的名詞需要銘記：

DAG：有向無(wú)環(huán)圖

AOV網(wǎng)：數(shù)據(jù)在頂點(diǎn)，頂點(diǎn)表示活動(dòng)，邊表示活動(dòng)的先后關(guān)系，可以理解為一種面向?qū)ο蟆?/p>

AOE網(wǎng)：數(shù)據(jù)在邊上，頂點(diǎn)表示事件，有向邊表示活動(dòng)，邊上的權(quán)值表示該活動(dòng)持續(xù)的時(shí)間，可以理解為面向過(guò)程。

很多人不知道AOE網(wǎng)干啥用的，拓?fù)渑判蚴墙鉀Q一個(gè)工程能否順序進(jìn)行的問(wèn)題，但有時(shí)還需解決工程完成需要的最短時(shí)間。而AOE經(jīng)常使用在求關(guān)鍵路徑中（這里就先不進(jìn)行詳細(xì)介紹內(nèi)容和算法了），圖片來(lái)源https://www.cnblogs.com/svod5306/p/14723338.html）。

我們今天講的拓?fù)渑判蚓褪窃贏OV中找到不破壞圖結(jié)構(gòu)的序列，對(duì)于有向無(wú)環(huán)圖，需要注意一下圖中：若A在B前面，則不存在B在A前面的路徑（不能成環(huán)）。圖中兩個(gè)相鄰節(jié)點(diǎn)在拓?fù)湫蛄兄兄恍枰獫M足前后關(guān)系而不一定需要相鄰（節(jié)點(diǎn)只需滿足相對(duì)的前后關(guān)系，所以拓?fù)渑判虿⒉灰欢ㄎㄒ唬?/p>

算法分析上面簡(jiǎn)單的介紹了拓?fù)渑判颍旅嬖敿?xì)講講拓?fù)渑判虻那蠓ā?/p>

正常步驟為（方法不一定唯一）：

1.從DAG圖中找到一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)輸出。可以遍歷入度為0的節(jié)點(diǎn)，也可以用優(yōu)先隊(duì)列維護(hù)。

2.刪除以這個(gè)點(diǎn)為起點(diǎn)的邊。刪除一條邊，其指向節(jié)點(diǎn)的入度減1，這樣為了找到下個(gè)沒(méi)有前驅(qū)節(jié)點(diǎn)的頂點(diǎn)。

3.重復(fù)上述，直到最后一個(gè)頂點(diǎn)被輸出。如果還有頂點(diǎn)未被輸出，則說(shuō)明有環(huán)！

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

step1：刪除節(jié)點(diǎn)1（或者2）及其指向的邊，將節(jié)點(diǎn)輸出

step2：刪除節(jié)點(diǎn)2（或者3）及其指向的邊，將節(jié)點(diǎn)輸出

step2（這里進(jìn)行兩步）：刪除節(jié)點(diǎn)3（或者4）及其指向的邊，將節(jié)點(diǎn)輸出，緊接著刪除節(jié)點(diǎn)3（或者6）其指向的邊，將節(jié)點(diǎn)輸出。

step3：按照上述規(guī)則重復(fù)進(jìn)行，直到所有節(jié)點(diǎn)都被刪除。

這樣就完成一次拓?fù)渑判蛄鞒蹋玫揭粋€(gè)拓?fù)湫蛄校沁@個(gè)序列并不唯一，從算法執(zhí)行過(guò)程中也看到有很多選擇方案，具體得到結(jié)果看你算法的設(shè)計(jì)了，但只要滿足DAG圖中前后相對(duì)關(guān)系。

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

代碼實(shí)現(xiàn)對(duì)于拓?fù)渑判颍绾斡么a實(shí)現(xiàn)呢？

雖然在上面詳細(xì)介紹了思路和流程，也很通俗易懂，但是實(shí)際上代碼的實(shí)現(xiàn)還是很需要斟酌的，如何在空間和時(shí)間上能夠得到較好的平衡且取得較好的效率？

首先要考慮存儲(chǔ)，對(duì)于節(jié)點(diǎn)，是用鄰接矩陣還是鄰接表存儲(chǔ)呢，通常拓?fù)渑判蛉绻褂镁仃嚧鎯?chǔ)都是比較稀疏的，比較浪費(fèi)內(nèi)存空間，這里還是使用鄰接表來(lái)存儲(chǔ)節(jié)點(diǎn)。

另外，如果圖中節(jié)點(diǎn)是1，2，3，4，5，6這樣的有序編號(hào)，我們可以直接用數(shù)組，但是如果遇到1，2，88，9999類似不連續(xù)跨度很大編號(hào)節(jié)點(diǎn)，也可以考慮用Map存儲(chǔ)映射一下位置。

那么我們具體的代碼思想為：

①新建node類，包含節(jié)點(diǎn)數(shù)值和它的指向節(jié)點(diǎn)集合（這里直接用List集合）

②初始化一個(gè)人node數(shù)組，輸入/枚舉節(jié)點(diǎn)之間關(guān)系，被指向的節(jié)點(diǎn)入度+1！（例如A—》C）那么C的入度+1；

③掃描所有node（這里掃描數(shù)組）。將所有入度為0的點(diǎn)加入一個(gè)容器棧（隊(duì)列）中。

④當(dāng)棧（隊(duì)列）不空的時(shí)候，拋出其中任意一個(gè)node（只要入度為零可以隨便選擇順序）。將node輸出，并且node指向的所有節(jié)點(diǎn)入度減1。如果某個(gè)點(diǎn)的入度被減為0，那么就將它加入棧（隊(duì)列）。

⑤重復(fù)上述操作，直到棧（隊(duì)列）為空。

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

因?yàn)楣?jié)點(diǎn)之間是有相關(guān)性的，一個(gè)節(jié)點(diǎn)若想入度為零，那么它的前驅(qū)節(jié)點(diǎn)點(diǎn)肯定在它前入度為0，拆除關(guān)聯(lián)箭頭將自己入度減1，在一個(gè)有向無(wú)環(huán)圖中總會(huì)有大于等于1個(gè)入度為0的節(jié)點(diǎn)。

在具體實(shí)現(xiàn)上，方式是有多樣的，我的這個(gè)只是一個(gè)簡(jiǎn)單的演示，效率不一定很高，大家參考一下即可。

具體實(shí)現(xiàn)代碼為：

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］;//儲(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>

至于圖的構(gòu)造，因?yàn)闆](méi)有條件可能效率并不高，算法也可能不太完美，如有優(yōu)化錯(cuò)誤還請(qǐng)大佬指正！

拓?fù)渑判蛘噎h(huán)前面說(shuō)到，拓?fù)渑判蛐枰谟邢驘o(wú)環(huán)圖中才能得到一個(gè)拓?fù)湫蛄校侨绻o定一個(gè)有向圖，怎么知道它是否可以形成一個(gè)拓?fù)湫蛄心兀?/p>

當(dāng)然是在拓?fù)渑判蛩惴ㄉ线M(jìn)行改動(dòng)，我們?cè)谶M(jìn)行拓?fù)渑判驎?huì)刪除所有入度為0的節(jié)點(diǎn)，但是如有有環(huán)那么刪除節(jié)點(diǎn)個(gè)數(shù)就小于所有節(jié)點(diǎn)個(gè)數(shù)，在具體實(shí)現(xiàn)上，我們只需要在棧或者隊(duì)列拋出時(shí)候通過(guò)一個(gè)計(jì)數(shù)器統(tǒng)計(jì)數(shù)字即可。

當(dāng)然這個(gè)問(wèn)題力扣207有原題可以看看自己代碼是否能夠ac，問(wèn)題描述：

你這個(gè)學(xué)期必須選修 numCourses 門課程，記為 0 到 numCourses - 1 。

在選修某些課程之前需要一些先修課程。先修課程按數(shù)組 prerequisites 給出，其中 prerequisites［i］ = ［ai， bi］ ，表示如果要學(xué)習(xí)課程 ai 則 必須 先學(xué)習(xí)課程 bi 。

例如，先修課程對(duì) ［0， 1］ 表示：想要學(xué)習(xí)課程 0 ，你需要先完成課程 1 。

請(qǐng)你判斷是否可能完成所有課程的學(xué)習(xí)？如果可以，返回 true ；否則，返回 false 。

分析上面已經(jīng)給出，不過(guò)在具體實(shí)現(xiàn)代碼的時(shí)候比較靈活，不一定非得創(chuàng)建node類，思路上理的清即可。

實(shí)現(xiàn)代碼：

class Solution {

public boolean canFinish（int numCourses， int［］［］ prerequisites） {

int indegree［］=new int［numCourses］;

List《Integer》 next［］=new ArrayList［numCourses］;

for（int i=0;i《numCourses;i++）{

next［i］=new ArrayList（）;

}

for（int i=0;i《prerequisites.length;i++） {

int preid=prerequisites［i］［1］;

int courseid=prerequisites［i］［0］;

indegree［courseid］++;//入度加一

next［preid］.add（courseid）;//next指向

}

Queue《Integer》queue=new ArrayDeque《》（）;

for（int i=0;i《numCourses;i++） {//加入入度為0的節(jié)點(diǎn)

if（indegree［i］==0）{

queue.add（i）;

}

}

int nodeNum=0;//判斷刪除節(jié)點(diǎn)數(shù)量 入度為0刪除 如果刪除所有那么返回true

while （！queue.isEmpty（））

{

nodeNum++;

int nodeId=queue.poll（）;

for（int i=0;i《next［nodeId］.size（）;i++）

{

int nodeIndex=next［nodeId］.get（i）;

indegree［nodeIndex］--;

if（indegree［nodeIndex］==0） {

queue.add（nodeIndex）;

}

}

}

if（nodeNum==numCourses）

return true;

return false;

}

}

好了，到這里拓?fù)渑判騼?nèi)容講解完畢！

責(zé)任編輯：haq