詳解C++實(shí)現(xiàn)拓?fù)渑判蛩惴?/h1>
更新時間:2021年06月11日 16:20:34 作者:Ouyang_Lianjun
拓?fù)渑判蚴菍σ粋€有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進(jìn)行拓?fù)渑判?,是將G中所有頂點(diǎn)排成一個線性序列,使得圖中任意一對頂點(diǎn)u和v,若邊(u,v)∈E(G),則u在線性序列中出現(xiàn)在v之前。本文將對其原理進(jìn)行講解,并且用C++進(jìn)行實(shí)現(xiàn)
一、拓?fù)渑判虻慕榻B
拓?fù)渑判驅(qū)?yīng)施工的流程圖具有特別重要的作用,它可以決定哪些子工程必須要先執(zhí)行,哪些子工程要在某些工程執(zhí)行后才可以執(zhí)行。為了形象地反映出整個工程中各個子工程(活動)之間的先后關(guān)系,可用一個有向圖來表示,圖中的頂點(diǎn)代表活動(子工程),圖中的有向邊代表活動的先后關(guān)系,即有向邊的起點(diǎn)的活動是終點(diǎn)活動的前序活動,只有當(dāng)起點(diǎn)活動完成之后,其終點(diǎn)活動才能進(jìn)行。通常,我們把這種頂點(diǎn)表示活動、邊表示活動間先后關(guān)系的有向圖稱做頂點(diǎn)活動網(wǎng)(Activity On Vertex network),簡稱AOV網(wǎng)。
一個AOV網(wǎng)應(yīng)該是一個有向無環(huán)圖,即不應(yīng)該帶有回路,因?yàn)槿魩в谢芈?,則回路上的所有活動都無法進(jìn)行(對于數(shù)據(jù)流來說就是死循環(huán))。在AOV網(wǎng)中,若不存在回路,則所有活動可排列成一個線性序列,使得每個活動的所有前驅(qū)活動都排在該活動的前面,我們把此序列叫做拓?fù)湫蛄?Topological order),由AOV網(wǎng)構(gòu)造拓?fù)湫蛄械倪^程叫做拓?fù)渑判?Topological sort)。AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?,滿足上述定義的任一線性序列都稱作它的拓?fù)湫蛄小?/p>
二、拓?fù)渑判虻膶?shí)現(xiàn)步驟
1.在有向圖中選一個沒有前驅(qū)的頂點(diǎn)并且輸出
2.從圖中刪除該頂點(diǎn)和所有以它為尾的?。ò自捑褪牵簞h除所有和它有關(guān)的邊)
3.重復(fù)上述兩步,直至所有頂點(diǎn)輸出,或者當(dāng)前圖中不存在無前驅(qū)的頂點(diǎn)為止,后者代表我們的有向圖是有環(huán)的,因此,也可以通過拓?fù)渑判騺砼袛嘁粋€圖是否有環(huán)。
三、拓?fù)渑判蚴纠謩訉?shí)現(xiàn)
如果我們有如下的一個有向無環(huán)圖,我們需要對這個圖的頂點(diǎn)進(jìn)行拓?fù)渑判?,過程如下:

首先,我們發(fā)現(xiàn)V6和v1是沒有前驅(qū)的,所以我們就隨機(jī)選去一個輸出,我們先輸出V6,刪除和V6有關(guān)的邊,得到如下圖結(jié)果:

然后,我們繼續(xù)尋找沒有前驅(qū)的頂點(diǎn),發(fā)現(xiàn)V1沒有前驅(qū),所以輸出V1,刪除和V1有關(guān)的邊,得到下圖的結(jié)果:

然后,我們又發(fā)現(xiàn)V4和V3都是沒有前驅(qū)的,那么我們就隨機(jī)選取一個頂點(diǎn)輸出(具體看你實(shí)現(xiàn)的算法和圖存儲結(jié)構(gòu)),我們輸出V4,得到如下圖結(jié)果:

然后,我們輸出沒有前驅(qū)的頂點(diǎn)V3,得到如下結(jié)果:

