拓?fù)渑判?#xff08;Topological Sorting）

這篇文章我們來(lái)講一下拓?fù)渑判?#xff0c;這可是一個(gè)很重要也很實(shí)用的算法，面試中常考，工作中常用，無(wú)論是互聯(lián)網(wǎng)公司還是金融公司，考算法的時(shí)候都賊喜歡問(wèn)這個(gè)。
拓?fù)渑判蚱鋵?shí)并不是一個(gè)傳統(tǒng)意義上的排序算法，它是針對(duì)AOV網(wǎng)線(xiàn)性輸出的過(guò)程，所以我們先來(lái)了解一下AOV網(wǎng)是什么東西。

AOV網(wǎng)

拓?fù)渑判蛩惴ㄖ贿m用于A(yíng)OV網(wǎng)，它是一種有向無(wú)環(huán)圖，那么到底什么是AOV網(wǎng)呢？
在日常生活中，一項(xiàng)大工程可以看作是由若干個(gè)小工程組成的，但這些小工程之間必定存在一些先后順序，也就是說(shuō)，有些工程必須在其它一些工程完成之后才能開(kāi)始。我們可以用有向圖來(lái)形象地表示這些工程之間的先后關(guān)系，小工程為頂點(diǎn)，之間的先后關(guān)系為有向邊，繪制成的有向圖就是AOV網(wǎng)。一個(gè)AOV網(wǎng)必定是一個(gè)有向無(wú)環(huán)圖，也就是不應(yīng)該帶有回路，否則就會(huì)出現(xiàn)先后關(guān)系的自相矛盾。
例如，假定一個(gè)計(jì)算機(jī)專(zhuān)業(yè)的學(xué)生必須完成下圖所列出的全部課程。

在這里，每個(gè)課程就代表一個(gè)小工程，學(xué)習(xí)一門(mén)課程就表示進(jìn)行一項(xiàng)工程，學(xué)習(xí)每門(mén)課程的先決條件是學(xué)完它的全部先修課程。如學(xué)習(xí)《高等數(shù)學(xué)》課程則可以隨時(shí)安排，因?yàn)樗腔A(chǔ)課程，沒(méi)有先修課。學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》課程就必須安排在學(xué)完它的兩門(mén)先修課程《離散數(shù)學(xué)》和《算法語(yǔ)言》之后。

若用AOV網(wǎng)來(lái)表示這種課程安排的先后關(guān)系，則如上圖所示。圖中的每個(gè)頂點(diǎn)代表一門(mén)課程，每條有向邊代表起點(diǎn)對(duì)應(yīng)的課程是終點(diǎn)對(duì)應(yīng)課程的先修課。從圖中可以清楚地看出各課程之間的先修和后續(xù)的關(guān)系。如課程C5的先修課為C2，后續(xù)課程為C4和C6。

拓?fù)渑判?/h1>

那么拓?fù)渑判虻降资歉墒裁吹哪?#xff1f;如果我們要安排課表，那么不可能直接把AOV圖給學(xué)生看，而是需要把它排成一個(gè)序列，使得每個(gè)課程的先修課都排在該課程的前面，這個(gè)過(guò)程就稱(chēng)為“拓?fù)渑判颉薄Ｍ負(fù)渑判虻玫降男蛄胁⒉皇俏ㄒ坏?#xff0c;就好像你早上穿衣服可以先穿內(nèi)衣再穿外套，然后再穿褲子，也可以先穿褲子再穿內(nèi)衣，最后再穿外套，只要內(nèi)衣在外套之前穿就行。
拓?fù)渑判虻玫降男蛄锌梢詭椭覀兒侠戆才乓粋€(gè)工程的進(jìn)度，所以，由AOV網(wǎng)構(gòu)造拓?fù)湫蛄芯哂泻芨叩膶?shí)際應(yīng)用價(jià)值。

算法思想

構(gòu)造拓?fù)湫蛄械耐負(fù)渑判蛩惴ㄋ枷牒芎?jiǎn)單：
（1）選擇一個(gè)入度為0的頂點(diǎn)；
（2）從AOV網(wǎng)中刪除此頂點(diǎn)及以此頂點(diǎn)為起點(diǎn)的關(guān)聯(lián)邊；
（3）重復(fù)上述兩步直到不存在入度為0的頂點(diǎn)為止；
（4）若AOV網(wǎng)中還有頂點(diǎn)，則說(shuō)明有向圖存在回路。

算法實(shí)現(xiàn)

class Graph {int V; // 頂點(diǎn)個(gè)數(shù) int* indegree; // 頂點(diǎn)入度 list<int> *adj; // 鄰接表 public:Graph(int v) {this->V = v;this->adj = new list<int>[v];this->indegree = new int[v];for(int i = 0; i < v; i++) {this->indegree[i] = 0;}}~Graph() {delete [] this->adj;delete [] this->indegree;}void addEdge(int v, int w) {this->adj[v].push_back(w);this->indegree[w]++;}vector<int> topologicalSort() {vector<int> res; // 拓?fù)湫蛄?queue<int> que; // 入度為0頂點(diǎn)集合 for(int i = 0; i < this->V; i++) {if (this->indegree[i] == 0) {que.push(i);}}while(!que.empty()) {int front = que.front();que.pop();res.push_back(front);for(int item:this->adj[front]) {if (!(--this->indegree[item])) {que.push(item);}}}return res.size() == this->V ? res : vector<int> ();} };

測(cè)試

int main(){Graph graph(8);graph.addEdge(0,1);graph.addEdge(0,2);graph.addEdge(2,4);graph.addEdge(1,4);graph.addEdge(1,3);graph.addEdge(4,3);graph.addEdge(4,5);graph.addEdge(4,6);graph.addEdge(3,5);graph.addEdge(6,7);graph.addEdge(5,7);graph.addEdge(3,7);for (int item:graph.topologicalSort()) {cout << item << " ";}return 0; }


練習(xí)題

LeetCode 1203.項(xiàng)目管理

總結(jié)

以上是生活随笔為你收集整理的拓扑排序（Topological Sorting）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。