圖論理論基礎
題目鏈接/文章講解:https://www.programmercarl.com/kamacoder/%E5%9B%BE%E8%AE%BA%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
了解圖的基本概念,連通性,圖的構造,圖的遍歷方式
深搜理論基礎
題目鏈接/文章講解:https://www.programmercarl.com/kamacoder/%E5%9B%BE%E8%AE%BA%E6%B7%B1%E6%90%9C%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
了解dfs 和 bfs的大體區別,dfs的搜索過程以及代碼框架。
98. 所有可達路徑
題目鏈接/文章講解:https://www.programmercarl.com/kamacoder/0098.%E6%89%80%E6%9C%89%E5%8F%AF%E8%BE%BE%E8%B7%AF%E5%BE%84.html
深度優先搜索:
1. 確認遞歸函數,參數
首先我們dfs函數一定要存一個圖,用來遍歷的,需要存一個目前我們遍歷的節點,定義為x。
還需要存一個n,表示終點,我們遍歷的時候,用來判斷當 x==n 時候 標明找到了終點。
代碼如下:
vector<vector<int>> result; // 收集符合條件的路徑
vector<int> path; // 0節點到終點的路徑
// x:目前遍歷的節點
// graph:存當前的圖
// n:終點
void dfs (const vector<vector<int>>& graph, int x, int n) {
2. 確認終止條件
什么時候我們就找到一條路徑了?
當目前遍歷的節點 為 最后一個節點 n 的時候 就找到了一條 從出發點到終止點的路徑。
代碼如下:
// 當前遍歷的節點x 到達節點n
if (x == n) { // 找到符合條件的一條路徑result.push_back(path);return;
}
3. 處理目前搜索節點出發的路徑
接下來是走 當前遍歷節點x的下一個節點。
首先是要找到 x節點指向了哪些節點呢? 遍歷方式是這樣的:
for (int i = 1; i <= n; i++) { // 遍歷節點x鏈接的所有節點if (graph[x][i] == 1) { // 找到 x指向的節點,就是節點i}
}
接下來就是將 選中的x所指向的節點,加入到 單一路徑來。
path.push_back(i); // 遍歷到的節點加入到路徑中來
進入下一層遞歸
dfs(graph, i, n); // 進入下一層遞歸
最后就是回溯的過程,撤銷本次添加節點的操作。
path.pop_back(); // 回溯,撤銷本節點
廣搜理論基礎?
題目鏈接/文章講解:https://www.programmercarl.com/kamacoder/%E5%9B%BE%E8%AE%BA%E5%B9%BF%E6%90%9C%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
了解廣度優先搜索的使用場景、過程和代碼框架
總結
第50天,繼續加油