1. 拓?fù)渑判驈囊蕾囮P(guān)系到執(zhí)行順序如果你寫(xiě)過(guò)稍微復(fù)雜一點(diǎn)的程序或者處理過(guò)有依賴關(guān)系的任務(wù)比如“編譯項(xiàng)目前需要先安裝依賴庫(kù)”、“課程B需要先修課程A”那你其實(shí)已經(jīng)摸到了拓?fù)渑判虻拈T(mén)檻。它不是什么高深莫測(cè)的算法而是一個(gè)解決“順序”問(wèn)題的樸素又強(qiáng)大的工具。簡(jiǎn)單說(shuō)拓?fù)渑判蚓褪墙o一堆有前后依賴關(guān)系的事情排出一個(gè)可行的執(zhí)行順序確保你在做任何一件事之前它所有依賴的前置條件都已經(jīng)完成了。想象一下你早上起床到出門(mén)的流程穿襪子必須在穿鞋之前但穿襪子和刷牙可以同時(shí)進(jìn)行如果技術(shù)允許。拓?fù)渑判蛞傻木褪菐湍憷砬暹@些動(dòng)作的先后順序或者告訴你由于“穿鞋必須在穿襪子之前穿襪子必須在穿鞋之前”這種循環(huán)依賴今天你根本出不了門(mén)。在計(jì)算機(jī)世界里它的應(yīng)用場(chǎng)景無(wú)處不在編譯器確定源文件的編譯順序、任務(wù)調(diào)度系統(tǒng)安排作業(yè)、包管理器解決軟件包依賴、甚至是在一些游戲里決定科技樹(shù)的解鎖順序。今天我們就來(lái)徹底搞懂它并附上一份你可以在各種場(chǎng)景下直接“抄作業(yè)”的C模板。2. 核心概念與問(wèn)題場(chǎng)景拆解2.1 什么是“拓?fù)洹焙汀芭判颉蔽覀兊孟炔痖_(kāi)“拓?fù)渑判颉边@四個(gè)字?！巴?fù)洹盩opology在這里借用了數(shù)學(xué)中“拓?fù)鋵W(xué)”的概念但你不必?fù)?dān)心我們不需要那些復(fù)雜的定義。在這里它特指研究圖形頂點(diǎn)間連接關(guān)系的結(jié)構(gòu)也就是“圖論”。而“排序”就是給頂點(diǎn)安排一個(gè)線性序列。所以拓?fù)渑判虻膶?duì)象是一個(gè)有向無(wú)環(huán)圖。我們來(lái)逐一拆解這個(gè)前提有向邊是有方向的A-B 表示 A 先于 B或者說(shuō) B 依賴于 A。這個(gè)方向性體現(xiàn)了依賴關(guān)系。無(wú)環(huán)圖中不能存在循環(huán)依賴即不能有路徑使得 A-B-C-...-A。一旦有環(huán)就無(wú)法找到一個(gè)滿足所有依賴關(guān)系的線性序列因?yàn)槟銜?huì)陷入“先有雞還是先有蛋”的死循環(huán)。圖由頂點(diǎn)任務(wù)、事件、節(jié)點(diǎn)和連接它們的邊依賴關(guān)系組成。一個(gè)典型的反例假設(shè)有三門(mén)課課程依賴是“數(shù)據(jù)結(jié)構(gòu)依賴于算法基礎(chǔ)算法基礎(chǔ)依賴于程序設(shè)計(jì)程序設(shè)計(jì)依賴于數(shù)據(jù)結(jié)構(gòu)”。這就形成了一個(gè)環(huán)你無(wú)法決定先上哪門(mén)課拓?fù)渑判蛟谶@種情況下會(huì)失敗這正是算法需要檢測(cè)出的情況。2.2 算法核心思想入度與隊(duì)列拓?fù)渑判蜃罱?jīng)典、最直觀的實(shí)現(xiàn)方法是Kahn算法其核心是“入度”和“隊(duì)列”。入度對(duì)于一個(gè)頂點(diǎn)來(lái)說(shuō)它的“入度”是指有多少條邊直接指向它。入度為0的頂點(diǎn)意味著沒(méi)有任何前置依賴可以立即被執(zhí)行。隊(duì)列用來(lái)存放當(dāng)前所有入度為0的頂點(diǎn)。算法流程可以類(lèi)比為“剝洋蔥”初始化計(jì)算圖中每個(gè)頂點(diǎn)的入度。找到所有入度為0的頂點(diǎn)把它們放入一個(gè)隊(duì)列或任何容器中。從隊(duì)列中取出一個(gè)頂點(diǎn)輸出它或存入結(jié)果序列。將這個(gè)頂點(diǎn)從圖中“移除”邏輯上即遍歷所有由它直接指向的鄰居頂點(diǎn)將這些鄰居頂點(diǎn)的入度減1。如果某個(gè)鄰居頂點(diǎn)的入度因此減為0則將其加入隊(duì)列。重復(fù)步驟3-5直到隊(duì)列為空。循環(huán)結(jié)束后的檢查如果輸出的頂點(diǎn)數(shù)量等于圖中總頂點(diǎn)數(shù)恭喜拓?fù)渑判虺晒敵鲂蛄芯褪瞧渲幸粋€(gè)可行的順序。如果輸出的頂點(diǎn)數(shù)量小于總頂點(diǎn)數(shù)說(shuō)明圖中存在環(huán)無(wú)法進(jìn)行拓?fù)渑判?。注意一個(gè)有向無(wú)環(huán)圖的拓?fù)渑判蚪Y(jié)果可能不唯一。只要滿足依賴關(guān)系多個(gè)順序都是正確的。這就像早上你可以先刷牙再洗臉也可以先洗臉再刷牙只要在吃早飯之前完成就行。3. C模板實(shí)現(xiàn)與逐行解析理解了思想我們來(lái)看代碼。下面這份模板力求清晰、通用并加了詳細(xì)注釋。你可以根據(jù)具體問(wèn)題修改頂點(diǎn)數(shù)據(jù)的類(lèi)型T和圖的存儲(chǔ)方式。#include iostream #include vector #include queue using namespace std; /** * brief 使用Kahn算法進(jìn)行拓?fù)渑判虻哪０?* tparam T 頂點(diǎn)數(shù)據(jù)的類(lèi)型如int, string, 或自定義結(jié)構(gòu)體 * param numVertices 頂點(diǎn)數(shù)量頂點(diǎn)編號(hào)假設(shè)為 0 到 numVertices-1 * param adjList 鄰接表adjList[u] 存儲(chǔ)所有從u出發(fā)能直接到達(dá)的頂點(diǎn)v * return vectorT 拓?fù)渑判虻慕Y(jié)果序列。如果圖中有環(huán)返回空向量。 */ vectorint topologicalSort(int numVertices, const vectorvectorint adjList) { vectorint inDegree(numVertices, 0); // 1. 初始化入度數(shù)組 vectorint result; // 存儲(chǔ)拓?fù)渑判蚪Y(jié)果 queueint q; // 存放當(dāng)前入度為0的頂點(diǎn) // 2. 計(jì)算每個(gè)頂點(diǎn)的初始入度 for (int u 0; u numVertices; u) { for (int v : adjList[u]) { inDegree[v]; // 有一條u-v的邊v的入度加1 } } // 3. 將所有初始入度為0的頂點(diǎn)入隊(duì) for (int i 0; i numVertices; i) { if (inDegree[i] 0) { q.push(i); } } // 4. 開(kāi)始“剝洋蔥”過(guò)程 while (!q.empty()) { int u q.front(); // 取出一個(gè)當(dāng)前可執(zhí)行的頂點(diǎn) q.pop(); result.push_back(u); // 加入結(jié)果序列 // 遍歷u的所有出邊模擬“移除u” for (int v : adjList[u]) { inDegree[v]--; // 鄰居v的入度減1 if (inDegree[v] 0) { // 如果v因此變得無(wú)依賴 q.push(v); // 將v加入隊(duì)列 } } } // 5. 檢查是否所有頂點(diǎn)都被排序 if (result.size() ! numVertices) { // 結(jié)果數(shù)量不對(duì)說(shuō)明圖中有環(huán)無(wú)法完成拓?fù)渑判?return vectorint(); // 返回空結(jié)果表示失敗 } return result; } // 一個(gè)簡(jiǎn)單的使用示例 int main() { // 示例6個(gè)頂點(diǎn)0-5依賴關(guān)系如下 // 5 - 0, 5 - 2 // 4 - 0, 4 - 1 // 2 - 3 // 3 - 1 int n 6; vectorvectorint graph(n); graph[5].push_back(0); graph[5].push_back(2); graph[4].push_back(0); graph[4].push_back(1); graph[2].push_back(3); graph[3].push_back(1); // 注意這里沒(méi)有 1 - x 的邊所以頂點(diǎn)1的入度可能不為0 vectorint order topologicalSort(n, graph); if (order.empty()) { cout 圖中存在環(huán)無(wú)法進(jìn)行拓?fù)渑判? endl; } else { cout 拓?fù)渑判蚪Y(jié)果一種可能的順序: ; for (int v : order) { cout v ; } cout endl; // 一種可能的輸出5 4 2 0 3 1 或 4 5 0 2 3 1 等 } return 0; }關(guān)鍵代碼段解析與實(shí)操心得鄰接表adjList這是存儲(chǔ)圖最常用的方式之一特別適合稀疏圖。graph[u]是一個(gè)向量存儲(chǔ)了所有從頂點(diǎn)u出發(fā)能直接到達(dá)的頂點(diǎn)v。它的空間復(fù)雜度是 O(VE)遍歷某個(gè)頂點(diǎn)所有鄰居的時(shí)間復(fù)雜度是 O(出度)。在構(gòu)建圖時(shí)務(wù)必確保邊的方向與你對(duì)依賴關(guān)系的理解一致。常見(jiàn)的坑是“我以為A依賴B所以建了邊B-A”結(jié)果正好反了。記住邊u-v表示u必須先于vv依賴于u。入度數(shù)組inDegree我們單獨(dú)用一個(gè)數(shù)組來(lái)維護(hù)入度而不是每次去鄰接表里統(tǒng)計(jì)這是典型的“空間換時(shí)間”優(yōu)化。初始化時(shí)遍歷所有邊進(jìn)行計(jì)算時(shí)間復(fù)雜度 O(E)。隊(duì)列q的選擇這里用了std::queue先進(jìn)先出保證了排序結(jié)果的一種特定順序偏向于按初始入隊(duì)順序。如果你想得到字典序最小的拓?fù)渑判蚩梢园裶ueue換成priority_queue最小堆。這樣每次取出的是當(dāng)前可執(zhí)行頂點(diǎn)中編號(hào)最小的那個(gè)。這在一些題目中是明確的要求。結(jié)果校驗(yàn)result.size() ! numVertices這是檢測(cè)圖中是否有環(huán)的簡(jiǎn)潔方法。如果存在環(huán)那么環(huán)上的所有頂點(diǎn)入度永遠(yuǎn)不可能減為0它們永遠(yuǎn)不會(huì)進(jìn)入隊(duì)列導(dǎo)致結(jié)果序列不完整。這是Kahn算法一個(gè)非常優(yōu)雅的特性既能排序又能檢環(huán)。4. 模板的變通與實(shí)戰(zhàn)應(yīng)用上面的模板假設(shè)頂點(diǎn)是連續(xù)的整數(shù)編號(hào)。在實(shí)際問(wèn)題中頂點(diǎn)可能是字符串如課程名、文件名或者自定義對(duì)象。這時(shí)你需要引入映射。4.1 處理字符串頂點(diǎn)如課程名#include unordered_map #include string vectorstring topologicalSort(const unordered_mapstring, vectorstring adjList) { unordered_mapstring, int inDegree; unordered_mapstring, vectorstring graph adjList; // 復(fù)制一份也可直接用 // 初始化所有頂點(diǎn)的入度為0并計(jì)算真實(shí)入度 for (const auto pair : graph) { inDegree[pair.first]; // 確保每個(gè)頂點(diǎn)都在map中入度初始化為0 for (const string neighbor : pair.second) { inDegree[neighbor]; // 鄰居入度加1 } } queuestring q; for (const auto pair : inDegree) { if (pair.second 0) { q.push(pair.first); } } vectorstring result; while (!q.empty()) { string u q.front(); q.pop(); result.push_back(u); for (const string v : graph[u]) { // 注意graph[u]可能不存在需要先判斷 if (--inDegree[v] 0) { q.push(v); } } } if (result.size() ! inDegree.size()) { return vectorstring(); } return result; }注意事項(xiàng)當(dāng)頂點(diǎn)是字符串時(shí)構(gòu)建鄰接表要格外小心頂點(diǎn)是否存在。最好使用unordered_mapstring, vectorstring來(lái)存儲(chǔ)圖并在計(jì)算入度前確保所有出現(xiàn)過(guò)的頂點(diǎn)都在inDegree中有記錄即使入度為0。4.2 需要輸出所有可能排序或特定排序Kahn算法使用隊(duì)列天然產(chǎn)生一種排序。若要所有可能排序需要使用回溯算法在每一步選擇任意一個(gè)入度為0的頂點(diǎn)遞歸下去。這屬于DFS的思路時(shí)間復(fù)雜度會(huì)很高O(V!)僅適用于頂點(diǎn)數(shù)很少的情況。若要字典序最小的排序如前所述將隊(duì)列替換為優(yōu)先隊(duì)列最小堆即可// 將 queueint q; 替換為 priority_queueint, vectorint, greaterint q; // 最小堆 // 入隊(duì)用 q.push(i); // 出隊(duì)用 int u q.top(); q.pop();4.3 復(fù)雜度分析與選擇依據(jù)時(shí)間復(fù)雜度O(V E)。每個(gè)頂點(diǎn)和每條邊都被訪問(wèn)常數(shù)次初始化入度遍歷所有邊O(E)主循環(huán)中每個(gè)頂點(diǎn)出隊(duì)一次O(V)每條邊被檢查一次O(E)。非常高效?？臻g復(fù)雜度O(V E)用于存儲(chǔ)鄰接表和輔助數(shù)據(jù)結(jié)構(gòu)入度數(shù)組、隊(duì)列、結(jié)果數(shù)組。何時(shí)選擇拓?fù)渑判虍?dāng)你面對(duì)的問(wèn)題可以抽象為“任務(wù)調(diào)度”、“依賴解析”、“順序安排”并且依賴關(guān)系沒(méi)有循環(huán)時(shí)拓?fù)渑判蛲ǔＪ鞘走x工具。相比于暴力搜索所有排列它的效率是指數(shù)級(jí)的提升。5. 常見(jiàn)問(wèn)題排查與深度優(yōu)化技巧即使理解了算法在實(shí)際編碼和調(diào)試中還是會(huì)遇到各種問(wèn)題。下面是我踩過(guò)的一些坑和解決技巧。5.1 為什么我的程序輸出空或結(jié)果不對(duì)問(wèn)題1結(jié)果為空函數(shù)返回空vector原因幾乎可以肯定是圖中存在有向環(huán)。排查檢查輸入肉眼檢查你構(gòu)建的adjList看是否有明顯的循環(huán)如A-B, B-C, C-A。打印入度在初始化后和主循環(huán)中打印inDegree數(shù)組觀察哪些頂點(diǎn)的入度始終不為0。DFS檢環(huán)實(shí)現(xiàn)一個(gè)DFS版本的環(huán)檢測(cè)算法作為雙重驗(yàn)證。給頂點(diǎn)標(biāo)記三種狀態(tài)未訪問(wèn)(0)、訪問(wèn)中(1)、已訪問(wèn)(2)。在DFS過(guò)程中如果遇到狀態(tài)為“訪問(wèn)中”的鄰居說(shuō)明找到了環(huán)。問(wèn)題2結(jié)果序列不完整數(shù)量少于頂點(diǎn)數(shù)但也沒(méi)報(bào)環(huán)原因這通常就是環(huán)導(dǎo)致的算法已經(jīng)通過(guò)result.size() ! numVertices檢測(cè)到了并返回了空。如果你沒(méi)檢查這個(gè)條件就會(huì)得到不完整結(jié)果。務(wù)必進(jìn)行完整性檢查問(wèn)題3結(jié)果順序和預(yù)期不一樣原因拓?fù)渑判虮旧砜赡懿晃ㄒ?。你用的?duì)列FIFO順序、或者輸入邊的順序都會(huì)影響最終輸出。只要結(jié)果滿足所有依賴關(guān)系就是正確的。如果需要特定順序如字典序需使用優(yōu)先隊(duì)列。5.2 鄰接表 vs 鄰接矩陣我們的模板用了鄰接表。什么時(shí)候用鄰接矩陣呢鄰接表適用于稀疏圖邊數(shù)E遠(yuǎn)小于頂點(diǎn)數(shù)V的平方。節(jié)省空間遍歷鄰居高效。拓?fù)渑判虻慕^大多數(shù)場(chǎng)景都用它。鄰接矩陣一個(gè)V x V的二維數(shù)組或vectorvectorbool。適用于稠密圖或者需要頻繁判斷任意兩個(gè)頂點(diǎn)間是否有邊。在拓?fù)渑判蛑杏盟跏蓟攵刃枰闅v整個(gè)矩陣復(fù)雜度為 O(V^2)不如鄰接表高效。選擇建議除非題目明確給出矩陣形式或圖非常稠密否則無(wú)腦用鄰接表。5.3 處理頂點(diǎn)編號(hào)不連續(xù)或自定義頂點(diǎn)有時(shí)題目給的頂點(diǎn)編號(hào)不是從0開(kāi)始的連續(xù)整數(shù)。比如編號(hào)是101, 203, 305。方法仍然可以使用整數(shù)模板但需要做一個(gè)重映射。先收集所有出現(xiàn)的頂點(diǎn)編號(hào)排序去重然后映射到0, 1, 2, ...。在輸入和輸出時(shí)進(jìn)行轉(zhuǎn)換?；蛘咧苯邮褂蒙厦嫣岬降淖址旤c(diǎn)模板把編號(hào)當(dāng)作字符串處理。對(duì)于自定義頂點(diǎn)如結(jié)構(gòu)體你需要定義哈希函數(shù)如果使用unordered_map或比較函數(shù)如果使用優(yōu)先隊(duì)列核心還是將頂點(diǎn)映射到一個(gè)唯一的ID或直接使用指針/引用。5.4 內(nèi)存與性能優(yōu)化使用vector和queue的reserve如果事先知道頂點(diǎn)和邊的大致數(shù)量可以使用reserve預(yù)分配內(nèi)存減少動(dòng)態(tài)擴(kuò)容的開(kāi)銷(xiāo)。vectorvectorint adjList(numVertices); for(auto list : adjList) list.reserve(estimatedAvgDegree); result.reserve(numVertices);使用int而非size_t在算法競(jìng)賽或?qū)π阅芤髽O高的場(chǎng)景使用int作為索引和計(jì)數(shù)器可能比size_t稍快且與大多數(shù)題目輸入匹配。但在需要處理大規(guī)模數(shù)據(jù)時(shí)要注意int的范圍。迭代器遍歷在C中使用基于范圍的for循環(huán) (for (int v : adjList[u])) 通常足夠快且簡(jiǎn)潔。在極端優(yōu)化場(chǎng)景可以考慮用指針遍歷vector的數(shù)據(jù)區(qū)但可讀性會(huì)下降。5.5 一個(gè)綜合案例編譯依賴解析假設(shè)我們要編譯多個(gè)文件文件間有依賴關(guān)系A(chǔ).cpp包含B.h則B.cpp需先于A.cpp編譯。建模每個(gè)源代碼文件是一個(gè)頂點(diǎn)。如果文件X依賴于文件Y即X包含了Y的頭文件則建立一條邊Y - X。注意方向被依賴者指向依賴者。輸入可能是文件列表和依賴對(duì)。運(yùn)行拓?fù)渑判虻玫降木褪且粋€(gè)可行的編譯順序。處理結(jié)果如果排序失敗說(shuō)明存在循環(huán)包含例如A.h包含B.hB.h又包含A.h這是編譯錯(cuò)誤需要程序員解決。這個(gè)案例清晰地展示了如何將實(shí)際問(wèn)題抽象成圖并應(yīng)用我們的模板。