Breadth-First Search (BFS) 在拓?fù)渑判蛑械膽?yīng)用主要是用來解決有向無環(huán)圖（DAG）的拓?fù)渑判騿栴}。拓?fù)渑判蚴菍?duì)有向圖中所有節(jié)點(diǎn)的一種線性排序，使得對(duì)于每一條有向邊 (u, v)，節(jié)點(diǎn) u 在排序中都出現(xiàn)在節(jié)點(diǎn) v 的前面。如果圖中存在環(huán)路，則無法進(jìn)行拓?fù)渑判颉?
BFS 解決拓?fù)渑判虻牟襟E如下：
- 統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的入度（in-degree），即指向該節(jié)點(diǎn)的邊的數(shù)量。
- 將所有入度為 0 的節(jié)點(diǎn)加入隊(duì)列。
- 對(duì)于每個(gè)入度為 0 的節(jié)點(diǎn)，依次出隊(duì)，更新其相鄰節(jié)點(diǎn)的入度，將入度變?yōu)?0 的節(jié)點(diǎn)加入隊(duì)列。
- 重復(fù)步驟 3 直到隊(duì)列為空。
如果最終遍歷過的節(jié)點(diǎn)數(shù)等于圖中的節(jié)點(diǎn)數(shù)，說明圖是有向無環(huán)圖，可以得到一個(gè)拓?fù)渑判颉?/p>
01.課程表
題目鏈接：https://leetcode.cn/problems/course-schedule/
你這個(gè)學(xué)期必須選修 numCourses 門課程，記為 0 到 numCourses - 1 。
在選修某些課程之前需要一些先修課程。 先修課程按數(shù)組 prerequisites 給出，其中 prerequisites[i] = [ai, bi] ，表示如果要學(xué)習(xí)課程 ai 則 必須 先學(xué)習(xí)課程 bi 。
- 例如，先修課程對(duì)
[0, 1]表示：想要學(xué)習(xí)課程0，你需要先完成課程1。
請(qǐng)你判斷是否可能完成所有課程的學(xué)習(xí)？如果可以，返回 true ；否則，返回 false 。
示例 1：
輸入：numCourses = 2, prerequisites = [[1,0]]
輸出：true
解釋：總共有 2 門課程。學(xué)習(xí)課程 1 之前，你需要完成課程 0 。這是可能的。
示例 2：
輸入：numCourses = 2, prerequisites = [[1,0],[0,1]]
輸出：false
解釋：總共有 2 門課程。學(xué)習(xí)課程 1 之前，你需要先完成課程 0 ；并且學(xué)習(xí)課程 0 之前，你還應(yīng)先完成課程 1 。這是不可能的。
提示：
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCourses-
prerequisites[i]中的所有課程對(duì) 互不相同
思路
這里我們可以采用容器模擬鄰接矩陣或者鄰接表來進(jìn)行拓?fù)渑判颍袛噙@個(gè)圖是否有環(huán)的方式來解決這個(gè)問題
代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-834379.html
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
unordered_map<int,vector<int>> edges;
vector<int> in(numCourses,0);
for(vector<int>& e:prerequisites){
int a=e[0],b=e[1];
edges[b].push_back(a);
in[a]++;
}
queue<int> q;
for(int i=0;i<numCourses;++i)
if(in[i]==0) q.push(i);
while(!q.empty()){
int t=q.front();
q.pop();
for(int e:edges[t]){
in[e]--;
if(in[e]==0) q.push(e);
}
}
for(int i:in) if(i) return false;
return true;
}
};
- 使用一個(gè)哈希表
edges存儲(chǔ)有向圖的邊，其中edges[b]表示節(jié)點(diǎn)b指向的所有節(jié)點(diǎn)。 - 使用數(shù)組
in記錄每個(gè)節(jié)點(diǎn)的入度。初始化時(shí)，將所有節(jié)點(diǎn)的入度設(shè)為 0。 - 遍歷先修課程的關(guān)系，構(gòu)建有向圖并更新入度數(shù)組。
- 將入度為 0 的節(jié)點(diǎn)加入隊(duì)列
q。 - 使用 BFS 進(jìn)行拓?fù)渑判颍瑥娜攵葹?0 的節(jié)點(diǎn)開始，依次出隊(duì)，并將其鄰接節(jié)點(diǎn)的入度減 1。如果鄰接節(jié)點(diǎn)的入度減為 0，將其加入隊(duì)列。
- 如果最終所有節(jié)點(diǎn)的入度都為 0，說明圖中不存在環(huán)，可以完成所有課程，返回
true；否則，返回false。
02.課程表 II
題目鏈接：https://leetcode.cn/problems/course-schedule-ii/
現(xiàn)在你總共有 numCourses 門課需要選，記為 0 到 numCourses - 1。給你一個(gè)數(shù)組 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在選修課程 ai 前 必須 先選修 bi 。
- 例如，想要學(xué)習(xí)課程
0，你需要先完成課程1，我們用一個(gè)匹配來表示：[0,1]。
返回你為了學(xué)完所有課程所安排的學(xué)習(xí)順序?？赡軙?huì)有多個(gè)正確的順序，你只要返回 任意一種 就可以了。如果不可能完成所有課程，返回 一個(gè)空數(shù)組 。
示例 1：
輸入：numCourses = 2, prerequisites = [[1,0]]
輸出：[0,1]
解釋：總共有 2 門課程。要學(xué)習(xí)課程 1，你需要先完成課程 0。因此，正確的課程順序?yàn)?[0,1] 。
示例 2：
輸入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
輸出：[0,2,1,3]
解釋：總共有 4 門課程。要學(xué)習(xí)課程 3，你應(yīng)該先完成課程 1 和課程 2。并且課程 1 和課程 2 都應(yīng)該排在課程 0 之后。
因此，一個(gè)正確的課程順序是 [0,1,2,3] 。另一個(gè)正確的排序是 [0,2,1,3] 。
示例 3：
輸入：numCourses = 1, prerequisites = []
輸出：[0]
思路
總體思路和上面一致，我們只需要在每次將入度為0的點(diǎn)順序保存即為拓?fù)渑判虻捻樞颉?/p>
代碼
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
unordered_map<int,vector<int>> edges;
vector<int> in(numCourses,0);
for(vector<int>& e:prerequisites){
int a=e[0],b=e[1];
edges[b].push_back(a);
in[a]++;
}
queue<int> q;
vector<int> ret;
for(int i=0;i<numCourses;++i)
if(in[i]==0){
q.push(i);
ret.push_back(i);
}
while(!q.empty()){
int t=q.front();
q.pop();
for(int e:edges[t]){
in[e]--;
if(in[e]==0){
q.push(e);
ret.push_back(e);
}
}
}
for(int i:in) if(i) return {};
return ret;
}
};
- 使用一個(gè)哈希表
edges存儲(chǔ)有向圖的邊，其中edges[b]表示節(jié)點(diǎn)b指向的所有節(jié)點(diǎn)。 - 使用數(shù)組
in記錄每個(gè)節(jié)點(diǎn)的入度。初始化時(shí)，將所有節(jié)點(diǎn)的入度設(shè)為 0。 - 遍歷先修課程的關(guān)系，構(gòu)建有向圖并更新入度數(shù)組。
- 將入度為 0 的節(jié)點(diǎn)加入隊(duì)列
q，同時(shí)將這些節(jié)點(diǎn)加入結(jié)果數(shù)組ret中。 - 使用 BFS 進(jìn)行拓?fù)渑判颍瑥娜攵葹?0 的節(jié)點(diǎn)開始，依次出隊(duì)，并將其鄰接節(jié)點(diǎn)的入度減 1。如果鄰接節(jié)點(diǎn)的入度減為 0，將其加入隊(duì)列和結(jié)果數(shù)組。
- 如果最終所有節(jié)點(diǎn)的入度都為 0，說明圖中不存在環(huán)，返回拓?fù)渑判蚪Y(jié)果；否則，返回空數(shù)組表示無法完成拓?fù)渑判?/li>
03.火星詞典
題目鏈接：https://leetcode.cn/problems/Jf1JuT
現(xiàn)有一種使用英語字母的外星文語言，這門語言的字母順序與英語順序不同。
給定一個(gè)字符串列表 words ，作為這門語言的詞典，words 中的字符串已經(jīng) 按這門新語言的字母順序進(jìn)行了排序 。
請(qǐng)你根據(jù)該詞典還原出此語言中已知的字母順序，并 按字母遞增順序 排列。若不存在合法字母順序，返回 "" 。若存在多種可能的合法字母順序，返回其中 任意一種 順序即可。
字符串 s 字典順序小于 字符串 t 有兩種情況：
- 在第一個(gè)不同字母處，如果
s中的字母在這門外星語言的字母順序中位于t中字母之前，那么s的字典順序小于t。 - 如果前面
min(s.length, t.length)字母都相同，那么s.length < t.length時(shí)，s的字典順序也小于t。
示例 1：
輸入：words = ["wrt","wrf","er","ett","rftt"]
輸出："wertf"
示例 2：
輸入：words = ["z","x"]
輸出："zx"
示例 3：
輸入：words = ["z","x","z"]
輸出：""
解釋：不存在合法字母順序，因此返回 "" 。
提示：
1 <= words.length <= 1001 <= words[i].length <= 100-
words[i]僅由小寫英文字母組成
思路
將題意搞清楚之后，這道題就變成了判斷有向圖時(shí)候有環(huán)，可以用拓?fù)渑判蚪鉀Q。
如何搜集信息（如何建圖）：
a. 兩層for循環(huán)枚舉出所有的兩個(gè)字符串的組合；
b. 然后利用指針，根據(jù)字典序規(guī)則找出信息。文章來源：http://www.zghlxwxcb.cn/news/detail-834379.html
- 使用哈希表
edges存儲(chǔ)字母之間的順序關(guān)系，其中edges[a]表示字母a后面可以跟隨的字母集合。 - 使用哈希表
in記錄每個(gè)字母的入度，即有多少字母在它之前。 - 使用布爾變量
cheak標(biāo)記是否出現(xiàn)了無效的字母順序。 - 定義
add函數(shù)，該函數(shù)比較兩個(gè)單詞s1和s2，找到它們第一個(gè)不相同的字母，然后將這個(gè)字母的順序關(guān)系添加到edges中。如果s2是s1的前綴，則將cheak設(shè)置為true。 - 在構(gòu)建字母之間的順序關(guān)系時(shí)，遍歷相鄰的兩個(gè)單詞，調(diào)用
add函數(shù)，如果cheak為true，則直接返回空字符串。 - 使用隊(duì)列
q存儲(chǔ)入度為 0 的字母，初始化隊(duì)列時(shí)將所有入度為 0 的字母加入。 - 使用
BFS進(jìn)行拓?fù)渑判颍粩鄬⑷攵葹?0 的字母出隊(duì)，并將其后面可以跟隨的字母的入度減 1。將入度為 0 的字母加入結(jié)果字符串ret中。 - 最后檢查所有字母的入度是否都為 0，如果不為 0，則說明有環(huán)，返回空字符串；否則，返回結(jié)果字符串
ret。
代碼
class Solution {
unordered_map<char,unordered_set<char>> edges;
unordered_map<char,int> in;
bool cheak=false;
void add(string& s1,string& s2){
int n=min(s1.size(),s2.size());
int i=0;
while(i<n){
if(s1[i]!=s2[i]){
char a=s1[i],b=s2[i];
if(!edges.count(a)||!edges[a].count(b)){
edges[a].insert(b);
in[b]++;
}
break;
}
i++;
}
if(i==s2.size()&&i<s1.size()) cheak=true;
}
public:
string alienOrder(vector<string>& words) {
for(auto& s:words)
for(auto& ch:s)
in[ch]=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(cheak) return "";
}
queue<char> q;
for(auto& [a,b]:in)
if(b==0) q.push(a);
string ret;
while(!q.empty()){
char t=q.front();
q.pop();
ret+=t;
for(char ch:edges[t])
if(--in[ch]==0) q.push(ch);
}
for(auto& [a,b]:in) if(b) return "";
return ret;
}
};
到了這里，關(guān)于算法沉淀——BFS 解決拓?fù)渑判颍╨eetcode真題剖析）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
