C++圖的拓撲排序是什么

本文小編為大家詳細介紹“C++圖的拓撲排序是什么”，內容詳細，步驟清晰，細節處理妥當，希望這篇“C++圖的拓撲排序是什么”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

一、前言

且該序列必須滿足下面兩個條件：

1. 每個頂點出現且只出現一次。

2. 若存在一條從頂點 x到頂點 y的路徑，那么在序列中頂點 x 出現在頂點 y的前面。

拓撲排序只適用于 AOV網 （有向無環圖）

若圖中有環，則一定不存在拓撲序。

可以證明，一個有向無環圖，一定存在一個拓撲序列。有向無環圖，又被稱為拓撲圖。

入度: 即有多少條邊指向自己這個節點。

出度: 即有多少條邊從自己這個節點指出去。

二、算法流程

算法流程：

用隊列來執行 ，初始化所有入度為0的頂點入隊。

主要由以下兩步循環執行，直到不存在入度為 0 的頂點為止

選擇一個入度為 0 的頂點，并將它輸出；

刪除圖中從頂點連出的所有邊

循環結束

若輸出的頂點數小于圖中的頂點數，則表示該圖存在回路，即無法拓撲排序，

否則，輸出的就是拓撲序列 （不唯一）

模板如下：

1.數組模擬隊列實現拓撲排序

bool topsort()
{
    int hh = 0, tt = -1;
    // in[i] 存儲點i的入度
    for (int i = 1; i <= n; i ++ )// 將所有入度為0的點加入隊列
        if (in[i]==0)
            top[ ++ tt] = i;
    while (hh <= tt)
    {
        int t = top[hh ++ ];//找到入度為0的隊頭
  //遍歷一下以t為頭節點的的單鏈表，給每一個結點都要減去1，并再次找到入度為0的點
        for (int i = h[t]; i != -1; i = ne[i])
        {
        // 遍歷 t 點的出邊
            int j = e[i];
            if (-- in[j] == 0)//將入度減1,如果 j 入度為0，加入隊列當中
                top[ ++ tt] = j;
        }
    }
    // 如果所有點都入隊了，說明存在拓撲序列；否則不存在拓撲序列。
    return tt == n - 1;
}

2.使用STL queue實現拓撲排序

bool topsort(){
    queue<int> q;
    int t;
    for(int i = 1;i <= n; ++i)// 將所有入度為0的點加入隊列
        if(in[i] == 0) q.push(i);
    while(q.size()){
        t = q.front();//每次取出隊列的首部
        top[cnt] = t;//加入到 拓撲序列中
        cnt ++; // 序列中的元素 ++
        q.pop();
        for(int i = h[t];i != -1; i = ne[i]){
            // 遍歷 t 點的出邊
            int j = e[i];
            in[j] --;// j 的入度 --
            if(in[j] == 0) q.push(j); //如果 j 入度為0，加入隊列當中
        }
    }
    if(cnt < n) return 0;
    else return 1;
}

時間復雜度 O(n+m), n表示點數，m表示邊數

三、有向圖的拓撲排序

給定一個 n 個點 m 條邊的有向圖，點的編號是 1 到 n，圖中可能存在重邊和自環。

請輸出任意一個該有向圖的拓撲序列，如果拓撲序列不存在，則輸出 −1。

思路

我們每次找到入讀為0的點，然后把他插入到隊列里，然后將這個點刪除，這也就意味著這個點連接的下一個點（可能是多個）的入度就會減1。

這個時候，我們就進入了下一輪。

我們因為前面將一個點刪除了，那么它指向的點的入度就會都減去1，所以，就會出現新的點的入度為0，這個點顯然是因為它的入度小，所以它理所應當的排在拓撲序里面在第二位。當前面的一個點沒有了被刪除了，那它就要首當其沖了。

和圖的BFS思路很像，但是加了搜索的規則（即入度為零的先被搜索）可以看點這里

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 代表每個元素的入度
// top是拓撲排序的序列，cnt代表top中有多少個元素
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的點加入隊列
        if(in[i] == 0) q.push(i);
    while(q.size()){
        t = q.front();//每次取出隊列的首部
        top[cnt] = t;//加入到 拓撲序列中
        cnt ++; // 序列中的元素 ++
        q.pop();
        for(int i = h[t];i != -1; i = ne[i]){
            // 遍歷 t 點的出邊
            int j = e[i];
            in[j] --;// j 的入度 --
            if(in[j] == 0) q.push(j); //如果 j 入度為0，加入隊列當中
        }
    }
    if(cnt < n) return 0;
    else return 1;
}
int main(){
    int a,b;
    cin >> n >> m;
    memset(h,-1,sizeof h);//給頭節點賦值為-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;
}

讀到這里，這篇“C++圖的拓撲排序是什么”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。