然后,我們分別輸出V5和V2,最后全部頂點(diǎn)輸出完成,該圖的一個拓?fù)湫蛄袨椋?/p>
v6–>v1—->v4—>v3—>v5—>v2
四、拓?fù)渑判虻拇a實(shí)現(xiàn)
下面,我們將用兩種方法來實(shí)現(xiàn)我么的拓?fù)渑判颍?/p>
1.Kahn算法
2.基于DFS的拓?fù)渑判蛩惴?/p>
首先我們先介紹第一個算法的思路:
Kahn的算法的思路其實(shí)就是我們之前那個手動展示的拓?fù)渑判虻膶?shí)現(xiàn),我們先使用一個棧保存入度為0 的頂點(diǎn),然后輸出棧頂元素并且將和棧頂元素有關(guān)的邊刪除,減少和棧頂元素有關(guān)的頂點(diǎn)的入度數(shù)量并且把入度減少到0的頂點(diǎn)也入棧。具體的代碼如下:
bool Graph_DG::topological_sort() {
cout << "圖的拓?fù)湫蛄袨椋? << endl;
//棧s用于保存棧為空的頂點(diǎn)下標(biāo)
stack<int> s;
int i;
ArcNode * temp;
//計算每個頂點(diǎn)的入度,保存在indgree數(shù)組中
for (i = 0; i != this->vexnum; i++) {
temp = this->arc[i].firstarc;
while (temp) {
++this->indegree[temp->adjvex];
temp = temp->next;
}
}
//把入度為0的頂點(diǎn)入棧
for (i = 0; i != this->vexnum; i++) {
if (!indegree[i]) {
s.push(i);
}
}
//count用于計算輸出的頂點(diǎn)個數(shù)
int count=0;
while (!s.empty()) {//如果棧為空,則結(jié)束循環(huán)
i = s.top();
s.pop();//保存棧頂元素,并且棧頂元素出棧
cout << this->arc[i].data<<" ";//輸出拓?fù)湫蛄?
temp = this->arc[i].firstarc;
while (temp) {
if (!(--this->indegree[temp->adjvex])) {//如果入度減少到為0,則入棧
s.push(temp->adjvex);
}
temp = temp->next;
}
++count;
}
if (count == this->vexnum) {
cout << endl;
return true;
}
cout << "此圖有環(huán),無拓?fù)湫蛄? << endl;
return false;//說明這個圖有環(huán)
}
現(xiàn)在,我們來介紹第二個算法的思路:
其實(shí)DFS就是深度優(yōu)先搜索,它每次都沿著一條路徑一直往下搜索,知道某個頂點(diǎn)沒有了出度時,就停止遞歸,往回走,所以我們就用DFS的這個思路,我們可以得到一個有向無環(huán)圖的拓?fù)湫蛄?,其?shí)DFS很像Kahn算法的逆過程。具體的代碼實(shí)現(xiàn)如下:
bool Graph_DG::topological_sort_by_dfs() {
stack<string> result;
int i;
bool * visit = new bool[this->vexnum];
//初始化我們的visit數(shù)組
memset(visit, 0, this->vexnum);
cout << "基于DFS的拓?fù)渑判驗(yàn)椋? << endl;
//開始執(zhí)行DFS算法
for (i = 0; i < this->vexnum; i++) {
if (!visit[i]) {
dfs(i, visit, result);
}
}
//輸出拓?fù)湫蛄?,因?yàn)槲覀兠看味际钦业搅顺龆葹?的頂點(diǎn)加入棧中,
//所以輸出時其實(shí)就要逆序輸出,這樣就是每次都是輸出入度為0的頂點(diǎn)
for (i = 0; i < this->vexnum; i++) {
cout << result.top() << " ";
result.pop();
}
cout << endl;
return true;
}
void Graph_DG::dfs(int n, bool * & visit, stack<string> & result) {
visit[n] = true;
ArcNode * temp = this->arc[n].firstarc;
while (temp) {
if (!visit[temp->adjvex]) {
dfs(temp->adjvex, visit,result);
}
temp = temp->next;
}
//由于加入頂點(diǎn)到集合中的時機(jī)是在dfs方法即將退出之時,
//而dfs方法本身是個遞歸方法,
//僅僅要當(dāng)前頂點(diǎn)還存在邊指向其他不論什么頂點(diǎn),
//它就會遞歸調(diào)用dfs方法,而不會退出。
//因此,退出dfs方法,意味著當(dāng)前頂點(diǎn)沒有指向其他頂點(diǎn)的邊了
//,即當(dāng)前頂點(diǎn)是一條路徑上的最后一個頂點(diǎn)。
//換句話說其實(shí)就是此時該頂點(diǎn)出度為0了
result.push(this->arc[n].data);
}
兩種算法總結(jié):
對于基于DFS的算法,增加結(jié)果集的條件是:頂點(diǎn)的出度為0。這個條件和Kahn算法中入度為0的頂點(diǎn)集合似乎有著異曲同工之妙,Kahn算法不須要檢測圖是否為DAG,假設(shè)圖為DAG,那么在入度為0的棧為空之后,圖中還存在沒有被移除的邊,這就說明了圖中存在環(huán)路。而基于DFS的算法須要首先確定圖為DAG,當(dāng)然也可以做出適當(dāng)調(diào)整,讓環(huán)路的檢測測和拓?fù)渑判蛲粫r候進(jìn)行,畢竟環(huán)路檢測也可以在DFS的基礎(chǔ)上進(jìn)行。
二者的復(fù)雜度均為O(V+E)。
五、完整的代碼和輸出展示
topological_sort.h文件的代碼
#pragma once
//#pragma once是一個比較常用的C/C++雜注,
//只要在頭文件的最開始加入這條雜注,
//就能夠保證頭文件只被編譯一次。
/*
拓?fù)渑判虮仨毷菍τ邢驁D的操作
算法實(shí)現(xiàn):
(1)Kahn算法
(2)DFS算法
采用鄰接表存儲圖
*/
#include<iostream>
#include<string>
#include<stack>
using namespace std;
//表結(jié)點(diǎn)
struct ArcNode {
ArcNode * next; //下一個關(guān)聯(lián)的邊
int adjvex; //保存弧尾頂點(diǎn)在頂點(diǎn)表中的下標(biāo)
};
struct Vnode {
string data; //頂點(diǎn)名稱
ArcNode * firstarc; //第一個依附在該頂點(diǎn)邊
};
class Graph_DG {
private:
int vexnum; //圖的頂點(diǎn)數(shù)
int edge; //圖的邊數(shù)
int * indegree; //每條邊的入度情況
Vnode * arc; //鄰接表
public:
Graph_DG(int, int);
~Graph_DG();
//檢查輸入邊的頂點(diǎn)是否合法
bool check_edge_value(int,int);
//創(chuàng)建一個圖
void createGraph();
//打印鄰接表
void print();
//進(jìn)行拓?fù)渑判?Kahn算法
bool topological_sort();
//進(jìn)行拓?fù)渑判?,DFS算法
bool topological_sort_by_dfs();
void dfs(int n,bool * & visit, stack<string> & result);
};
topological_sort.cpp文件代碼
#include"topological_sort.h"
Graph_DG::Graph_DG(int vexnum, int edge) {
this->vexnum = vexnum;
this->edge = edge;
this->arc = new Vnode[this->vexnum];
this->indegree = new int[this->vexnum];
for (int i = 0; i < this->vexnum; i++) {
this->indegree[i] = 0;
this->arc[i].firstarc = NULL;
this->arc[i].data = "v" + to_string(i + 1);
}
}
//釋放內(nèi)存空間
Graph_DG::~Graph_DG() {
ArcNode * p, *q;
for (int i = 0; i < this->vexnum; i++) {
if (this->arc[i].firstarc) {
p = this->arc[i].firstarc;
while (p) {
q = p->next;
delete p;
p = q;
}
}
}
delete [] this->arc;
delete [] this->indegree;
}
//判斷我們每次輸入的的邊的信息是否合法
//頂點(diǎn)從1開始編號
bool Graph_DG::check_edge_value(int start, int end) {
if (start<1 || end<1 || start>vexnum || end>vexnum) {
return false;
}
return true;
}
void Graph_DG::createGraph() {
int count = 0;
int start, end;
cout << "輸入每條起點(diǎn)和終點(diǎn)的頂點(diǎn)編號(從1開始編號)" << endl;
while (count != this->edge) {
cin >> start;
cin >> end;
//檢查邊是否合法
while (!this->check_edge_value(start, end)) {
cout << "輸入的頂點(diǎn)不合法,請重新輸入" << endl;
cin >> start;
cin >> end;
}
//聲明一個新的表結(jié)點(diǎn)
ArcNode * temp = new ArcNode;
temp->adjvex = end - 1;
temp->next = NULL;
//如果當(dāng)前頂點(diǎn)的還沒有邊依附時,
if (this->arc[start - 1].firstarc == NULL) {
this->arc[start - 1].firstarc = temp;
}
else {
ArcNode * now = this->arc[start - 1].firstarc;
while(now->next) {
now = now->next;
}//找到該鏈表的最后一個結(jié)點(diǎn)
now->next = temp;
}
++count;
}
}
void Graph_DG::print() {
int count = 0;
cout << "圖的鄰接矩陣為:" << endl;
//遍歷鏈表,輸出鏈表的內(nèi)容
while (count != this->vexnum) {
//輸出鏈表的結(jié)點(diǎn)
cout << this->arc[count].data<<" ";
ArcNode * temp = this->arc[count].firstarc;
while (temp) {
cout<<"<"<< this->arc[count].data<<","<< this->arc[temp->adjvex].data<<"> ";
temp = temp->next;
}
cout << "^" << endl;
++count;
}
}
bool Graph_DG::topological_sort() {
cout << "圖的拓?fù)湫蛄袨椋? << endl;
//棧s用于保存棧為空的頂點(diǎn)下標(biāo)
stack<int> s;
int i;
ArcNode * temp;
//計算每個頂點(diǎn)的入度,保存在indgree數(shù)組中
for (i = 0; i != this->vexnum; i++) {
temp = this->arc[i].firstarc;
while (temp) {
++this->indegree[temp->adjvex];
temp = temp->next;
}
}
//把入度為0的頂點(diǎn)入棧
for (i = 0; i != this->vexnum; i++) {
if (!indegree[i]) {
s.push(i);
}
}
//count用于計算輸出的頂點(diǎn)個數(shù)
int count=0;
while (!s.empty()) {//如果棧為空,則結(jié)束循環(huán)
i = s.top();
s.pop();//保存棧頂元素,并且棧頂元素出棧
cout << this->arc[i].data<<" ";//輸出拓?fù)湫蛄?
temp = this->arc[i].firstarc;
while (temp) {
if (!(--this->indegree[temp->adjvex])) {//如果入度減少到為0,則入棧
s.push(temp->adjvex);
}
temp = temp->next;
}
++count;
}
if (count == this->vexnum) {
cout << endl;
return true;
}
cout << "此圖有環(huán),無拓?fù)湫蛄? << endl;
return false;//說明這個圖有環(huán)
}
bool Graph_DG::topological_sort_by_dfs() {
stack<string> result;
int i;
bool * visit = new bool[this->vexnum];
//初始化我們的visit數(shù)組
memset(visit, 0, this->vexnum);
cout << "基于DFS的拓?fù)渑判驗(yàn)椋? << endl;
//開始執(zhí)行DFS算法
for (i = 0; i < this->vexnum; i++) {
if (!visit[i]) {
dfs(i, visit, result);
}
}
//輸出拓?fù)湫蛄?,因?yàn)槲覀兠看味际钦业搅顺龆葹?的頂點(diǎn)加入棧中,
//所以輸出時其實(shí)就要逆序輸出,這樣就是每次都是輸出入度為0的頂點(diǎn)
for (i = 0; i < this->vexnum; i++) {
cout << result.top() << " ";
result.pop();
}
cout << endl;
return true;
}
void Graph_DG::dfs(int n, bool * & visit, stack<string> & result) {
visit[n] = true;
ArcNode * temp = this->arc[n].firstarc;
while (temp) {
if (!visit[temp->adjvex]) {
dfs(temp->adjvex, visit,result);
}
temp = temp->next;
}
//由于加入頂點(diǎn)到集合中的時機(jī)是在dfs方法即將退出之時,
//而dfs方法本身是個遞歸方法,
//僅僅要當(dāng)前頂點(diǎn)還存在邊指向其他不論什么頂點(diǎn),
//它就會遞歸調(diào)用dfs方法,而不會退出。
//因此,退出dfs方法,意味著當(dāng)前頂點(diǎn)沒有指向其他頂點(diǎn)的邊了
//,即當(dāng)前頂點(diǎn)是一條路徑上的最后一個頂點(diǎn)。
//換句話說其實(shí)就是此時該頂點(diǎn)出度為0了
result.push(this->arc[n].data);
}
main.cpp文件:
#include"topological_sort.h"
//檢驗(yàn)輸入邊數(shù)和頂點(diǎn)數(shù)的值是否有效,可以自己推算為啥:
//頂點(diǎn)數(shù)和邊數(shù)的關(guān)系是:((Vexnum*(Vexnum - 1)) / 2) < edge
bool check(int Vexnum, int edge) {
if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge)
return false;
return true;
}
int main() {
int vexnum; int edge;
cout << "輸入圖的頂點(diǎn)個數(shù)和邊的條數(shù):" << endl;
cin >> vexnum >> edge;
while (!check(vexnum, edge)) {
cout << "輸入的數(shù)值不合法,請重新輸入" << endl;
cin >> vexnum >> edge;
}
Graph_DG graph(vexnum, edge);
graph.createGraph();
graph.print();
graph.topological_sort();
graph.topological_sort_by_dfs();
system("pause");
return 0;
}
輸入:
6 8
1 2
1 3
1 4
3 2
3 5
4 5
6 4
6 5
輸出:

