數(shù)據(jù)結(jié)構(gòu)---拓撲排序詳解

2019-11-06 06:30:00

字體：大中小

供稿：網(wǎng)友

前言 The time of test,family is best. Name:Willam Time:2017/3/6

1、拓撲排序的介紹

對一個有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u,v)∈E(G)，則u在線性序列中出現(xiàn)在v之前。拓撲排序?qū)?yīng)施工的流程圖具有特別重要的作用，它可以決定哪些子工程必須要先執(zhí)行，哪些子工程要在某些工程執(zhí)行后才可以執(zhí)行。為了形象地反映出整個工程中各個子工程(活動)之間的先后關(guān)系，可用一個有向圖來表示，圖中的頂點代表活動(子工程)，圖中的有向邊代表活動的先后關(guān)系，即有向邊的起點的活動是終點活動的前序活動，只有當起點活動完成之后，其終點活動才能進行。通常，我們把這種頂點表示活動、邊表示活動間先后關(guān)系的有向圖稱做頂點活動網(wǎng)(Activity On Vertex network)，簡稱AOV網(wǎng)。一個AOV網(wǎng)應(yīng)該是一個有向無環(huán)圖，即不應(yīng)該帶有回路，因為若帶有回路，則回路上的所有活動都無法進行（對于數(shù)據(jù)流來說就是死循環(huán)）。在AOV網(wǎng)中，若不存在回路，則所有活動可排列成一個線性序列，使得每個活動的所有前驅(qū)活動都排在該活動的前面，我們把此序列叫做拓撲序列(Topological order)，由AOV網(wǎng)構(gòu)造拓撲序列的過程叫做拓撲排序(Topological sort)。AOV網(wǎng)的拓撲序列不是唯一的，滿足上述定義的任一線性序列都稱作它的拓撲序列。

2、拓撲排序的實現(xiàn)步驟

在有向圖中選一個沒有前驅(qū)的頂點并且輸出從圖中刪除該頂點和所有以它為尾的弧（白話就是：刪除所有和它有關(guān)的邊）重復(fù)上述兩步，直至所有頂點輸出，或者當前圖中不存在無前驅(qū)的頂點為止，后者代表我們的有向圖是有環(huán)的，因此，也可以通過拓撲排序來判斷一個圖是否有環(huán)。

3、拓撲排序示例手動實現(xiàn)

如果我們有如下的一個有向無環(huán)圖，我們需要對這個圖的頂點進行拓撲排序，過程如下：這里寫圖片描述

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

然后，我們繼續(xù)尋找沒有前驅(qū)的頂點，發(fā)現(xiàn)V1沒有前驅(qū)，所以輸出V1，刪除和V1有關(guān)的邊，得到下圖的結(jié)果：這里寫圖片描述

然后，我們又發(fā)現(xiàn)V4和V3都是沒有前驅(qū)的，那么我們就隨機選取一個頂點輸出（具體看你實現(xiàn)的算法和圖存儲結(jié)構(gòu)），我們輸出V4，得到如下圖結(jié)果：這里寫圖片描述

然后，我們輸出沒有前驅(qū)的頂點V3，得到如下結(jié)果：這里寫圖片描述

然后，我們分別輸出V5和V2，最后全部頂點輸出完成，該圖的一個拓撲序列為：

v6–>v1—->v4—>v3—>v5—>v2

4、拓撲排序的代碼實現(xiàn)

下面，我們將用兩種方法來實現(xiàn)我么的拓撲排序：

Kahn算法基于DFS的拓撲排序算法

首先我們先介紹第一個算法的思路： Kahn的算法的思路其實就是我們之前那個手動展示的拓撲排序的實現(xiàn)，我們先使用一個棧保存入度為0 的頂點，然后輸出棧頂元素并且將和棧頂元素有關(guān)的邊刪除，減少和棧頂元素有關(guān)的頂點的入度數(shù)量并且把入度減少到0的頂點也入棧。具體的代碼如下：

