通知：代碼隨想錄算法訓練營 五期開始報名，預計下周三（12月7日）開營！
講完深度優(yōu)先搜索的理論基礎之后，今天來一個入門題目。
力扣題目鏈接：https://leetcode.cn/problems/all-paths-from-source-to-target/
給你一個有 n 個節(jié)點的 有向無環(huán)圖（DAG），請你找出所有從節(jié)點 0 到節(jié)點 n-1 的路徑并輸出（不要求按特定順序）
graph[i] 是一個從節(jié)點 i 可以訪問的所有節(jié)點的列表（即從節(jié)點 i 到節(jié)點 graph[i][j]存在一條有向邊）。
提示：
這道題目是深度優(yōu)先搜索，比較好的入門題。
如果對深度優(yōu)先搜索還不夠了解，可以先看這里：深度優(yōu)先搜索的理論基礎
我依然總結了深搜三部曲，如果按照代碼隨想錄刷題的錄友，應該刷過 二叉樹的遞歸三部曲，回溯三部曲。
大家可能有疑惑，深搜 和 二叉樹和回溯算法 有什么區(qū)別呢？什么時候用深搜 什么時候用回溯？
我在講解二叉樹理論基礎(https://programmercarl.com/二叉樹理論基礎.html)的時候，提到過，二叉樹的前中后序遍歷其實就是深搜在二叉樹這種數(shù)據(jù)結構上的應用。
那么回溯算法呢，其實 回溯算法就是深搜，只不過 我們給他一個更細分的定義，叫做回溯算法。
那有的錄友可能說：那我以后稱回溯算法為深搜，是不是沒毛?。?/p>
理論上來說，沒毛病，但 就像是 二叉樹 你不叫它二叉樹，叫它數(shù)據(jù)結構，有問題不？也沒問題對吧。
建議是 有細分的場景，還是稱其細分場景的名稱。所以回溯算法可以獨立出來，但回溯算法確實就是深搜。
接下來我們使用深搜三部曲來分析題目：
首先我們dfs函數(shù)一定要存一個圖，用來遍歷的，還要存一個目前我們遍歷的節(jié)點，定義為x
至于 單一路徑，和路徑集合可以放在全局變量，那么代碼是這樣的：
vector<vector<int>> result; // 收集符合條件的路徑
vector<int> path; // 0節(jié)點到終點的路徑
// x：目前遍歷的節(jié)點
// graph：存當前的圖
void dfs (vector<vector<int>>& graph, int x)
什么時候我們就找到一條路徑了？
當目前遍歷的節(jié)點 為 最后一個節(jié)點的時候，就找到了一條，從 出發(fā)點到終止點的路徑。
當前遍歷的節(jié)點，我們定義為x，最后一點節(jié)點，就是 graph.size() - 1。
所以 但 x 等于 graph.size() - 1 的時候就找到一條有效路徑。代碼如下：
// 要求從節(jié)點 0 到節(jié)點 n-1 的路徑并輸出，所以是 graph.size() - 1
if (x == graph.size() - 1) { // 找到符合條件的一條路徑
result.push_back(path); // 收集有效路徑
return;
}
接下來是走 當前遍歷節(jié)點x的下一個節(jié)點。
首先是要找到 x節(jié)點鏈接了哪些節(jié)點呢？ 遍歷方式是這樣的：
for (int i = 0; i < graph[x].size(); i++) { // 遍歷節(jié)點n鏈接的所有節(jié)點
接下來就是將 選中的x所連接的節(jié)點，加入到 單一路勁來。
path.push_back(graph[x][i]); // 遍歷到的節(jié)點加入到路徑中來
一些錄友可以疑惑這里如果找到x 鏈接的節(jié)點的，例如如果x目前是節(jié)點0，那么目前的過程就是這樣的：
二維數(shù)組中，graph[x][i] 都是x鏈接的節(jié)點，當前遍歷的節(jié)點就是 graph[x][i] 。
進入下一層遞歸
dfs(graph, graph[x][i]); // 進入下一層遞歸
最后就是回溯的過程，撤銷本次添加節(jié)點的操作。 該過程整體代碼：
for (int i = 0; i < graph[x].size(); i++) { // 遍歷節(jié)點n鏈接的所有節(jié)點
path.push_back(graph[x][i]); // 遍歷到的節(jié)點加入到路徑中來
dfs(graph, graph[x][i]); // 進入下一層遞歸
path.pop_back(); // 回溯，撤銷本節(jié)點
}
本題整體代碼如下：
class Solution {
private:
vector<vector<int>> result; // 收集符合條件的路徑
vector<int> path; // 0節(jié)點到終點的路徑
// x：目前遍歷的節(jié)點
// graph：存當前的圖
void dfs (vector<vector<int>>& graph, int x) {
// 要求從節(jié)點 0 到節(jié)點 n-1 的路徑并輸出，所以是 graph.size() - 1
if (x == graph.size() - 1) { // 找到符合條件的一條路徑
result.push_back(path);
return;
}
for (int i = 0; i < graph[x].size(); i++) { // 遍歷節(jié)點n鏈接的所有節(jié)點
path.push_back(graph[x][i]); // 遍歷到的節(jié)點加入到路徑中來
dfs(graph, graph[x][i]); // 進入下一層遞歸
path.pop_back(); // 回溯，撤銷本節(jié)點
}
}
public:
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
path.push_back(0); // 無論什么路徑已經(jīng)是從0節(jié)點出發(fā)
dfs(graph, 0); // 開始遍歷
return result;
}
};
本題是比較基礎的深度優(yōu)先搜索模板題，這種有向圖路徑問題，最合適使用深搜，當然本題也可以使用廣搜，但廣搜相對來說就麻煩了一些，需要記錄一下路徑。
而深搜和廣搜都適合解決顏色類的問題，例如島嶼系列，其實都是 遍歷+標記，所以使用哪種遍歷都是可以的。
至于廣搜理論基礎，我們在下一篇在好好講解，敬請期待！
聯(lián)系客服