輸入:
13 15
1 2
1 6
1 7
3 1
3 4
4 6
6 5
7 4
7 10
8 7
9 8
10 11
10 12
10 13
12 13
輸出:

以上就是詳解C++實(shí)現(xiàn)拓?fù)渑判蛩惴ǖ脑敿?xì)內(nèi)容,更多關(guān)于C++ 拓?fù)渑判蛩惴ǖ馁Y料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
-
C++中jsoncpp庫和nlohmann-json庫實(shí)現(xiàn)JSON與字符串類型轉(zhuǎn)換
jsoncpp是ROS自帶的一個JSON庫,它提供了一些函數(shù)來解析和生成JSON數(shù)據(jù),在ROS中,可以使用jsoncpp庫來實(shí)現(xiàn)JSON與字符串類型之間的轉(zhuǎn)換,這篇文章主要介紹了jsoncpp庫和nlohmann-json庫實(shí)現(xiàn)JSON與字符串類型轉(zhuǎn)換,需要的朋友可以參考下 2023-08-08
-
C++采用openfilename打開文件對話框用法實(shí)例
這篇文章主要介紹了C++采用openfilename打開文件對話框用法實(shí)例,是C++文件操作中非常實(shí)用的技巧,需要的朋友可以參考下 2014-10-10
-
C語言實(shí)現(xiàn)快速排序的方法及優(yōu)化
這篇文章主要介紹了C語言實(shí)現(xiàn)快速排序的方法及優(yōu)化,快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法,下面我們來看一看傳說中的快速排序的特點(diǎn)與效率怎么樣,需要的朋友可以參考下 2023-07-07
-
dev-c++創(chuàng)建lib(靜態(tài)鏈接庫)文件的實(shí)現(xiàn)步驟
本文主要介紹了dev-c++創(chuàng)建lib(靜態(tài)鏈接庫)文件的實(shí)現(xiàn)步驟,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧 2022-06-06
-
使用c++實(shí)現(xiàn)OpenCV圖像橫向&縱向拼接
這篇文章主要介紹了使用c++實(shí)現(xiàn)OpenCV圖像橫向&縱向拼接,文中有圖像拼接函數(shù),可以實(shí)現(xiàn)如“長圖拼接王”這類小程序的類似功能,大家可以將該函數(shù)封裝在軟件中自由使用 2021-08-08
最新評論
一、拓?fù)渑判虻慕榻B
拓?fù)渑判驅(qū)?yīng)施工的流程圖具有特別重要的作用,它可以決定哪些子工程必須要先執(zhí)行,哪些子工程要在某些工程執(zhí)行后才可以執(zhí)行。為了形象地反映出整個工程中各個子工程(活動)之間的先后關(guān)系,可用一個有向圖來表示,圖中的頂點(diǎn)代表活動(子工程),圖中的有向邊代表活動的先后關(guān)系,即有向邊的起點(diǎn)的活動是終點(diǎn)活動的前序活動,只有當(dāng)起點(diǎn)活動完成之后,其終點(diǎn)活動才能進(jìn)行。通常,我們把這種頂點(diǎn)表示活動、邊表示活動間先后關(guān)系的有向圖稱做頂點(diǎn)活動網(wǎng)(Activity On Vertex network),簡稱AOV網(wǎng)。
一個AOV網(wǎng)應(yīng)該是一個有向無環(huán)圖,即不應(yīng)該帶有回路,因?yàn)槿魩в谢芈?,則回路上的所有活動都無法進(jìn)行(對于數(shù)據(jù)流來說就是死循環(huán))。在AOV網(wǎng)中,若不存在回路,則所有活動可排列成一個線性序列,使得每個活動的所有前驅(qū)活動都排在該活動的前面,我們把此序列叫做拓?fù)湫蛄?Topological order),由AOV網(wǎng)構(gòu)造拓?fù)湫蛄械倪^程叫做拓?fù)渑判?Topological sort)。AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?,滿足上述定義的任一線性序列都稱作它的拓?fù)湫蛄小?/p>
二、拓?fù)渑判虻膶?shí)現(xiàn)步驟
1.在有向圖中選一個沒有前驅(qū)的頂點(diǎn)并且輸出
2.從圖中刪除該頂點(diǎn)和所有以它為尾的?。ò自捑褪牵簞h除所有和它有關(guān)的邊)
3.重復(fù)上述兩步,直至所有頂點(diǎn)輸出,或者當(dāng)前圖中不存在無前驅(qū)的頂點(diǎn)為止,后者代表我們的有向圖是有環(huán)的,因此,也可以通過拓?fù)渑判騺砼袛嘁粋€圖是否有環(huán)。
三、拓?fù)渑判蚴纠謩訉?shí)現(xiàn)
如果我們有如下的一個有向無環(huán)圖,我們需要對這個圖的頂點(diǎn)進(jìn)行拓?fù)渑判?,過程如下:
首先,我們發(fā)現(xiàn)V6和v1是沒有前驅(qū)的,所以我們就隨機(jī)選去一個輸出,我們先輸出V6,刪除和V6有關(guān)的邊,得到如下圖結(jié)果:
然后,我們繼續(xù)尋找沒有前驅(qū)的頂點(diǎn),發(fā)現(xiàn)V1沒有前驅(qū),所以輸出V1,刪除和V1有關(guān)的邊,得到下圖的結(jié)果:
然后,我們又發(fā)現(xiàn)V4和V3都是沒有前驅(qū)的,那么我們就隨機(jī)選取一個頂點(diǎn)輸出(具體看你實(shí)現(xiàn)的算法和圖存儲結(jié)構(gòu)),我們輸出V4,得到如下圖結(jié)果:
然后,我們輸出沒有前驅(qū)的頂點(diǎn)V3,得到如下結(jié)果:
然后,我們分別輸出V5和V2,最后全部頂點(diǎn)輸出完成,該圖的一個拓?fù)湫蛄袨椋?/p>
v6–>v1—->v4—>v3—>v5—>v2
四、拓?fù)渑判虻拇a實(shí)現(xiàn)
下面,我們將用兩種方法來實(shí)現(xiàn)我么的拓?fù)渑判颍?/p>
1.Kahn算法
2.基于DFS的拓?fù)渑判蛩惴?/p>
首先我們先介紹第一個算法的思路:
Kahn的算法的思路其實(shí)就是我們之前那個手動展示的拓?fù)渑判虻膶?shí)現(xiàn),我們先使用一個棧保存入度為0 的頂點(diǎn),然后輸出棧頂元素并且將和棧頂元素有關(guān)的邊刪除,減少和棧頂元素有關(guān)的頂點(diǎn)的入度數(shù)量并且把入度減少到0的頂點(diǎn)也入棧。具體的代碼如下:
bool Graph_DG::topological_sort() { cout << "圖的拓?fù)湫蛄袨椋? << endl; //棧s用于保存棧為空的頂點(diǎn)下標(biāo) stack<int> s; int i; ArcNode * temp; //計算每個頂點(diǎn)的入度,保存在indgree數(shù)組中 for (i = 0; i != this->vexnum; i++) { temp = this->arc[i].firstarc; while (temp) { ++this->indegree[temp->adjvex]; temp = temp->next; } } //把入度為0的頂點(diǎn)入棧 for (i = 0; i != this->vexnum; i++) { if (!indegree[i]) { s.push(i); } } //count用于計算輸出的頂點(diǎn)個數(shù) int count=0; while (!s.empty()) {//如果棧為空,則結(jié)束循環(huán) i = s.top(); s.pop();//保存棧頂元素,并且棧頂元素出棧 cout << this->arc[i].data<<" ";//輸出拓?fù)湫蛄? temp = this->arc[i].firstarc; while (temp) { if (!(--this->indegree[temp->adjvex])) {//如果入度減少到為0,則入棧 s.push(temp->adjvex); } temp = temp->next; } ++count; } if (count == this->vexnum) { cout << endl; return true; } cout << "此圖有環(huán),無拓?fù)湫蛄? << endl; return false;//說明這個圖有環(huán) }
現(xiàn)在,我們來介紹第二個算法的思路:
其實(shí)DFS就是深度優(yōu)先搜索,它每次都沿著一條路徑一直往下搜索,知道某個頂點(diǎn)沒有了出度時,就停止遞歸,往回走,所以我們就用DFS的這個思路,我們可以得到一個有向無環(huán)圖的拓?fù)湫蛄?,其?shí)DFS很像Kahn算法的逆過程。具體的代碼實(shí)現(xiàn)如下:
bool Graph_DG::topological_sort_by_dfs() { stack<string> result; int i; bool * visit = new bool[this->vexnum]; //初始化我們的visit數(shù)組 memset(visit, 0, this->vexnum); cout << "基于DFS的拓?fù)渑判驗(yàn)椋? << endl; //開始執(zhí)行DFS算法 for (i = 0; i < this->vexnum; i++) { if (!visit[i]) { dfs(i, visit, result); } } //輸出拓?fù)湫蛄?,因?yàn)槲覀兠看味际钦业搅顺龆葹?的頂點(diǎn)加入棧中, //所以輸出時其實(shí)就要逆序輸出,這樣就是每次都是輸出入度為0的頂點(diǎn) for (i = 0; i < this->vexnum; i++) { cout << result.top() << " "; result.pop(); } cout << endl; return true; } void Graph_DG::dfs(int n, bool * & visit, stack<string> & result) { visit[n] = true; ArcNode * temp = this->arc[n].firstarc; while (temp) { if (!visit[temp->adjvex]) { dfs(temp->adjvex, visit,result); } temp = temp->next; } //由于加入頂點(diǎn)到集合中的時機(jī)是在dfs方法即將退出之時, //而dfs方法本身是個遞歸方法, //僅僅要當(dāng)前頂點(diǎn)還存在邊指向其他不論什么頂點(diǎn), //它就會遞歸調(diào)用dfs方法,而不會退出。 //因此,退出dfs方法,意味著當(dāng)前頂點(diǎn)沒有指向其他頂點(diǎn)的邊了 //,即當(dāng)前頂點(diǎn)是一條路徑上的最后一個頂點(diǎn)。 //換句話說其實(shí)就是此時該頂點(diǎn)出度為0了 result.push(this->arc[n].data); }
兩種算法總結(jié):
對于基于DFS的算法,增加結(jié)果集的條件是:頂點(diǎn)的出度為0。這個條件和Kahn算法中入度為0的頂點(diǎn)集合似乎有著異曲同工之妙,Kahn算法不須要檢測圖是否為DAG,假設(shè)圖為DAG,那么在入度為0的棧為空之后,圖中還存在沒有被移除的邊,這就說明了圖中存在環(huán)路。而基于DFS的算法須要首先確定圖為DAG,當(dāng)然也可以做出適當(dāng)調(diào)整,讓環(huán)路的檢測測和拓?fù)渑判蛲粫r候進(jìn)行,畢竟環(huán)路檢測也可以在DFS的基礎(chǔ)上進(jìn)行。
二者的復(fù)雜度均為O(V+E)。
五、完整的代碼和輸出展示
topological_sort.h文件的代碼
#pragma once //#pragma once是一個比較常用的C/C++雜注, //只要在頭文件的最開始加入這條雜注, //就能夠保證頭文件只被編譯一次。 /* 拓?fù)渑判虮仨毷菍τ邢驁D的操作 算法實(shí)現(xiàn): (1)Kahn算法 (2)DFS算法 采用鄰接表存儲圖 */ #include<iostream> #include<string> #include<stack> using namespace std; //表結(jié)點(diǎn) struct ArcNode { ArcNode * next; //下一個關(guān)聯(lián)的邊 int adjvex; //保存弧尾頂點(diǎn)在頂點(diǎn)表中的下標(biāo) }; struct Vnode { string data; //頂點(diǎn)名稱 ArcNode * firstarc; //第一個依附在該頂點(diǎn)邊 }; class Graph_DG { private: int vexnum; //圖的頂點(diǎn)數(shù) int edge; //圖的邊數(shù) int * indegree; //每條邊的入度情況 Vnode * arc; //鄰接表 public: Graph_DG(int, int); ~Graph_DG(); //檢查輸入邊的頂點(diǎn)是否合法 bool check_edge_value(int,int); //創(chuàng)建一個圖 void createGraph(); //打印鄰接表 void print(); //進(jìn)行拓?fù)渑判?Kahn算法 bool topological_sort(); //進(jìn)行拓?fù)渑判?,DFS算法 bool topological_sort_by_dfs(); void dfs(int n,bool * & visit, stack<string> & result); };
topological_sort.cpp文件代碼
#include"topological_sort.h" Graph_DG::Graph_DG(int vexnum, int edge) { this->vexnum = vexnum; this->edge = edge; this->arc = new Vnode[this->vexnum]; this->indegree = new int[this->vexnum]; for (int i = 0; i < this->vexnum; i++) { this->indegree[i] = 0; this->arc[i].firstarc = NULL; this->arc[i].data = "v" + to_string(i + 1); } } //釋放內(nèi)存空間 Graph_DG::~Graph_DG() { ArcNode * p, *q; for (int i = 0; i < this->vexnum; i++) { if (this->arc[i].firstarc) { p = this->arc[i].firstarc; while (p) { q = p->next; delete p; p = q; } } } delete [] this->arc; delete [] this->indegree; } //判斷我們每次輸入的的邊的信息是否合法 //頂點(diǎn)從1開始編號 bool Graph_DG::check_edge_value(int start, int end) { if (start<1 || end<1 || start>vexnum || end>vexnum) { return false; } return true; } void Graph_DG::createGraph() { int count = 0; int start, end; cout << "輸入每條起點(diǎn)和終點(diǎn)的頂點(diǎn)編號(從1開始編號)" << endl; while (count != this->edge) { cin >> start; cin >> end; //檢查邊是否合法 while (!this->check_edge_value(start, end)) { cout << "輸入的頂點(diǎn)不合法,請重新輸入" << endl; cin >> start; cin >> end; } //聲明一個新的表結(jié)點(diǎn) ArcNode * temp = new ArcNode; temp->adjvex = end - 1; temp->next = NULL; //如果當(dāng)前頂點(diǎn)的還沒有邊依附時, if (this->arc[start - 1].firstarc == NULL) { this->arc[start - 1].firstarc = temp; } else { ArcNode * now = this->arc[start - 1].firstarc; while(now->next) { now = now->next; }//找到該鏈表的最后一個結(jié)點(diǎn) now->next = temp; } ++count; } } void Graph_DG::print() { int count = 0; cout << "圖的鄰接矩陣為:" << endl; //遍歷鏈表,輸出鏈表的內(nèi)容 while (count != this->vexnum) { //輸出鏈表的結(jié)點(diǎn) cout << this->arc[count].data<<" "; ArcNode * temp = this->arc[count].firstarc; while (temp) { cout<<"<"<< this->arc[count].data<<","<< this->arc[temp->adjvex].data<<"> "; temp = temp->next; } cout << "^" << endl; ++count; } } bool Graph_DG::topological_sort() { cout << "圖的拓?fù)湫蛄袨椋? << endl; //棧s用于保存棧為空的頂點(diǎn)下標(biāo) stack<int> s; int i; ArcNode * temp; //計算每個頂點(diǎn)的入度,保存在indgree數(shù)組中 for (i = 0; i != this->vexnum; i++) { temp = this->arc[i].firstarc; while (temp) { ++this->indegree[temp->adjvex]; temp = temp->next; } } //把入度為0的頂點(diǎn)入棧 for (i = 0; i != this->vexnum; i++) { if (!indegree[i]) { s.push(i); } } //count用于計算輸出的頂點(diǎn)個數(shù) int count=0; while (!s.empty()) {//如果棧為空,則結(jié)束循環(huán) i = s.top(); s.pop();//保存棧頂元素,并且棧頂元素出棧 cout << this->arc[i].data<<" ";//輸出拓?fù)湫蛄? temp = this->arc[i].firstarc; while (temp) { if (!(--this->indegree[temp->adjvex])) {//如果入度減少到為0,則入棧 s.push(temp->adjvex); } temp = temp->next; } ++count; } if (count == this->vexnum) { cout << endl; return true; } cout << "此圖有環(huán),無拓?fù)湫蛄? << endl; return false;//說明這個圖有環(huán) } bool Graph_DG::topological_sort_by_dfs() { stack<string> result; int i; bool * visit = new bool[this->vexnum]; //初始化我們的visit數(shù)組 memset(visit, 0, this->vexnum); cout << "基于DFS的拓?fù)渑判驗(yàn)椋? << endl; //開始執(zhí)行DFS算法 for (i = 0; i < this->vexnum; i++) { if (!visit[i]) { dfs(i, visit, result); } } //輸出拓?fù)湫蛄?,因?yàn)槲覀兠看味际钦业搅顺龆葹?的頂點(diǎn)加入棧中, //所以輸出時其實(shí)就要逆序輸出,這樣就是每次都是輸出入度為0的頂點(diǎn) for (i = 0; i < this->vexnum; i++) { cout << result.top() << " "; result.pop(); } cout << endl; return true; } void Graph_DG::dfs(int n, bool * & visit, stack<string> & result) { visit[n] = true; ArcNode * temp = this->arc[n].firstarc; while (temp) { if (!visit[temp->adjvex]) { dfs(temp->adjvex, visit,result); } temp = temp->next; } //由于加入頂點(diǎn)到集合中的時機(jī)是在dfs方法即將退出之時, //而dfs方法本身是個遞歸方法, //僅僅要當(dāng)前頂點(diǎn)還存在邊指向其他不論什么頂點(diǎn), //它就會遞歸調(diào)用dfs方法,而不會退出。 //因此,退出dfs方法,意味著當(dāng)前頂點(diǎn)沒有指向其他頂點(diǎn)的邊了 //,即當(dāng)前頂點(diǎn)是一條路徑上的最后一個頂點(diǎn)。 //換句話說其實(shí)就是此時該頂點(diǎn)出度為0了 result.push(this->arc[n].data); }
main.cpp文件:
#include"topological_sort.h" //檢驗(yàn)輸入邊數(shù)和頂點(diǎn)數(shù)的值是否有效,可以自己推算為啥: //頂點(diǎn)數(shù)和邊數(shù)的關(guān)系是:((Vexnum*(Vexnum - 1)) / 2) < edge bool check(int Vexnum, int edge) { if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge) return false; return true; } int main() { int vexnum; int edge; cout << "輸入圖的頂點(diǎn)個數(shù)和邊的條數(shù):" << endl; cin >> vexnum >> edge; while (!check(vexnum, edge)) { cout << "輸入的數(shù)值不合法,請重新輸入" << endl; cin >> vexnum >> edge; } Graph_DG graph(vexnum, edge); graph.createGraph(); graph.print(); graph.topological_sort(); graph.topological_sort_by_dfs(); system("pause"); return 0; }
輸入:
6 8
1 2
1 3
1 4
3 2
3 5
4 5
6 4
6 5
輸出:
輸入:
13 15
1 2
1 6
1 7
3 1
3 4
4 6
6 5
7 4
7 10
8 7
9 8
10 11
10 12
10 13
12 13
輸出:
以上就是詳解C++實(shí)現(xiàn)拓?fù)渑判蛩惴ǖ脑敿?xì)內(nèi)容,更多關(guān)于C++ 拓?fù)渑判蛩惴ǖ馁Y料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
C++中jsoncpp庫和nlohmann-json庫實(shí)現(xiàn)JSON與字符串類型轉(zhuǎn)換
jsoncpp是ROS自帶的一個JSON庫,它提供了一些函數(shù)來解析和生成JSON數(shù)據(jù),在ROS中,可以使用jsoncpp庫來實(shí)現(xiàn)JSON與字符串類型之間的轉(zhuǎn)換,這篇文章主要介紹了jsoncpp庫和nlohmann-json庫實(shí)現(xiàn)JSON與字符串類型轉(zhuǎn)換,需要的朋友可以參考下2023-08-08C++采用openfilename打開文件對話框用法實(shí)例
這篇文章主要介紹了C++采用openfilename打開文件對話框用法實(shí)例,是C++文件操作中非常實(shí)用的技巧,需要的朋友可以參考下2014-10-10C語言實(shí)現(xiàn)快速排序的方法及優(yōu)化
這篇文章主要介紹了C語言實(shí)現(xiàn)快速排序的方法及優(yōu)化,快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法,下面我們來看一看傳說中的快速排序的特點(diǎn)與效率怎么樣,需要的朋友可以參考下2023-07-07dev-c++創(chuàng)建lib(靜態(tài)鏈接庫)文件的實(shí)現(xiàn)步驟
本文主要介紹了dev-c++創(chuàng)建lib(靜態(tài)鏈接庫)文件的實(shí)現(xiàn)步驟,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06使用c++實(shí)現(xiàn)OpenCV圖像橫向&縱向拼接
這篇文章主要介紹了使用c++實(shí)現(xiàn)OpenCV圖像橫向&縱向拼接,文中有圖像拼接函數(shù),可以實(shí)現(xiàn)如“長圖拼接王”這類小程序的類似功能,大家可以將該函數(shù)封裝在軟件中自由使用2021-08-08