引言

上篇我們介紹了BFS解決拓撲排序的背景知識，本篇我們將結合具體題目分析，進一步深化對于該算法的理解運用。

一、課程表

1.1 題目鏈接：https://leetcode.cn/problems/course-schedule/description/

1.2 題目分析：

• numCourses 表示要學的課程的數量
• prerequisites[i] = [ai, bi] ，表示如果要學習課程 ai 則 必須 先學習課程 bi 。
• 如果存在能按照順序學完的可能，返回true，否則返回false

1.3 思路講解：

該題為一個明顯的拓撲排序問題，根據上篇講解，我們可以這樣子處理

• 首先構建鄰接表，先決條件pre表示的順序即為b->a，作為邊加入其中
• 同時，由于學習a之前必須要學習b，因此a的入度加1
• 之后將入度為0的節點入隊列，層序遍歷即可

1.4 代碼實現：

class Solution {
public:bool canFinish(int n, vector<vector<int>>& prerequisites) {unordered_map<int,vector<int>> edges;//鄰接表vector<int> in(n);//入度//建圖for(auto e: prerequisites){int a=e[0],b=e[1];edges[b].push_back(a);in[a]++;}queue<int> q;//將入度為0的節點入隊列for(int i=0;i<n;i++){if(in[i]==0){q.push(i);}}//層序遍歷while(q.size()){int t=q.front();q.pop();for(int e : edges[t]){in[e]--;if(in[e]==0){q.push(e);}}}for(int i=0;i<n;i++){if(in[i]){return false;}//說明無法學完所有課程}return true;}
};

二、課程表||

2.1 題目鏈接：https://leetcode.cn/problems/course-schedule-ii/description/

2.2 題目分析：

該題與上題要求基本相同，只是返回值要求返回可能的一種學習順序，如果不存在，則返回空數組

2.3 思路講解：

判斷是否可以學習的思路與上題相同，我們只需要在層序遍歷時，用一個數組記錄當前學習順序即可。

2.4 代碼實現：

class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {unordered_map<int,vector<int>> edges;//鄰接表vector<int> in(numCourses);//入度vector<int> ret;//返回值vector<int> temp;//空數組queue<int> q;//建圖for(auto e:prerequisites){int a=e[0],b=e[1];edges[b].push_back(a);in[a]++;}//入度為0的節點入隊列for(int i=0;i<numCourses;i++){if(in[i]==0){q.push(i);}}while(q.size()){int t=q.front();q.pop();ret.push_back(t);//更新結果for(int e:edges[t]){in[e]--;if(in[e]==0){q.push(e);}}}for(int i=0;i<numCourses;i++){if(in[i]){return temp;}}//存在未完成情況，返回空數組return ret;}
};

三、火星詞典

3.1 題目鏈接：https://leetcode.cn/problems/Jf1JuT/description/

3.2 題目分析：

題目要求一時間難以讀懂，我們來簡單翻譯一下：

• 給定的word里面已經按一種新的字母順序排列好

假設 words = [“wrt”,“wrf”,“er”,“ett”,“rftt”]，我們可以得到字母之間的一些依賴關系：

• 比如從 “wrt” 和 “wrf” 可以得出 t 在 f 之前（因為 “t” 是兩個單詞中的不同字母，且在相同位置上不同）。

• 從 “er” 和 “ett” 中可以得出 r 在 e 之前。

最終需要返回題目中外星詞典的遞增順序，若不存在合法的順序，則返回空

3.3 思路講解：

我們通過比較相鄰的單詞，找出它們的第一個不同字母。這些字母的順序關系就可以幫助我們構建字母的順序圖。

圖的構建：

• 我們可以通過圖來表示字母之間的順序關系。每個字母是圖中的一個節點，而字母之間的順序關系是邊。

拓撲排序：

• 通過拓撲排序的方法，我們可以得到字母的正確排序。如果有環，則說明字母順序無法確定，返回空字符串。

3.4 代碼實現：

class Solution {
public:unordered_map<char,unordered_set<char>> edges;//邊unordered_map<char,int> in;//入度bool check;//處理特殊情況void add(string& s1,string& s2){int n=min(s1.size(),s2.size());int i;for( i=0;i<n;i++){if(s1[i]!=s2[i]){char a=s1[i],b=s2[i];if(!edges.count(a) || !edges[a].count(b))//如果之前為記錄過，則記錄這條邊a->b{edges[a].insert(b);in[b]++;//更新邊和入度節點}break;//注意跳出循環}}if(i==s2.size()&&i<s1.size())//處理abc ab這種特殊情況{check=true;}}string alienOrder(vector<string>& words) {//建圖和初始化for(auto e: words){for(auto ch:e){in[ch]=0;}//將所有字符的入度都初始化為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 "";//存在非法情況}}}//拓撲排序queue<char> q;string ret;//將所有入度為0的節點for(auto [a,b] :in){if(b==0){q.push(a);}}while(q.size()){char t=q.front();q.pop();ret+=t;for(auto e:edges[t]){if(--in[e]==0) q.push(e);}}for(auto [a,b] :in){if(b!=0){return "";}}//判斷是否存在不合法順序return ret;}
};

小結

本篇關于BFS解決拓撲排序的講解就暫告段落啦，希望能對大家的學習產生幫助，歡迎各位佬前來支持斧正！！！