bool Graph_DG::topological_sort() { cout << "圖的拓撲序列為：" << endl; //棧s用于保存棧為空的頂點下標 stack<int> s; int i; ArcNode * temp; //計算每個頂點的入度，保存在indgree數(shù)組中 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用于計算輸出的頂點個數(shù) int count=0; while (!s.empty()) {//如果棧為空，則結(jié)束循環(huán) 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 << "此圖有環(huán)，無拓撲序列" << endl; return false;//說明這個圖有環(huán)}

現(xiàn)在，我們來介紹第二個算法的思路：其實DFS就是深度優(yōu)先搜索，它每次都沿著一條路徑一直往下搜索，知道某個頂點沒有了出度時，就停止遞歸，往回走，所以我們就用DFS的這個思路，我們可以得到一個有向無環(huán)圖的拓撲序列，其實DFS很像Kahn算法的逆過程。具體的代碼實現(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的拓撲排序為：" << endl; //開始執(zhí)行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方法本身是個遞歸方法， //僅僅要當前頂點還存在邊指向其他不論什么頂點， //它就會遞歸調(diào)用dfs方法，而不會退出。 //因此，退出dfs方法，意味著當前頂點沒有指向其他頂點的邊了 //，即當前頂點是一條路徑上的最后一個頂點。 //換句話說其實就是此時該頂點出度為0了 result.push(this->arc[n].data);}

兩種算法總結(jié)：對于基于DFS的算法，增加結(jié)果集的條件是：頂點的出度為0。這個條件和Kahn算法中入度為0的頂點集合似乎有著異曲同工之妙，Kahn算法不須要檢測圖是否為DAG，假設(shè)圖為DAG，那么在入度為0的棧為空之后，圖中還存在沒有被移除的邊，這就說明了圖中存在環(huán)路。而基于DFS的算法須要首先確定圖為DAG，當然也可以做出適當調(diào)整，讓環(huán)路的檢測測和拓撲排序同一時候進行，畢竟環(huán)路檢測也可以在DFS的基礎(chǔ)上進行。二者的復(fù)雜度均為O(V+E)。

5、完整的代碼和輸出展示

topological_sort.h文件的代碼/************************************************************//* 程序作者：Willam *//* 程序完成時間：2017/3/6 *//* 有任何問題請聯(lián)系：2930526477@QQ.com *//************************************************************///@盡量寫出完美的程序#PRagma once//#pragma once是一個比較常用的C/C++雜注，//只要在頭文件的最開始加入這條雜注，//就能夠保證頭文件只被編譯一次。/*拓撲排序必須是對有向圖的操作算法實現(xiàn)：（1）Kahn算法（2）DFS算法采用鄰接表存儲圖*/#include<iostream>#include<string>#include<stack>using namespace std;//表結(jié)點struct ArcNode { ArcNode * next; //下一個關(guān)聯(lián)的邊 int adjvex; //保存弧尾頂點在頂點表中的下標};struct Vnode { string data; //頂點名稱 ArcNode * firstarc; //第一個依附在該頂點邊};class Graph_DG {private: int vexnum; //圖的頂點數(shù) int edge; //圖的邊數(shù) int * indegree; //每條邊的入度情況 Vnode * arc; //鄰接表public: Graph_DG(int, int); ~Graph_DG(); //檢查輸入邊的頂點是否合法 bool check_edge_value(int,int); //創(chuàng)建一個圖 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); }}//釋放內(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;}//判斷我們每次輸入的的邊的信息是否合法//頂點從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; } //聲明一個新的表結(jié)點 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; }//找到該鏈表的最后一個結(jié)點 now->next = temp; } ++count; }}void Graph_DG::print() { int count = 0; cout << "圖的鄰接矩陣為：" << endl; //遍歷鏈表，輸出鏈表的內(nèi)容 while (count != this->vexnum) { //輸出鏈表的結(jié)點 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數(shù)組中 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用于計算輸出的頂點個數(shù) int count=0; while (!s.empty()) {//如果棧為空，則結(jié)束循環(huán) 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 << "此圖有環(huán)，無拓撲序列" << 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的拓撲排序為：" << endl; //開始執(zhí)行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方法本身是個遞歸方法， //僅僅要當前頂點還存在邊指向其他不論什么頂點， //它就會遞歸調(diào)用dfs方法，而不會退出。 //因此，退出dfs方法，意味著當前頂點沒有指向其他頂點的邊了 //，即當前頂點是一條路徑上的最后一個頂點。 //換句話說其實就是此時該頂點出度為0了 result.push(this->arc[n].data);}main.cpp文件：#include"topological_sort.h"http://檢驗輸入邊數(shù)和頂點數(shù)的值是否有效，可以自己推算為啥：//頂點數(shù)和邊數(shù)的關(guān)系是：((Vexnum*(Vexnum - 1)) / 2) < edgebool 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 << "輸入圖的頂點個數(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 81 21 31 43 23 54 56 46 5

輸出：這里寫圖片描述