歡迎拜訪：霧里看山-CSDN博客
本篇主題：算法思想 之 拓撲排序問題
發布時間：2025.8.4
隸屬專欄：算法

算法介紹

拓撲排序（Topological Sorting）是針對有向無環圖（DAG, Directed Acyclic Graph） 的一種重要排序算法，其核心是將圖中所有頂點按照一定規則排列，使得對于圖中任意一條有向邊 (u, v)，頂點 u 都排在頂點 v 之前。

拓撲排序的本質是解決 “依賴關系” 問題—— 當任務 / 節點之間存在先后依賴（如 “必須完成 A 才能做 B”）時，通過拓撲排序可以找到一個合法的執行順序；若圖中存在環（如 “A 依賴 B，B 依賴 C，C 依賴 A”），則不存在拓撲排序（此時可用于檢測環）。

核心原理

拓撲排序的關鍵是 “消除入度為 0 的節點”：

• 入度（In-degree）：頂點被指向的邊的數量（即 “前驅節點” 的數量）。
• 入度為 0 的節點：沒有前驅依賴，可優先執行 / 輸出。
• 流程：反復找到入度為 0 的節點，輸出該節點后移除其所有出邊（減少其鄰接節點的入度），直至所有節點被輸出（合法拓撲序）或無法找到入度為 0 的節點（存在環，無拓撲序）。

適用場景

拓撲排序廣泛應用于 “存在依賴關系” 的場景：

• 課程安排：修課需先完成先修課程（如 “修算法前必須修數據結構”）。
• 任務調度：任務 A 必須在任務 B 之前執行。
• 編譯依賴：程序模塊的編譯順序（被依賴的模塊先編譯）。
• 依賴包安裝：軟件包的安裝順序（依賴的包先安裝）。

實現步驟(Kahn 算法)

Kahn 算法是最直觀的拓撲排序實現，利用隊列存儲 “入度為 0 的節點”，通過層次遍歷逐步消除依賴。

步驟：

• 構建鄰接表：存儲圖的邊關系（u -> v 表示 u 是 v 的前驅）。
• 計算入度數組：記錄每個節點的入度（初始值）。
• 初始化隊列：將所有入度為 0 的節點加入隊列（這些節點無依賴，可優先輸出）。
• BFS 遍歷：
  • 從隊列中取出一個節點 u，加入拓撲序結果。
  • 遍歷 u 的所有鄰接節點 v，將 v 的入度減 1（因為 u 已被 “消除”，v 的一個依賴 被滿足）。
  • 若 v 的入度減為 0，將其加入隊列（此時 v 已無依賴）。
• 檢查結果：若拓撲序的長度等于節點總數，說明是合法 DAG（存在拓撲序）；否則圖中存在環（無拓撲序）。

例題

課程表

題目鏈接

207. 課程表

題目描述

你這個學期必須選修 numCourses 門課程，記為 0 到 numCourses - 1 。

在選修某些課程之前需要一些先修課程。 先修課程按數組 prerequisites 給出，其中 prerequisites[i] = [ai, bi] ，表示如果要學習課程 ai 則 必須 先學習課程 bi 。

• 例如，先修課程對 [0, 1] 表示：想要學習課程 0 ，你需要先完成課程 1 。

請你判斷是否可能完成所有課程的學習？如果可以，返回 true ；否則，返回 false 。

示例 1：

輸入：numCourses = 2, prerequisites = [[1,0]]
輸出：true
解釋：總共有 2 門課程。學習課程 1 之前，你需要完成課程 0 。這是可能的。

示例 2：

輸入：numCourses = 2, prerequisites = [[1,0],[0,1]]
輸出：false
解釋：總共有 2 門課程。學習課程 1 之前，你需要先完成?課程 0 ；并且學習課程 0 之前，你還應先完成課程 1 。這是不可能的。

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i] 中的所有課程對 互不相同

算法思路

標準拓撲排序問題，直接使用算法介紹中的實現步驟進行即可。

代碼實現

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {//1. 準備工作unordered_map<int, vector<int>> edges; // 鄰接表存圖vector<int> in(numCourses);// 保存每一個點的入度//2. 建圖for(auto& e : prerequisites){int a = e[0], b = e[1];// b->aedges[b].push_back(a);in[a]++;}//3. 拓撲排序queue<int> q;// (1). 把所有入度為0的點存進去for(int i = 0; i < numCourses; i++){if(in[i] == 0)q.push(i);}// (2). bfswhile(q.size()){int n = q.front();q.pop();for(int a : edges[n]){in[a]--;if(in[a] == 0)q.push(a);}}// (3). 判斷是否有環for(int i : in){if(i)return false;}return true;}
};

課程表 II

題目鏈接

210. 課程表 II

題目描述

