前置知識(shí)
有向無環(huán)圖
在圖論中，如果一個(gè)有向圖無法從某個(gè)頂點(diǎn)出發(fā)經(jīng)過若干條邊回到該點(diǎn)，則這個(gè)圖是一個(gè)有向無環(huán)圖（DAG圖）。
如圖所示。
入度
對(duì)于一個(gè)有向圖，若x點(diǎn)指向y點(diǎn)，則稱x點(diǎn)為y點(diǎn)的入度。
出度
對(duì)于一個(gè)有向圖，若x點(diǎn)指向y點(diǎn)，則稱y點(diǎn)為x點(diǎn)的出度。
隊(duì)列
隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。
我們可以用雙指針標(biāo)記一下，通過front指針與rear指針，對(duì)隊(duì)頭和隊(duì)尾進(jìn)行標(biāo)記，然后只允許在front、rear指針的位置進(jìn)行增刪改查，那么這樣便實(shí)現(xiàn)了對(duì)數(shù)組的受限。這是一種運(yùn)用數(shù)組的數(shù)據(jù)結(jié)構(gòu)對(duì)隊(duì)列的模擬。初學(xué)者建議先用這種方式熟悉隊(duì)列。
具體操作：
/*
通常將front賦值為0，rear賦值為-1
方便后續(xù)進(jìn)隊(duì)、出隊(duì)以及取隊(duì)首元素
*/
int a[100], front=0, rear=-1;
// 進(jìn)隊(duì)
a[++rear] = 10;
// 出隊(duì)
front++
// 取隊(duì)首元素
a[front]
// 取隊(duì)尾元素
a[rear]
// 判斷是否為空隊(duì)
if(front > rear)
cout << "該隊(duì)列為空隊(duì)";
不過，到了后期，為了節(jié)省時(shí)間，我們可以直接用c++自帶的STL容器來完成操作。
具體操作如下：
// 導(dǎo)入queue包
#include<queue>
// 申明一個(gè)queue對(duì)象
// 填入你想裝填的數(shù)據(jù)類型
queue<int> qu;
// 進(jìn)隊(duì)
int a = 10;
qu.push(a);
// 出隊(duì)，無返回值
qu.pop();
// 取隊(duì)首元素
int front = qu.front();
概述
今天我們來學(xué)拓?fù)渑判?/strong>
什么是拓?fù)渑判蚰兀?br>百度百科這樣說：
對(duì)一個(gè)有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進(jìn)行拓?fù)渑判?，是將G中所有頂點(diǎn)排成一個(gè)線性序列，使得圖中任意一對(duì)頂點(diǎn)u和v，若邊<u,v>∈E(G)，則u在線性序列中出現(xiàn)在v之前。通常，這樣的線性序列稱為滿足拓?fù)浯涡?Topological Order)的序列，簡稱拓?fù)湫蛄小：唵蔚恼f，由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱之為拓?fù)渑判颉?/p>
什么意思呢？
俗話說的好：
實(shí)踐是真理的試金石
那么，就讓我們舉一個(gè)例子吧！
如圖，1、2、3、4、5幾個(gè)點(diǎn)組成了一個(gè)圖。
那么，1，2，4，3，6，5或1，2，4，3，5，6就是它的拓?fù)湫?/strong>
但是，這是如何實(shí)現(xiàn)的呢？請(qǐng)看下面的算法原理。
算法原理
下面我將使用圖文結(jié)合的方式演示拓?fù)渑判虻乃惴ㄔ怼?/p>
還是上面那張圖。
首先，將入度為0的點(diǎn)入隊(duì)。上圖中是點(diǎn)1。
然后，用寬搜遍歷隊(duì)列。
對(duì)每個(gè)點(diǎn)的每輪遍歷步驟如下：
- 將這個(gè)點(diǎn)出隊(duì)，并加入拓?fù)鋽?shù)組中
- 遍歷這個(gè)點(diǎn)的所有出度
- 將其出度點(diǎn)的入度數(shù)量減少一
- 如果其出度點(diǎn)入度為0，入隊(duì)
那么，一輪下來，就變成這樣子了：
以此類推。
遍歷到點(diǎn)3時(shí)，是這樣的：
……
然后，就沒有然后了，一切結(jié)束。
如圖所示，其拓?fù)湫驗(yàn)?，2，4，3，5，6。當(dāng)然，也可以是1，2，4，3，6，5。
算法實(shí)現(xiàn)
這可以變?yōu)橐韵碌膯栴}。我稱為拓?fù)渑判蛟獑栴}。
給你一個(gè)有向無環(huán)圖，請(qǐng)輸出它的拓?fù)湫颍╩條有向邊，n個(gè)結(jié)點(diǎn)）
建圖（鄰接表存圖）
首先，我們要建圖
這里采用鄰接表建圖。
鄰接表是什么？
以點(diǎn)為一個(gè)結(jié)點(diǎn)，用其鄰接點(diǎn)建表
怎么這么朦朧？好吧，偷懶了，自己查百度……
看到這里，就默認(rèn)你會(huì)了建圖操作。那么，放一下代碼。
（此處設(shè)定為m條有向邊）
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
rd[y]++;
e[x].push_back(y);
}
rd[y]++ 是什么意思？請(qǐng)往后看。
入隊(duì)
上面提到，首先，將入度為0的點(diǎn)入隊(duì)。
那么，我們就遍歷一遍n個(gè)點(diǎn)，當(dāng)遇到入度為0的點(diǎn)時(shí)，入隊(duì)。
如何判斷入度為0？
這時(shí)前面的 rd數(shù)組 就有用了。它是用于統(tǒng)計(jì)入度數(shù)的。
而前面為何是rd[y]++?
因?yàn)槭?x指向y，因此y入度數(shù)加1
入隊(duì)操作
非常簡單！這里為了省力，用了STL容器
只需要**q.push（i）**一下就可以了
代碼
queue<int>q;
for(int i=1;i<=n;i++)
{
if(rd[i]==0) q.push(i);
//入度為0，入隊(duì)
}
核心部分
這部分的過程，我在前面是這樣說的：
用寬搜遍歷隊(duì)列。
那就寬搜。
寬搜
沒遍歷到一個(gè)點(diǎn)，就將其彈出，并壓入拓?fù)鋽?shù)組。
對(duì)每個(gè)點(diǎn)的操作
我在前面這樣說：
對(duì)每個(gè)點(diǎn)的每輪遍歷步驟如下：
1.將這個(gè)點(diǎn)出隊(duì)，并加入拓?fù)鋽?shù)組中
2.遍歷這個(gè)點(diǎn)的所有出度
3.將其出度點(diǎn)的入度數(shù)量減少一
4.如果其出度點(diǎn)入度為0，入隊(duì)
那就照著做嘛。
很簡單，實(shí)在看不懂代碼中有注釋。
代碼
while(!q.empty())
{
int x=q.front();
q.pop();
topu.push_back(x);//推入拓?fù)鋽?shù)組
for(auto y:e[x])
{
rd[y]--;//刪掉一條邊
if(rd[y]==0)//入度為0
{
q.push(y);//入隊(duì)
}
}
}
好，大功告成！
算法元代碼
上面沒看懂的話，看下面的代碼，含有注釋。
#include<bits/stdc++.h>
using namespace std;
const int NN=5005;
int n,m,rd[NN];
//rd[i]表示i點(diǎn)的入度數(shù)
vector<int>e[NN],topu;
//e作為鄰接表存儲(chǔ)用，topu儲(chǔ)存拓?fù)湫?
void tuopu()
{
queue<int>q;
for(int i=1;i<=n;i++)
{
if(rd[i]==0) q.push(i);
//入度為0，入隊(duì)
}
while(!q.empty())
{
int x=q.front();
q.pop();
topu.push_back(x);//推入拓?fù)鋽?shù)組
for(auto y:e[x])
{
rd[y]--;//刪掉一條邊
if(rd[y]==0)//入度為0
{
q.push(y);//入隊(duì)
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
rd[y]++;//x指向y，因此y入度數(shù)加1
e[x].push_back(y);//加邊
}
tuopu();
for(auto x:topu)
{
printf("%d ",x);//輸出拓?fù)湫?
}
}
總結(jié)
拓?fù)渑判蚓褪沁@回事：
首先，將入度為0的點(diǎn)入隊(duì)。
然后，用寬搜遍歷隊(duì)列。
在此之后，對(duì)每個(gè)點(diǎn)進(jìn)行如下操作：
1.將這個(gè)點(diǎn)出隊(duì)，并加入拓?fù)鋽?shù)組中
2.遍歷這個(gè)點(diǎn)的所有出度
3.將其出度點(diǎn)的入度數(shù)量減少一
4.如果其出度點(diǎn)入度為0，入隊(duì)文章來源：http://www.zghlxwxcb.cn/news/detail-723783.html
下一篇文章，我將會(huì)詳細(xì)講解拓?fù)渑判蛳嚓P(guān)例題。
好，期待三連~~文章來源地址http://www.zghlxwxcb.cn/news/detail-723783.html
到了這里，關(guān)于拓?fù)渑判蛟斀猓ò惴ㄔ韴D解、算法實(shí)現(xiàn)過程詳解、算法例題變式全面講解等）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
