深度優先搜索dfs
提到深度優先搜索（dfs），就不得不說和廣度優先搜索（bfs）有什么區別
根據搜索方式的不同，可以將圖的遍歷分為「深度優先搜索」和「廣度優先搜索」。
- 深度優先搜索：從某一頂點出發，沿著?條路徑?直搜索下去，在?法搜索時，回退到剛剛訪問過的節點。
- 廣度優先搜索：從某個頂點出發，?次性訪問所有未被訪問的鄰接點，再依次從這些已訪問過的鄰接點出發，?層?層地訪問。
基礎與模板：
不斷深入，更新標記
下圖來自：AlgoNote/docs/06_graph/06_03_graph_dfs.md at main · itcharge/AlgoNote · GitHub
兩種兩種深度優先搜索的實現方式
- 遞歸實現
- 基于堆棧實現
首先介紹遞歸實現。與算法本身非常的和諧，和二叉樹的遍歷的兩種方式很像，實現方法也類似，只不過圖的儲存方式跟二叉樹不同而已。
基于堆棧實現：深度優先搜索是使用stack比較合適
題目1、797. 所有可能的路徑
給你一個有 n 個節點的 有向無環圖（DAG），請你找出從節點 0 到節點 n-1 的所有路徑并輸出（不要求按特定順序）
graph[i] 是一個從節點 i 可以訪問的所有節點的列表（即從節點 i 到節點 graph[i][j]存在一條有向邊）。
示例 1：
輸入：graph = [[1,2],[3],[3],[]]
輸出：[[0,1,3],[0,2,3]]
解釋：有兩條路徑 0 -> 1 -> 3 和 0 -> 2 -> 3
示例 2：
輸入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
輸出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
提示：
n == graph.length2 <= n <= 150 <= graph[i][j] < ngraph[i][j] != i（即不存在自環）graph[i]中的所有元素 互不相同- 保證輸入為 有向無環圖（DAG）
這個題目使用深度優先搜索，用stack實現感覺代碼量比較多一些。這里使用遞歸實現比較好理解，而且代碼量比較少，需要考慮的細節也比較多。需要改變DFS的遞歸條件
找出從節點 0 到節點 n-1 的所有路徑并輸出，所以遞歸的時候碰見n-1就把這一組加入結果
class Solution {
public:vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {vector<vector<int>> res;vector<int> singleVec{0}; // 這里開頭0先加到中間vec里面int num = graph.size();function<void(vector<int>&)> dfs = [&](vector<int>& vec){if(singleVec.back() == num-1){ // 中間vec最后一個值判斷條件res.push_back(singleVec);return;}for(auto a:vec){singleVec.push_back(a);dfs(graph[a]);singleVec.pop_back();// 這里singleVec在外面有push就需要pop}};dfs(graph[0]);return res;}
};
題目2、200. 島嶼數量
給你一個由 '1'（陸地）和 '0'（水）組成的的二維網格，請你計算網格中島嶼的數量。
島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。
此外，你可以假設該網格的四條邊均被水包圍。
示例 1：
輸入：grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]
]
輸出：1
示例 2：
輸入：grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]
]
輸出：3
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]的值為'0'或'1'
經典題目：往上下左右四個方向DFS，先遍歷，碰到1就開開始DFS把周圍的1都變成0
int dir[4][2]={0,1,1,0,0,-1,-1,0}; // 上下左右void makezero(vector<vector<char>>& grid,int x,int y){grid[x][y] = '0'; // 碰見1以后上下左右都置零for(int i = 0;i<4;i++){int nx = x+dir[i][0];int ny = y+dir[i][1];if(nx<0||ny<0||nx>=grid.size()||ny>=grid[0].size()) continue;if(grid[nx][ny]=='1'){makezero(grid,nx,ny);}}}int numIslands(vector<vector<char>>& grid) {int row = grid.size();int col = grid[0].size();int res = 0;for(int i = 0 ;i<row;i++){for(int j =0;j<col;j++ ){if(grid[i][j] == '1' ){ //碰見1之后，周圍置零makezero(grid,i,j);res++;}}}return res;}
題目3、695. 島嶼的最大面積
給你一個大小為 m x n 的二進制矩陣 grid 。
島嶼 是由一些相鄰的 1 (代表土地) 構成的組合，這里的「相鄰」要求兩個 1 必須在 水平或者豎直的四個方向上 相鄰。你可以假設 grid 的四個邊緣都被 0（代表水）包圍著。
島嶼的面積是島上值為 1 的單元格的數目。
計算并返回 grid 中最大的島嶼面積。如果沒有島嶼，則返回面積為 0 。
示例 1：
輸入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
輸出：6
解釋：答案不應該是 11 ，因為島嶼只能包含水平或垂直這四個方向上的 1 。
示例 2：
輸入：grid = [[0,0,0,0,0,0,0,0]]
輸出：0
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 50grid[i][j]為0或1
這個題目只是在外面加一個參數count，遍歷數組，得到count的最大值
題目4、133. 克隆圖
給你無向 連通 圖中一個節點的引用，請你返回該圖的 深拷貝（克隆）。
圖中的每個節點都包含它的值 val（int） 和其鄰居的列表（list[Node]）。
class Node {public int val;public List<Node> neighbors;
}
測試用例格式：
簡單起見，每個節點的值都和它的索引相同。例如，第一個節點值為 1（val = 1），第二個節點值為 2（val = 2），以此類推。該圖在測試用例中使用鄰接列表表示。
鄰接列表 是用于表示有限圖的無序列表的集合。每個列表都描述了圖中節點的鄰居集。
給定節點將始終是圖中的第一個節點（值為 1）。你必須將 給定節點的拷貝 作為對克隆圖的引用返回。
class Solution {
public:vector<int> flags = vector<int>(101,1);unordered_map<Node*,Node*>mp;
}
這里的flags 為什么不能 vector<int> flags(101,1);
在 C++ 類的定義里，成員變量的初始化要遵循特定的語法規則。當你在類中聲明非靜態成員變量時，像下面這樣直接初始化是不被允許的：
vector<int> flags(101,1); // 錯誤的類內初始化方式這是因為這種圓括號初始化的形式，會被編譯器理解成函數聲明。也就是說，編譯器會把它誤認為是一個名為flags，返回類型為vector，并且帶有兩個參數（一個int類型和一個int類型）的函數。
而使用等號加花括號或者直接用花括號的初始化方式，就不會產生歧義，所以是合法的類內初始化形式：
vector<int> flags = vector<int>(101,1); // 正確，使用等號初始化 vector<int> flags{101,1}; // 正確，使用花括號列表初始化（但這種方式是創建包含兩個元素101和1的vector） vector<int> flags = {101,1}; // 正確，等價于上面的花括號形式在你的代碼中：
vector<int> flags = vector<int>(101,1);這是正確的類內初始化寫法。它借助拷貝初始化，先構造出一個臨時的vector對象，然后再把這個臨時對象拷貝給成員變量flags。
總結一下，類內初始化要避開圓括號語法，防止和函數聲明混淆。建議優先采用花括號初始化或者等號初始化的方式。
這個題目，主要是
- 首先，
dfs時要確定好終止條件，當新節點創立好了之后就不用創立了，返回這個新節點即可 - 怎么找到創立好的新節點呢，通過哈希表建立起新舊節點的關系，通過舊節點找到新節點
class Node {
public:int val;vector<Node*> neighbors;Node() {val = 0;neighbors = vector<Node*>();}Node(int _val) {val = _val;neighbors = vector<Node*>();}Node(int _val, vector<Node*> _neighbors) {val = _val;neighbors = _neighbors;}
};
class Solution {
public:// 這里為了判斷這個節點有沒有被創建vector<int> flags = vector<int>(101,1); // 這個建立原始圖節點和新建節點之間映射// 當neighbors中有已經創建的節點之后// 通過這個哈希表就可以找到新建的對應節點unordered_map<Node*,Node*>mp;Node* cloneGraph(Node* node) {if(!node) return nullptr;if(flags[node->val] == 0) return mp[node];// 節點已創建，返回新節點Node* res = new Node(node->val);// 新建節點mp[node] = res; // 建立新舊節點哈希表flags[node->val] = 0; // 表示新節點已經創建for(auto a:node->neighbors){res->neighbors.push_back(cloneGraph(a));} // 新節點neighborsreturn res;}
};上面是個人寫的代碼，讓deepseek優化之后發現，這個創建標識符flags可以省略，通過哈希表就可以完成這個是否創建的判斷
class Solution {
public:unordered_map<Node*, Node*> visited; // 存儲原節點到克隆節點的映射Node* cloneGraph(Node* node) {if (!node) return nullptr;if (visited.find(node) != visited.end()) return visited[node]; // 已克隆則直接返回Node* cloneNode = new Node(node->val); // 創建新節點visited[node] = cloneNode; // 建立映射關系for (Node* neighbor : node->neighbors) {cloneNode->neighbors.push_back(cloneGraph(neighbor)); // 遞歸克隆鄰居}return cloneNode;}
};
題目5、841. 鑰匙和房間
有 n 個房間，房間按從 0 到 n - 1 編號。最初，除 0 號房間外的其余所有房間都被鎖住。你的目標是進入所有的房間。然而，你不能在沒有獲得鑰匙的時候進入鎖住的房間。
當你進入一個房間，你可能會在里面找到一套 不同的鑰匙，每把鑰匙上都有對應的房間號，即表示鑰匙可以打開的房間。你可以拿上所有鑰匙去解鎖其他房間。
給你一個數組 rooms 其中 rooms[i] 是你進入 i 號房間可以獲得的鑰匙集合。如果能進入 所有 房間返回 true，否則返回 false。
這里就是dfs的模板題。把圖從開頭遍歷，設置flags，表示遍歷到這個節點，，否則返回false
class Solution {
public:bool canVisitAllRooms(vector<vector<int>>& rooms) {vector<int> flags(rooms.size(),1); // 標準位，1表示未遍歷到flags[0] = 0; // 0已經遍歷到，0有鑰匙function<void(vector<int>&)>dfs = [&](vector<int>& vec){for(auto a:vec){if(flags[a]){ flags[a] = 0; // 遍歷到置零dfs(rooms[a]); // 繼續遍歷到下一個vec}}};dfs(rooms[0]);for(auto b:flags){ // 如果這個flags全部被遍歷到之后，返回tureif(b == 1) return false;}return true;}
};
 ? | DrinkWater（喝水記錄組件）)
