一、基本思路

1、概念定義

• 拓撲序列定義：

• • 若一個由圖中所有點構成的序列 A滿足：對于圖中的每條邊 (x,y)，x在 A中都出現在 y之前，則稱 A是該圖的一個拓撲序列。
• • 人話：始終滿足每條邊的起點在終點前面，從前指向后。

• 

• 注意：如果在有向圖中構成一個環(huán)，則必定無法構成拓撲結構，也可以證明有向無環(huán)圖一定存在拓撲序列，即有向無環(huán)圖=拓撲圖

• 入度：對一個節(jié)點而言，有多少條邊指向自己。

• 出度：對一個節(jié)點而言，有多少條邊指向外面。

二、拓撲序列模板

• 1. 因為拓撲序列都是從前指向后面的，因此當前入度為0的點都可以當做是起點。
• 2. 入度為0，意味著沒有任何一個點在我面前，可以放在最前面的位置。
• 3. 每次遍歷完之后，就可以讓 入度-1，表示前面指向他的確定了一個，直到為0 ，就可以加入序列，這就代表著后面再也沒有指向這個節(jié)點的了。

// 偽代碼
queue <--- 所有入度為0的點
while(queue 不空){
	t = 隊頭；
	枚舉t的所有出邊（t ---> j）{
		j = e[i];
		刪掉t ---> j這條邊，即入度 d[j]--;
		if (d[j] == 0){			// 此時 j 的入度為了 0 ，則可以放在最前面去了
			queue <--- j;		// 入隊
		}
	}
}

拓撲排序 —— 模板題 AcWing 848. 有向圖的拓撲序列
時間復雜度 O(n+m)	n 表示點數，m 表示邊數
bool topsort()
{
    int hh = 0, tt = -1;

    // d[i] 存儲點i的入度
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    // 如果所有點都入隊了，說明存在拓撲序列；否則不存在拓撲序列。
    return tt == n - 1;
}

• 若存在環(huán)，則找不到一個入度為 0 的點，沒有突破口，無法入隊。一個無環(huán)圖，一定存在一個入度為0的點。

三、例題題解

文章來源地址http://www.zghlxwxcb.cn/news/detail-767398.html

// java題解實現
import java.util.*;

public class Main{
    static int N = 100010;
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] h = new int[N];
    static int idx = 0;
    static int hh = 0;
    static int tt = -1;
    static int[] q = new int[N];
    static int[] d = new int[N];                // 表示入度大小，為了后面進行入度逐漸減小做準備
    static int n,m;
    
    static void add(int a, int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    
    static boolean topsort(){
        
        for(int i = 1; i <= n; i++){        // 首先將入度為0的節(jié)點加入隊列中
            if(d[i] == 0){
                q[++tt] = i;
            }
        }
        
        while(hh <= tt){
            int temp = q[hh++];             // 此處僅僅是對所控制的隊列進行了首節(jié)點后移
            
            for(int i = h[temp]; i != -1; i = ne[i]){
                int j = e[i];               // 遍歷當前隊列節(jié)點能到達的節(jié)點
                d[j] --;                    // 有點指向，那必然不為0，遍歷過去之后，就可以排除這個點指向了

                if(d[j] == 0){              // 如果入度后面為0了，說明沒有點指向他了
                    q[++tt] = j;             // 入度為0了，后面的遍歷沒有指向他的了，所以可以加入隊列了
                }
            }
        }
        
        return tt == n - 1;                  // 判斷是不是隊列已經將n個節(jié)點存在q中了，因為q從0開始存儲的
    }

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        
        n = in.nextInt();
        m = in.nextInt();
        
        for(int i = 0; i < N; i++){
            h[i] = -1;
            d[i] = 0;
        }
        
        for(int i = 0; i < m; i++){
            int a = in.nextInt();
            int b = in.nextInt();
            add(a, b);
            d[b]++;                         // 有節(jié)點指向 b故此需要進行入度+1
        }
        
        if(topsort()){
            for(int i = 0; i < n; i++){
                System.out.print(q[i] + " ");       // 盡管其中的hh指針已經移到后面，但是隊列中始終存儲著序列
            }
        }else{
            System.out.println("-1");
        }
        
    }
}

到了這里，關于二十一、搜索與圖論——拓撲序列（有向圖）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！