[[404279]]

前言

大家好，我是bigsai。

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

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

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

什么是拓?fù)渑判?

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

拓?fù)渑判蛴泻巫饔?

拓?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開發(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可以隨便先開始哪一個(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ù)渑判虿⒉灰欢ㄎㄒ?。

算法分析

上面簡(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ù)湫蛄心?

當(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)容講解完畢，謝謝!