C++詳細(xì)講解圖的拓?fù)渑判?/h1>
更新時(shí)間：2022年05月30日 11:20:08 作者：quicklsleap
拓?fù)渑判颍═opological?Sorting）若一個(gè)由圖中所有點(diǎn)構(gòu)成的序列?A?滿足：對于圖中的每條邊?(x,y)，x?在?A?中都出現(xiàn)在?y?之前，則稱?A?是該圖的一個(gè)拓?fù)湫蛄?/div>
一、前言
且該序列必須滿足下面兩個(gè)條件：
- 每個(gè)頂點(diǎn)出現(xiàn)且只出現(xiàn)一次。
- 若存在一條從頂點(diǎn) x到頂點(diǎn) y的路徑，那么在序列中頂點(diǎn) x 出現(xiàn)在頂點(diǎn) y的前面。
拓?fù)渑判蛑贿m用于 AOV網(wǎng) （有向無環(huán)圖）
若圖中有環(huán)，則一定不存在拓?fù)湫颉?/p>
可以證明，一個(gè)有向無環(huán)圖，一定存在一個(gè)拓?fù)湫蛄?。有向無環(huán)圖，又被稱為拓?fù)鋱D。
入度: 即有多少條邊指向自己這個(gè)節(jié)點(diǎn)。
出度: 即有多少條邊從自己這個(gè)節(jié)點(diǎn)指出去。
二、算法流程
算法流程：
用隊(duì)列來執(zhí)行 ，初始化所有入度為0的頂點(diǎn)入隊(duì)。
主要由以下兩步循環(huán)執(zhí)行，直到不存在入度為 0 的頂點(diǎn)為止
選擇一個(gè)入度為 0 的頂點(diǎn)，并將它輸出；
刪除圖中從頂點(diǎn)連出的所有邊
循環(huán)結(jié)束
若輸出的頂點(diǎn)數(shù)小于圖中的頂點(diǎn)數(shù)，則表示該圖存在回路，即無法拓?fù)渑判颍?/p>
否則，輸出的就是拓?fù)湫蛄?（不唯一）
模板如下：
1.數(shù)組模擬隊(duì)列實(shí)現(xiàn)拓?fù)渑判?/p>
bool topsort()
{
int hh = 0, tt = -1;
// in[i] 存儲點(diǎn)i的入度
for (int i = 1; i <= n; i ++ )// 將所有入度為0的點(diǎn)加入隊(duì)列
if (in[i]==0)
top[ ++ tt] = i;
while (hh <= tt)
{
int t = top[hh ++ ];//找到入度為0的隊(duì)頭
//遍歷一下以t為頭節(jié)點(diǎn)的的單鏈表，給每一個(gè)結(jié)點(diǎn)都要減去1，并再次找到入度為0的點(diǎn)
for (int i = h[t]; i != -1; i = ne[i])
{
// 遍歷 t 點(diǎn)的出邊
int j = e[i];
if (-- in[j] == 0)//將入度減1,如果 j 入度為0，加入隊(duì)列當(dāng)中
top[ ++ tt] = j;
}
}
// 如果所有點(diǎn)都入隊(duì)了，說明存在拓?fù)湫蛄?；否則不存在拓?fù)湫蛄小?
return tt == n - 1;
}
2.使用STL queue實(shí)現(xiàn)拓?fù)渑判?/p>
bool topsort(){
queue<int> q;
int t;
for(int i = 1;i <= n; ++i)// 將所有入度為0的點(diǎn)加入隊(duì)列
if(in[i] == 0) q.push(i);
while(q.size()){
t = q.front();//每次取出隊(duì)列的首部
top[cnt] = t;//加入到 拓?fù)湫蛄兄?
cnt ++; // 序列中的元素 ++
q.pop();
for(int i = h[t];i != -1; i = ne[i]){
// 遍歷 t 點(diǎn)的出邊
int j = e[i];
in[j] --;// j 的入度 --
if(in[j] == 0) q.push(j); //如果 j 入度為0，加入隊(duì)列當(dāng)中
}
}
if(cnt < n) return 0;
else return 1;
}
時(shí)間復(fù)雜度 O(n+m), n表示點(diǎn)數(shù)，m表示邊數(shù)
三、有向圖的拓?fù)渑判?/h2>
給定一個(gè) n 個(gè)點(diǎn) m 條邊的有向圖，點(diǎn)的編號是 1 到 n，圖中可能存在重邊和自環(huán)。
請輸出任意一個(gè)該有向圖的拓?fù)湫蛄?，如果拓?fù)湫蛄胁淮嬖冢瑒t輸出 −1。
思路
我們每次找到入讀為0的點(diǎn)，然后把他插入到隊(duì)列里，然后將這個(gè)點(diǎn)刪除，這也就意味著這個(gè)點(diǎn)連接的下一個(gè)點(diǎn)（可能是多個(gè)）的入度就會減1。
這個(gè)時(shí)候，我們就進(jìn)入了下一輪。
我們因?yàn)榍懊鎸⒁粋€(gè)點(diǎn)刪除了，那么它指向的點(diǎn)的入度就會都減去1，所以，就會出現(xiàn)新的點(diǎn)的入度為0，這個(gè)點(diǎn)顯然是因?yàn)樗娜攵刃?，所以它理所?yīng)當(dāng)?shù)呐旁谕負(fù)湫蚶锩嬖诘诙弧．?dāng)前面的一個(gè)點(diǎn)沒有了被刪除了，那它就要首當(dāng)其沖了。
和圖的BFS思路很像，但是加了搜索的規(guī)則（即入度為零的先被搜索）可以看點(diǎn)這里
AC代碼
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int e[N],ne[N],h[N],idx,in[N],n,m,top[N],cnt = 1;
// e,ne,h,idx 鄰接表模板
// in 代表每個(gè)元素的入度
// top是拓?fù)渑判虻男蛄?，cnt代表top中有多少個(gè)元素
void add(int a,int b){
e[idx] = b; ne[idx] = h[a];h[a] = idx ++;
}
bool topsort(){
queue<int> q;
int t;
for(int i = 1;i <= n; ++i)// 將所有入度為0的點(diǎn)加入隊(duì)列
if(in[i] == 0) q.push(i);
while(q.size()){
t = q.front();//每次取出隊(duì)列的首部
top[cnt] = t;//加入到 拓?fù)湫蛄兄?
cnt ++; // 序列中的元素 ++
q.pop();
for(int i = h[t];i != -1; i = ne[i]){
// 遍歷 t 點(diǎn)的出邊
int j = e[i];
in[j] --;// j 的入度 --
if(in[j] == 0) q.push(j); //如果 j 入度為0，加入隊(duì)列當(dāng)中
}
}
if(cnt < n) return 0;
else return 1;
}
int main(){
int a,b;
cin >> n >> m;
memset(h,-1,sizeof h);//給頭節(jié)點(diǎn)賦值為-1；
while(m--){
cin >> a >> b;
add(a,b);
in[b] ++;// a -> b , b的入度++
}
if(topsort() == 0) cout << "-1";
else {
for(int i = 1;i <= n; ++i){
cout << top[i] <<" ";
}
}
return 0;
}
到此這篇關(guān)于C++詳細(xì)講解圖的拓?fù)渑判虻奈恼戮徒榻B到這了,更多相關(guān)C++拓?fù)渑判騼?nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
-
C語言中求和、計(jì)算平均值、方差和標(biāo)準(zhǔn)差的實(shí)例
這篇文章主要介紹了C語言中求和、計(jì)算平均值、方差和標(biāo)準(zhǔn)差的實(shí)例，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧 2020-12-12
-
這篇文章主要介紹了Qt?5.9使用VTK顯示點(diǎn)云,主要包括PCL安裝及在VS2013中使用PCL的方法，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下 2022-07-07
-
這篇文章主要為大家詳細(xì)介紹了Opencv實(shí)現(xiàn)拼圖板小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下 2020-03-03
-
從匯編看c++中函數(shù)里面的static關(guān)鍵字的使用說明
c++中的static關(guān)鍵字使得函數(shù)里面的局部變量的存活期不在局限于函數(shù)里面，而是變?yōu)樵谡麄€(gè)程序生命期里面都有效 2013-05-05
-
本文主要介紹了Qt菜單QMenu和菜單欄QMenuBar及自定義菜單用法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧 2022-05-05
-
C++分析類的對象作類成員調(diào)用構(gòu)造與析構(gòu)函數(shù)及靜態(tài)成員
終于到了對象的初始化和清理的最后階段了，在這里分享一個(gè)cpp里有多個(gè)類時(shí)，一個(gè)類的對象作為另一個(gè)類成員的時(shí)候構(gòu)造函數(shù)和析構(gòu)函數(shù)調(diào)用的時(shí)機(jī)。還有一個(gè)靜態(tài)成員也是經(jīng)常考到的點(diǎn)，在這篇博客將會詳解其概念并舉出案例鞏固，讓我們開始 2022-05-05
-
基于C語言實(shí)現(xiàn)簡單學(xué)生成績管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了基于C語言實(shí)現(xiàn)簡單學(xué)生成績管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下 2022-08-08
-
這篇文章主要介紹了C++入門實(shí)現(xiàn)十步萬度游戲,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下 2021-10-10
-
C語言實(shí)現(xiàn)飛機(jī)大戰(zhàn)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)飛機(jī)大戰(zhàn)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下 2022-06-06
-
Boost是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱。Boost庫是一個(gè)可移植、提供源代碼的C++庫，作為標(biāo)準(zhǔn)庫的后備，是C++標(biāo)準(zhǔn)化進(jìn)程的開發(fā)引擎之一，是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱 2022-11-11
最新評論
一、前言
且該序列必須滿足下面兩個(gè)條件：
- 每個(gè)頂點(diǎn)出現(xiàn)且只出現(xiàn)一次。
- 若存在一條從頂點(diǎn) x到頂點(diǎn) y的路徑，那么在序列中頂點(diǎn) x 出現(xiàn)在頂點(diǎn) y的前面。
拓?fù)渑判蛑贿m用于 AOV網(wǎng) （有向無環(huán)圖）
若圖中有環(huán)，則一定不存在拓?fù)湫颉?/p>
可以證明，一個(gè)有向無環(huán)圖，一定存在一個(gè)拓?fù)湫蛄?。有向無環(huán)圖，又被稱為拓?fù)鋱D。
入度: 即有多少條邊指向自己這個(gè)節(jié)點(diǎn)。
出度: 即有多少條邊從自己這個(gè)節(jié)點(diǎn)指出去。
二、算法流程
算法流程：
用隊(duì)列來執(zhí)行 ，初始化所有入度為0的頂點(diǎn)入隊(duì)。
主要由以下兩步循環(huán)執(zhí)行，直到不存在入度為 0 的頂點(diǎn)為止
選擇一個(gè)入度為 0 的頂點(diǎn)，并將它輸出；
刪除圖中從頂點(diǎn)連出的所有邊
循環(huán)結(jié)束
若輸出的頂點(diǎn)數(shù)小于圖中的頂點(diǎn)數(shù)，則表示該圖存在回路，即無法拓?fù)渑判颍?/p>
否則，輸出的就是拓?fù)湫蛄?（不唯一）
模板如下：
1.數(shù)組模擬隊(duì)列實(shí)現(xiàn)拓?fù)渑判?/p>
bool topsort()
{
int hh = 0, tt = -1;
// in[i] 存儲點(diǎn)i的入度
for (int i = 1; i <= n; i ++ )// 將所有入度為0的點(diǎn)加入隊(duì)列
if (in[i]==0)
top[ ++ tt] = i;
while (hh <= tt)
{
int t = top[hh ++ ];//找到入度為0的隊(duì)頭
//遍歷一下以t為頭節(jié)點(diǎn)的的單鏈表，給每一個(gè)結(jié)點(diǎn)都要減去1，并再次找到入度為0的點(diǎn)
for (int i = h[t]; i != -1; i = ne[i])
{
// 遍歷 t 點(diǎn)的出邊
int j = e[i];
if (-- in[j] == 0)//將入度減1,如果 j 入度為0，加入隊(duì)列當(dāng)中
top[ ++ tt] = j;
}
}
// 如果所有點(diǎn)都入隊(duì)了，說明存在拓?fù)湫蛄?；否則不存在拓?fù)湫蛄小?
return tt == n - 1;
}
2.使用STL queue實(shí)現(xiàn)拓?fù)渑判?/p>
bool topsort(){
queue<int> q;
int t;
for(int i = 1;i <= n; ++i)// 將所有入度為0的點(diǎn)加入隊(duì)列
if(in[i] == 0) q.push(i);
while(q.size()){
t = q.front();//每次取出隊(duì)列的首部
top[cnt] = t;//加入到 拓?fù)湫蛄兄?
cnt ++; // 序列中的元素 ++
q.pop();
for(int i = h[t];i != -1; i = ne[i]){
// 遍歷 t 點(diǎn)的出邊
int j = e[i];
in[j] --;// j 的入度 --
if(in[j] == 0) q.push(j); //如果 j 入度為0，加入隊(duì)列當(dāng)中
}
}
if(cnt < n) return 0;
else return 1;
}時(shí)間復(fù)雜度 O(n+m), n表示點(diǎn)數(shù)，m表示邊數(shù)
三、有向圖的拓?fù)渑判?/h2>
給定一個(gè) n 個(gè)點(diǎn) m 條邊的有向圖，點(diǎn)的編號是 1 到 n，圖中可能存在重邊和自環(huán)。
請輸出任意一個(gè)該有向圖的拓?fù)湫蛄?，如果拓?fù)湫蛄胁淮嬖冢瑒t輸出 −1。
思路
我們每次找到入讀為0的點(diǎn)，然后把他插入到隊(duì)列里，然后將這個(gè)點(diǎn)刪除，這也就意味著這個(gè)點(diǎn)連接的下一個(gè)點(diǎn)（可能是多個(gè)）的入度就會減1。
這個(gè)時(shí)候，我們就進(jìn)入了下一輪。
我們因?yàn)榍懊鎸⒁粋€(gè)點(diǎn)刪除了，那么它指向的點(diǎn)的入度就會都減去1，所以，就會出現(xiàn)新的點(diǎn)的入度為0，這個(gè)點(diǎn)顯然是因?yàn)樗娜攵刃?，所以它理所?yīng)當(dāng)?shù)呐旁谕負(fù)湫蚶锩嬖诘诙弧．?dāng)前面的一個(gè)點(diǎn)沒有了被刪除了，那它就要首當(dāng)其沖了。
和圖的BFS思路很像，但是加了搜索的規(guī)則（即入度為零的先被搜索）可以看點(diǎn)這里
AC代碼
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int e[N],ne[N],h[N],idx,in[N],n,m,top[N],cnt = 1;
// e,ne,h,idx 鄰接表模板
// in 代表每個(gè)元素的入度
// top是拓?fù)渑判虻男蛄?，cnt代表top中有多少個(gè)元素
void add(int a,int b){
e[idx] = b; ne[idx] = h[a];h[a] = idx ++;
}
bool topsort(){
queue<int> q;
int t;
for(int i = 1;i <= n; ++i)// 將所有入度為0的點(diǎn)加入隊(duì)列
if(in[i] == 0) q.push(i);
while(q.size()){
t = q.front();//每次取出隊(duì)列的首部
top[cnt] = t;//加入到 拓?fù)湫蛄兄?
cnt ++; // 序列中的元素 ++
q.pop();
for(int i = h[t];i != -1; i = ne[i]){
// 遍歷 t 點(diǎn)的出邊
int j = e[i];
in[j] --;// j 的入度 --
if(in[j] == 0) q.push(j); //如果 j 入度為0，加入隊(duì)列當(dāng)中
}
}
if(cnt < n) return 0;
else return 1;
}
int main(){
int a,b;
cin >> n >> m;
memset(h,-1,sizeof h);//給頭節(jié)點(diǎn)賦值為-1；
while(m--){
cin >> a >> b;
add(a,b);
in[b] ++;// a -> b , b的入度++
}
if(topsort() == 0) cout << "-1";
else {
for(int i = 1;i <= n; ++i){
cout << top[i] <<" ";
}
}
return 0;
}
到此這篇關(guān)于C++詳細(xì)講解圖的拓?fù)渑判虻奈恼戮徒榻B到這了,更多相關(guān)C++拓?fù)渑判騼?nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
-
C語言中求和、計(jì)算平均值、方差和標(biāo)準(zhǔn)差的實(shí)例
這篇文章主要介紹了C語言中求和、計(jì)算平均值、方差和標(biāo)準(zhǔn)差的實(shí)例，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-12-12 - 這篇文章主要介紹了Qt?5.9使用VTK顯示點(diǎn)云,主要包括PCL安裝及在VS2013中使用PCL的方法，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-07-07
- 這篇文章主要為大家詳細(xì)介紹了Opencv實(shí)現(xiàn)拼圖板小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-03-03
-
從匯編看c++中函數(shù)里面的static關(guān)鍵字的使用說明
c++中的static關(guān)鍵字使得函數(shù)里面的局部變量的存活期不在局限于函數(shù)里面，而是變?yōu)樵谡麄€(gè)程序生命期里面都有效2013-05-05 - 本文主要介紹了Qt菜單QMenu和菜單欄QMenuBar及自定義菜單用法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05
-
C++分析類的對象作類成員調(diào)用構(gòu)造與析構(gòu)函數(shù)及靜態(tài)成員
終于到了對象的初始化和清理的最后階段了，在這里分享一個(gè)cpp里有多個(gè)類時(shí)，一個(gè)類的對象作為另一個(gè)類成員的時(shí)候構(gòu)造函數(shù)和析構(gòu)函數(shù)調(diào)用的時(shí)機(jī)。還有一個(gè)靜態(tài)成員也是經(jīng)常考到的點(diǎn)，在這篇博客將會詳解其概念并舉出案例鞏固，讓我們開始2022-05-05 -
基于C語言實(shí)現(xiàn)簡單學(xué)生成績管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了基于C語言實(shí)現(xiàn)簡單學(xué)生成績管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-08-08 - 這篇文章主要介紹了C++入門實(shí)現(xiàn)十步萬度游戲,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-10-10
-
C語言實(shí)現(xiàn)飛機(jī)大戰(zhàn)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)飛機(jī)大戰(zhàn)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06 - Boost是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱。Boost庫是一個(gè)可移植、提供源代碼的C++庫，作為標(biāo)準(zhǔn)庫的后備，是C++標(biāo)準(zhǔn)化進(jìn)程的開發(fā)引擎之一，是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱2022-11-11