首頁 > 軟體

詳解C++實現拓撲排序演演算法

2021-06-11 19:00:56

一、拓撲排序的介紹

拓撲排序對應施工的流程圖具有特別重要的作用,它可以決定哪些子工程必須要先執行,哪些子工程要在某些工程執行後才可以執行。為了形象地反映出整個工程中各個子工程(活動)之間的先後關係,可用一個有向圖來表示,圖中的頂點代表活動(子工程),圖中的有向邊代表活動的先後關係,即有向邊的起點的活動是終點活動的前序活動,只有當起點活動完成之後,其終點活動才能進行。通常,我們把這種頂點表示活動、邊表示活動間先後關係的有向圖稱做頂點活動網(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++實現拓撲排序演演算法的詳細內容,更多關於C++ 拓撲排序演演算法的資料請關注it145.com其它相關文章!


IT145.com E-mail:sddin#qq.com