總結(jié)leetcode75中的圖深度優(yōu)先搜索算法題解題思路。
上一篇：力扣75——二叉搜索樹

1 鑰匙和房間

題目：

有 n 個房間，房間按從 0 到 n - 1 編號。最初，除 0 號房間外的其余所有房間都被鎖住。
你的目標(biāo)是進入所有的房間。然而，你不能在沒有獲得鑰匙的時候進入鎖住的房間。當(dāng)你進入一個房間，你可能會在里面找到一套不同的鑰匙，每把鑰匙上都有對應(yīng)的房間號，
即表示鑰匙可以打開的房間。你可以拿上所有鑰匙去解鎖其他房間。給你一個數(shù)組 rooms 其中 rooms[i] 是你進入 i 號房間可以獲得的鑰匙集合。如果能進入
所有 房間返回 true，否則返回 false。

題解：
我的方法：廣度優(yōu)先搜索。進入一個房間t，拿到里面的鑰匙tmp，然后把鑰匙tmp壓入隊列q中。while循環(huán)從隊列q拿鑰匙，直到q空了為止。最后檢查所有房間visit是否都被訪問。
官方代碼：深度優(yōu)先搜索。利用遞歸函數(shù)dfs：進入一個房間，拿到鑰匙，再用for循環(huán)調(diào)用dfs函數(shù)。

class Solution {
public:bool canVisitAllRooms(vector<vector<int>>& rooms) {int numRooms = rooms.size();vector<int> visit(numRooms,0);visit[0] = 1;vector<int> tmp;queue<int> q;q.push(0);while (!q.empty()) {tmp = rooms[q.front()];q.pop();if (!tmp.empty()) {for (int t : tmp) {if (visit[t] == 1)continue;q.push(t);visit[t] = 1;}}}for (int v : visit) {if (v == 0) return false;}return true;}
};
//官方的代碼更簡潔合理
/*
class Solution {
public:vector<int> vis;int num;void dfs(vector<vector<int>>& rooms, int x) {vis[x] = true;num++;for (auto& it : rooms[x]) {if (!vis[it]) {dfs(rooms, it);}}}bool canVisitAllRooms(vector<vector<int>>& rooms) {int n = rooms.size();num = 0;vis.resize(n);dfs(rooms, 0);return num == n;}
};
*/

2 省份數(shù)量

題目：

有 n 個城市，其中一些彼此相連，另一些沒有相連。如果城市 a 與城市 b 直接相連，
且城市 b 與城市 c 直接相連，那么城市 a 與城市 c 間接相連。省份 是一組直接或間接相連的城市，組內(nèi)不含其他沒有相連的城市。給你一個 n x n 的矩陣 isConnected ，其中 isConnected[i][j] = 1 表示第 i 個城市和
第 j 個城市直接相連，而 isConnected[i][j] = 0 表示二者不直接相連。返回矩陣中 省份 的數(shù)量。

題解：
深度優(yōu)先搜索。for遍歷每個城市，用遞歸函數(shù)dfs找到所有與當(dāng)前城市i直接或間接相連的城市，用visit來標(biāo)記已經(jīng)搜索過的城市。

class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {int nums = 0, nC = isConnected.size();vector<int> visit(nC, 0);for (int i = 0; i < nC; i++) {if (visit[i] == 0) {nums++;dfs(isConnected, visit, i);}}return nums;}void dfs(vector<vector<int>>& isConnected,vector<int> & visit,int i) {visit[i] = 1;for (int j = 0; j < isConnected.size(); j++) {if (isConnected[i][j] == 1&& visit[j] == 0) {dfs(isConnected, visit, j);}}}
};

3 重新規(guī)劃路線

題目：

n 座城市，從 0 到 n-1 編號，其間共有 n-1 條路線。因此，要想在兩座不同城市之間旅行只有
唯一一條路線可供選擇（路線網(wǎng)形成一顆樹）。去年，交通運輸部決定重新規(guī)劃路線，以改變交通
擁堵的狀況。路線用 connections 表示，其中 connections[i] = [a, b] 表示從城市 a 到 b 的一條有向
路線。今年，城市 0 將會舉辦一場大型比賽，很多游客都想前往城市 0 。
請你幫助重新規(guī)劃路線方向，使每個城市都可以訪問城市 0 。返回需要變更方向的最小路線數(shù)。
題目數(shù)據(jù) 保證 每個城市在重新規(guī)劃路線方向后都能到達城市 0 。

題解：
廣度優(yōu)先搜索。目的是將所有路線的方向都朝著城市0，所以遍歷所有與城市0直接相連的城市，然后對這每一個相連的城市進行廣度優(yōu)先搜索，更改那些方向錯誤的路線。具體的過程在代碼中有注釋。

