溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關C++如何實現拓撲排序算法，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
拓撲排序對應施工的流程圖具有特別重要的作用，它可以決定哪些子工程必須要先執行，哪些子工程要在某些工程執行后才可以執行。為了形象地反映出整個工程中各個子工程(活動)之間的先后關系，可用一個有向圖來表示，圖中的頂點代表活動(子工程)，圖中的有向邊代表活動的先后關系，即有向邊的起點的活動是終點活動的前序活動，只有當起點活動完成之后，其終點活動才能進行。通常，我們把這種頂點表示活動、邊表示活動間先后關系的有向圖稱做頂點活動網(Activity On Vertex network)，簡稱AOV網。
一個AOV網應該是一個有向無環圖，即不應該帶有回路，因為若帶有回路，則回路上的所有活動都無法進行（對于數據流來說就是死循環）。在AOV網中，若不存在回路，則所有活動可排列成一個線性序列，使得每個活動的所有前驅活動都排在該活動的前面，我們把此序列叫做拓撲序列(Topological order)，由AOV網構造拓撲序列的過程叫做拓撲排序(Topological sort)。AOV網的拓撲序列不是唯一的，滿足上述定義的任一線性序列都稱作它的拓撲序列。
1.在有向圖中選一個沒有前驅的頂點并且輸出
2.從圖中刪除該頂點和所有以它為尾的弧（白話就是：刪除所有和它有關的邊）
3.重復上述兩步，直至所有頂點輸出，或者當前圖中不存在無前驅的頂點為止，后者代表我們的有向圖是有環的，因此，也可以通過拓撲排序來判斷一個圖是否有環。
如果我們有如下的一個有向無環圖，我們需要對這個圖的頂點進行拓撲排序，過程如下：
首先，我們發現V6和v1是沒有前驅的，所以我們就隨機選去一個輸出，我們先輸出V6，刪除和V6有關的邊，得到如下圖結果：
然后，我們繼續尋找沒有前驅的頂點，發現V1沒有前驅，所以輸出V1，刪除和V1有關的邊，得到下圖的結果：
然后，我們又發現V4和V3都是沒有前驅的，那么我們就隨機選取一個頂點輸出（具體看你實現的算法和圖存儲結構），我們輸出V4，得到如下圖結果：
然后，我們輸出沒有前驅的頂點V3，得到如下結果：
然后，我們分別輸出V5和V2，最后全部頂點輸出完成，該圖的一個拓撲序列為：
v6–>v1—->v4—>v3—>v5—>v2
下面，我們將用兩種方法來實現我么的拓撲排序：
1.Kahn算法
2.基于DFS的拓撲排序算法
首先我們先介紹第一個算法的思路：
Kahn的算法的思路其實就是我們之前那個手動展示的拓撲排序的實現，我們先使用一個棧保存入度為0 的頂點，然后輸出棧頂元素并且將和棧頂元素有關的邊刪除，減少和棧頂元素有關的頂點的入度數量并且把入度減少到0的頂點也入棧。具體的代碼如下：
bool Graph_DG::topological_sort() {
cout << "圖的拓撲序列為：" << endl;
//棧s用于保存棧為空的頂點下標
stack<int> s;
int i;
ArcNode * temp;
//計算每個頂點的入度，保存在indgree數組中
for (i = 0; i != this->vexnum; i++) {
temp = this->arc[i].firstarc;
while (temp) {
++this->indegree[temp->adjvex];
temp = temp->next;
}
}
//把入度為0的頂點入棧
for (i = 0; i != this->vexnum; i++) {
if (!indegree[i]) {
s.push(i);
}
}
//count用于計算輸出的頂點個數
int count=0;
while (!s.empty()) {//如果棧為空，則結束循環
i = s.top();
s.pop();//保存棧頂元素，并且棧頂元素出棧
cout << this->arc[i].data<<" ";//輸出拓撲序列
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 << "此圖有環，無拓撲序列" << endl;
return false;//說明這個圖有環
}現在，我們來介紹第二個算法的思路：
其實DFS就是深度優先搜索，它每次都沿著一條路徑一直往下搜索，知道某個頂點沒有了出度時，就停止遞歸，往回走，所以我們就用DFS的這個思路，我們可以得到一個有向無環圖的拓撲序列，其實DFS很像Kahn算法的逆過程。具體的代碼實現如下：
bool Graph_DG::topological_sort_by_dfs() {
stack<string> result;
int i;
bool * visit = new bool[this->vexnum];
//初始化我們的visit數組
memset(visit, 0, this->vexnum);
cout << "基于DFS的拓撲排序為：" << endl;
//開始執行DFS算法
for (i = 0; i < this->vexnum; i++) {
if (!visit[i]) {
dfs(i, visit, result);
}
}
//輸出拓撲序列，因為我們每次都是找到了出度為0的頂點加入棧中，
//所以輸出時其實就要逆序輸出，這樣就是每次都是輸出入度為0的頂點
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;
}
//由于加入頂點到集合中的時機是在dfs方法即將退出之時，
//而dfs方法本身是個遞歸方法，
//僅僅要當前頂點還存在邊指向其他不論什么頂點，
//它就會遞歸調用dfs方法，而不會退出。
//因此，退出dfs方法，意味著當前頂點沒有指向其他頂點的邊了
//，即當前頂點是一條路徑上的最后一個頂點。
//換句話說其實就是此時該頂點出度為0了
result.push(this->arc[n].data);
}兩種算法總結：
對于基于DFS的算法，增加結果集的條件是：頂點的出度為0。這個條件和Kahn算法中入度為0的頂點集合似乎有著異曲同工之妙，Kahn算法不須要檢測圖是否為DAG，假設圖為DAG，那么在入度為0的棧為空之后，圖中還存在沒有被移除的邊，這就說明了圖中存在環路。而基于DFS的算法須要首先確定圖為DAG，當然也可以做出適當調整，讓環路的檢測測和拓撲排序同一時候進行，畢竟環路檢測也可以在DFS的基礎上進行。
二者的復雜度均為O(V+E)。
topological_sort.h文件的代碼
#pragma once
//#pragma once是一個比較常用的C/C++雜注，
//只要在頭文件的最開始加入這條雜注，
//就能夠保證頭文件只被編譯一次。
/*
拓撲排序必須是對有向圖的操作
算法實現：
（1）Kahn算法
（2）DFS算法
采用鄰接表存儲圖
*/
#include<iostream>
#include<string>
#include<stack>
using namespace std;
//表結點
struct ArcNode {
ArcNode * next; //下一個關聯的邊
int adjvex; //保存弧尾頂點在頂點表中的下標
};
struct Vnode {
string data; //頂點名稱
ArcNode * firstarc; //第一個依附在該頂點邊
};
class Graph_DG {
private:
int vexnum; //圖的頂點數
int edge; //圖的邊數
int * indegree; //每條邊的入度情況
Vnode * arc; //鄰接表
public:
Graph_DG(int, int);
~Graph_DG();
//檢查輸入邊的頂點是否合法
bool check_edge_value(int,int);
//創建一個圖
void createGraph();
//打印鄰接表
void print();
//進行拓撲排序,Kahn算法
bool topological_sort();
//進行拓撲排序，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);
}
}
//釋放內存空間
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;
}
//判斷我們每次輸入的的邊的信息是否合法
//頂點從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 << "輸入每條起點和終點的頂點編號（從1開始編號）" << endl;
while (count != this->edge) {
cin >> start;
cin >> end;
//檢查邊是否合法
while (!this->check_edge_value(start, end)) {
cout << "輸入的頂點不合法，請重新輸入" << endl;
cin >> start;
cin >> end;
}
//聲明一個新的表結點
ArcNode * temp = new ArcNode;
temp->adjvex = end - 1;
temp->next = NULL;
//如果當前頂點的還沒有邊依附時，
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;
}//找到該鏈表的最后一個結點
now->next = temp;
}
++count;
}
}
void Graph_DG::print() {
int count = 0;
cout << "圖的鄰接矩陣為：" << endl;
//遍歷鏈表，輸出鏈表的內容
while (count != this->vexnum) {
//輸出鏈表的結點
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 << "圖的拓撲序列為：" << endl;
//棧s用于保存棧為空的頂點下標
stack<int> s;
int i;
ArcNode * temp;
//計算每個頂點的入度，保存在indgree數組中
for (i = 0; i != this->vexnum; i++) {
temp = this->arc[i].firstarc;
while (temp) {
++this->indegree[temp->adjvex];
temp = temp->next;
}
}
//把入度為0的頂點入棧
for (i = 0; i != this->vexnum; i++) {
if (!indegree[i]) {
s.push(i);
}
}
//count用于計算輸出的頂點個數
int count=0;
while (!s.empty()) {//如果棧為空，則結束循環
i = s.top();
s.pop();//保存棧頂元素，并且棧頂元素出棧
cout << this->arc[i].data<<" ";//輸出拓撲序列
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 << "此圖有環，無拓撲序列" << endl;
return false;//說明這個圖有環
}
bool Graph_DG::topological_sort_by_dfs() {
stack<string> result;
int i;
bool * visit = new bool[this->vexnum];
//初始化我們的visit數組
memset(visit, 0, this->vexnum);
cout << "基于DFS的拓撲排序為：" << endl;
//開始執行DFS算法
for (i = 0; i < this->vexnum; i++) {
if (!visit[i]) {
dfs(i, visit, result);
}
}
//輸出拓撲序列，因為我們每次都是找到了出度為0的頂點加入棧中，
//所以輸出時其實就要逆序輸出，這樣就是每次都是輸出入度為0的頂點
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;
}
//由于加入頂點到集合中的時機是在dfs方法即將退出之時，
//而dfs方法本身是個遞歸方法，
//僅僅要當前頂點還存在邊指向其他不論什么頂點，
//它就會遞歸調用dfs方法，而不會退出。
//因此，退出dfs方法，意味著當前頂點沒有指向其他頂點的邊了
//，即當前頂點是一條路徑上的最后一個頂點。
//換句話說其實就是此時該頂點出度為0了
result.push(this->arc[n].data);
}main.cpp文件：
#include"topological_sort.h"
//檢驗輸入邊數和頂點數的值是否有效，可以自己推算為啥：
//頂點數和邊數的關系是：((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 << "輸入圖的頂點個數和邊的條數：" << endl;
cin >> vexnum >> edge;
while (!check(vexnum, edge)) {
cout << "輸入的數值不合法，請重新輸入" << 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++如何實現拓撲排序算法”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