現在你總共有 numCourses 門課需要選，記為 0 到 numCourses - 1。給你一個數組 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在選修課程 ai 前 必須 先選修 bi 。

• 例如，想要學習課程 0 ，你需要先完成課程 1 ，我們用一個匹配來表示：[0,1] 。

返回你為了學完所有課程所安排的學習順序。可能會有多個正確的順序，你只要返回 任意一種 就可以了。如果不可能完成所有課程，返回 一個空數組 。

示例 1：

輸入：numCourses = 2, prerequisites = [[1,0]]
輸出：[0,1]
解釋：總共有 2 門課程。要學習課程 1，你需要先完成課程 0。因此，正確的課程順序為 [0,1] 。

示例 2：

輸入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
輸出：[0,2,1,3]
解釋：總共有 4 門課程。要學習課程 3，你應該先完成課程 1 和課程 2。并且課程 1 和課程 2 都應該排在課程 0 之后。
因此，一個正確的課程順序是 [0,1,2,3] 。另一個正確的排序是 [0,2,1,3] 。

示例 3：

輸入：numCourses = 1, prerequisites = []
輸出：[0]

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• 所有[ai, bi] 互不相同

算法思路

整體思路和上一題一樣，多一個數組保存結果即可

代碼實現

class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {//1. 準備工作unordered_map<int, vector<int>> edges; // 鄰接表存圖vector<int> in(numCourses);// 保存每一個點的入度vector<int> ret;//2. 建圖for(auto& e : prerequisites){int a = e[0], b = e[1];// b->aedges[b].push_back(a);in[a]++;}//3. 拓撲排序queue<int> q;// (1). 把所有入度為0的點存進去for(int i = 0; i < numCourses; i++){if(in[i] == 0)q.push(i);}// (2). bfswhile(q.size()){int n = q.front();q.pop();ret.push_back(n);for(int a : edges[n]){in[a]--;if(in[a] == 0)q.push(a);}}// (3). 判斷是否有環for(int i : in){if(i)return vector<int>();}return ret;}
};

火星詞典

題目鏈接

LCR 114. 火星詞典

題目描述

現有一種使用英語字母的外星文語言，這門語言的字母順序與英語順序不同。

給定一個字符串列表 words ，作為這門語言的詞典，words 中的字符串已經 按這門新語言的字母順序進行了排序 。

請你根據該詞典還原出此語言中已知的字母順序，并 按字母遞增順序 排列。若不存在合法字母順序，返回 "" 。若存在多種可能的合法字母順序，返回其中 任意一種 順序即可。

字符串 s 字典順序小于 字符串 t 有兩種情況：

• 在第一個不同字母處，如果 s 中的字母在這門外星語言的字母順序中位于 t 中字母之前，那么 s 的字典順序小于 t 。
• 如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 時，s 的字典順序也小于 t 。

示例 1:

輸入：words = [“wrt”,“wrf”,“er”,“ett”,“rftt”]
輸出：“wertf”

示例 2：

輸入：words = [“z”,“x”]
輸出：“zx”

示例 3：

輸入：words = [“z”,“x”,“z”]
輸出：“”
解釋：不存在合法字母順序，因此返回 “”。

提示：

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] 僅由小寫英文字母組成

算法思路

1. 先根據字典兩兩比較字母之間的先后順序，建立有向無環圖
   a. 兩層 for 循環枚舉出所有的兩個字符串的組合；
   b. 然后利用指針，根據字典序規則找出信息。
2. 根據有向無環圖做拓撲排序找出字母的順序

代碼實現

class Solution {unordered_map<char, unordered_set<char>> edges;// 鄰接表存圖unordered_map<char,int> in;// 保存每一個點的入度bool check = false;
public:string alienOrder(vector<string>& words) {for(auto& s : words)for(auto& c : s)in[c] = 0;int n = words.size();for(int i = 0; i < n; i++){for(int j = i+1; j < n; j++){add(words[i],words[j]);if(check) return "";}}string ret;queue<char> q;for(auto& [a,b] : in){if(b == 0)q.push(a);}while(q.size()){char c = q.front();q.pop();ret += c;for(char ch : edges[c]){in[ch]--;if(in[ch] == 0)q.push(ch);}}for(auto& [a,b]:in)if(b != 0)return "";return ret;}void add(const string& s1, const string& s2){int n = min(s1.size(), s2.size());int i = 0;for(; i < n; i++){if(s1[i] != s2[i]) {char a = s1[i], b = s2[i];// a->b;if(!edges.count(a) || !edges[a].count(b)){edges[a].insert(b);in[b]++;}break;}}if(i==s2.size() && i < s1.size())check = true;}
};

?? 寫在最后：以上內容是我在學習以后得一些總結和概括，如有錯誤或者需要補充的地方歡迎各位大佬評論或者私信我交流！！！