class Solution {
public:int minReorder(int n, vector<vector<int>>& connections) {vector<vector<int>> conn_idx(n, vector<int>());//這里使用了類似于鄰接表的方法，將和節(jié)點有關(guān)的連接的id序號加入到對應(yīng)的向量中//這樣在后面遍歷的時候，只要查找connections里面對應(yīng)的id即可//要注意這里連接兩端都加入了連接的序號for (int i = 0; i < connections.size(); i++) {conn_idx[connections[i][0]].push_back(i);conn_idx[connections[i][1]].push_back(i);}vector<bool> vi(connections.size(), false);//此處標(biāo)志的是某條邊是否被訪問過，而不是某個點是否被訪問過int ans = 0;queue<int> que;que.push(0);while (!que.empty()) {auto q = que.front();que.pop();//這個循環(huán)是對和節(jié)點q相關(guān)的連接進行遍歷，通過上面存儲的連接的id進行遍歷for (auto idx : conn_idx[q]) {if (vi[idx]) continue;vi[idx] = true;int a = connections[idx][0];//連接的起始int b = connections[idx][1];//連接的終點ans += (a == q);//如果當(dāng)前點是出的，那么要修改為入，ans++a = (a == q) ? b : a;que.push(a);}}return ans;}
};

4 除法求值

題目：

給你一個變量對數(shù)組 equations 和一個實數(shù)值數(shù)組 values 作為已知條件，其中 equations[i] 
= [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每個 Ai 或 Bi 是一個表示
單個變量的字符串。
另有一些以數(shù)組 queries 表示的問題，其中 queries[j] = [Cj, Dj] 表示第 j 個問題，請你根
據(jù)已知條件找出 Cj / Dj = ? 的結(jié)果作為答案。返回 所有問題的答案 。如果存在某個無法確定的答案，則用 -1.0 替代這個答案。如果問題中出現(xiàn)
了給定的已知條件中沒有出現(xiàn)的字符串，也需要用 -1.0 替代這個答案。注意：輸入總是有效的。你可以假設(shè)除法運算中不會出現(xiàn)除數(shù)為 0 的情況，且不存在任何矛盾的結(jié)果。
注意：未在等式列表中出現(xiàn)的變量是未定義的，因此無法確定它們的答案。

題解：
并查集。
1 先定義1個unordered_map類型的parent，它記錄了一個數(shù)的被除數(shù)，被除數(shù)的被除數(shù)是它自己。
2 再定義1個unordered_map類型的mp，記錄1個數(shù)除被除數(shù)得到的值。
3 接著定義函數(shù)find()，該函數(shù)可以找到一個數(shù)的祖先。在這個過程中，如果發(fā)現(xiàn)一個數(shù)的祖先跟它隔了2代或更多代，就遞歸進行壓縮，并修改對應(yīng)的mp值。
4 然后，通過for循環(huán)遍歷equations，將所以除法公式及其結(jié)果記錄好。
5 最后，計算queries中的問題。如果被除數(shù)或除數(shù)不存在于parent中，則無法求解；如果除數(shù)和被除數(shù)的祖先不是同一個，也無法求解；如果除數(shù)和被除數(shù)是同一個祖先，則直接用它們的mp值做除法即可。

class Solution {
public:unordered_map<string, string> parent;unordered_map<string, double> mp;string find(string x){if(parent[x] == x)  return x;string px = parent[x];string res =  parent[x] = find(parent[x]);    mp[x] *= mp[px];return res;}vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {int n = equations.size();for(int i = 0; i < n; i ++ ){string a = equations[i][0], b = equations[i][1];double v = values[i];if(parent.find(a) == parent.end() && parent.find(b) == parent.end()){parent[a] = a; parent[b] = a;mp[b] = v, mp[a] = 1.0;}else if(parent.find(a) == parent.end()){parent[a] = a; string pb = find(b);mp[a] = 1.0;mp[pb] = v / mp[b];parent[pb] = a;}else if(parent.find(b) == parent.end()){parent[b] = a;mp[b] = v;}else{string pa = find(a), pb = find(b);if(pa == pb)    continue;parent[pb] = pa;mp[pb] = mp[a] * v / mp[b];} }vector<double> res;for(auto &item : queries){string a = item[0], b = item[1];if(parent.find(a) == parent.end() || parent.find(b) == parent.end())    res.push_back(-1.0);else{string pa = find(a), pb = find(b);if(pa != pb)    res.push_back(-1.0);else    res.push_back(mp[b] / mp[a]);}}return res;}
};

1-4 解題總結(jié)

a 題目類型總結(jié)：

• 題目1：從1個節(jié)點出發(fā)，是否可以到達所有節(jié)點。
• 題目2：所有節(jié)點構(gòu)成幾個連通域。
• 題目3：從任意節(jié)點出發(fā)，是否可以到達某個節(jié)點。
• 題目4：節(jié)點1是否可以到達節(jié)點2。

b 題目1和題目3本質(zhì)上是一樣的，只是邊的方向相反了而已。他們既可以使用深度優(yōu)先搜索，也可以使用廣度優(yōu)先搜索。
c 題目2既可以使用深度優(yōu)先搜索，也可以使用廣度優(yōu)先搜索。
d 題目4是檢查兩個點之間是否連通，所以，用深度優(yōu)先搜索更合適。
e 這些題目不限制是否會重復(fù)經(jīng)過某個節(jié)點，只考慮哪些節(jié)點是相通的。