通知：代碼隨想錄算法訓(xùn)練營 五期開始報名，預(yù)計下周三（12月7日）開營！

講完深度優(yōu)先搜索的理論基礎(chǔ)之后，今天來一個入門題目。

797.所有可能的路徑

力扣題目鏈接：https:///problems/all-paths-from-source-to-target/

給你一個有 n 個節(jié)點(diǎn)的 有向無環(huán)圖（DAG），請你找出所有從節(jié)點(diǎn) 0 到節(jié)點(diǎn) n-1 的路徑并輸出（不要求按特定順序）

graph[i] 是一個從節(jié)點(diǎn) i 可以訪問的所有節(jié)點(diǎn)的列表（即從節(jié)點(diǎn) i 到節(jié)點(diǎn) graph[i][j]存在一條有向邊）。

提示：

• n == graph.length
• 2 <= n <= 15
• 0 <= graph[i][j] < n
• graph[i][j] != i（即不存在自環(huán)）
• graph[i] 中的所有元素 互不相同
• 保證輸入為 有向無環(huán)圖（DAG）

思路

這道題目是深度優(yōu)先搜索，比較好的入門題。

如果對深度優(yōu)先搜索還不夠了解，可以先看這里：深度優(yōu)先搜索的理論基礎(chǔ)

我依然總結(jié)了深搜三部曲，如果按照代碼隨想錄刷題的錄友，應(yīng)該刷過 二叉樹的遞歸三部曲，回溯三部曲。

大家可能有疑惑，深搜 和 二叉樹和回溯算法 有什么區(qū)別呢？什么時候用深搜 什么時候用回溯？

我在講解二叉樹理論基礎(chǔ)(https:///二叉樹理論基礎(chǔ).html)的時候，提到過，二叉樹的前中后序遍歷其實(shí)就是深搜在二叉樹這種數(shù)據(jù)結(jié)構(gòu)上的應(yīng)用。

那么回溯算法呢，其實(shí) 回溯算法就是深搜，只不過 我們給他一個更細(xì)分的定義，叫做回溯算法。

那有的錄友可能說：那我以后稱回溯算法為深搜，是不是沒毛??？

理論上來說，沒毛病，但 就像是  二叉樹 你不叫它二叉樹，叫它數(shù)據(jù)結(jié)構(gòu)，有問題不？也沒問題對吧。

建議是 有細(xì)分的場景，還是稱其細(xì)分場景的名稱。所以回溯算法可以獨(dú)立出來，但回溯算法確實(shí)就是深搜。

接下來我們使用深搜三部曲來分析題目：

1. 確認(rèn)遞歸函數(shù)，參數(shù)

首先我們dfs函數(shù)一定要存一個圖，用來遍歷的，還要存一個目前我們遍歷的節(jié)點(diǎn)，定義為x

至于 單一路徑，和路徑集合可以放在全局變量，那么代碼是這樣的：

2. 確認(rèn)終止條件

什么時候我們就找到一條路徑了？

當(dāng)目前遍歷的節(jié)點(diǎn) 為 最后一個節(jié)點(diǎn)的時候，就找到了一條，從 出發(fā)點(diǎn)到終止點(diǎn)的路徑。

當(dāng)前遍歷的節(jié)點(diǎn)，我們定義為x，最后一點(diǎn)節(jié)點(diǎn)，就是 graph.size() - 1。

所以 但 x 等于 graph.size() - 1 的時候就找到一條有效路徑。代碼如下：

// 要求從節(jié)點(diǎn) 0 到節(jié)點(diǎn) n-1 的路徑并輸出，所以是 graph.size() - 1
if (x == graph.size() - 1) { // 找到符合條件的一條路徑
    result.push_back(path); // 收集有效路徑
    return;
}

3. 處理目前搜索節(jié)點(diǎn)出發(fā)的路徑

接下來是走 當(dāng)前遍歷節(jié)點(diǎn)x的下一個節(jié)點(diǎn)。

首先是要找到 x節(jié)點(diǎn)鏈接了哪些節(jié)點(diǎn)呢？ 遍歷方式是這樣的：

接下來就是將 選中的x所連接的節(jié)點(diǎn)，加入到 單一路勁來。

path.push_back(graph[x][i]); // 遍歷到的節(jié)點(diǎn)加入到路徑中來

一些錄友可以疑惑這里如果找到x 鏈接的節(jié)點(diǎn)的，例如如果x目前是節(jié)點(diǎn)0，那么目前的過程就是這樣的：

二維數(shù)組中，graph[x][i] 都是x鏈接的節(jié)點(diǎn)，當(dāng)前遍歷的節(jié)點(diǎn)就是 graph[x][i] 。

進(jìn)入下一層遞歸

最后就是回溯的過程，撤銷本次添加節(jié)點(diǎn)的操作。 該過程整體代碼：

for (int i = 0; i < graph[x].size(); i++) { // 遍歷節(jié)點(diǎn)n鏈接的所有節(jié)點(diǎn)
    path.push_back(graph[x][i]); // 遍歷到的節(jié)點(diǎn)加入到路徑中來
    dfs(graph, graph[x][i]); // 進(jìn)入下一層遞歸
    path.pop_back(); // 回溯，撤銷本節(jié)點(diǎn)
}

本題整體代碼如下：

總結(jié)

本題是比較基礎(chǔ)的深度優(yōu)先搜索模板題，這種有向圖路徑問題，最合適使用深搜，當(dāng)然本題也可以使用廣搜，但廣搜相對來說就麻煩了一些，需要記錄一下路徑。

而深搜和廣搜都適合解決顏色類的問題，例如島嶼系列，其實(shí)都是 遍歷+標(biāo)記，所以使用哪種遍歷都是可以的。

至于廣搜理論基礎(chǔ)，我們在下一篇在好好講解，敬請期待！