通知：代碼隨想錄算法訓(xùn)練營(yíng) 五期開(kāi)始報(bào)名，預(yù)計(jì)下周三（12月7日）開(kāi)營(yíng)！

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

797.所有可能的路徑

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

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

graph[i] 是一個(gè)從節(jié)點(diǎn) i 可以訪問(wèn)的所有節(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] 中的所有元素 互不相同
• 保證輸入為 有向無(wú)環(huán)圖（DAG）

思路

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

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

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

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

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

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

那有的錄友可能說(shuō)：那我以后稱回溯算法為深搜，是不是沒(méi)毛?。?/p>

理論上來(lái)說(shuō)，沒(méi)毛病，但 就像是  二叉樹(shù) 你不叫它二叉樹(shù)，叫它數(shù)據(jù)結(jié)構(gòu)，有問(wèn)題不？也沒(méi)問(wèn)題對(duì)吧。

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

接下來(lái)我們使用深搜三部曲來(lái)分析題目：

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

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

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

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

什么時(shí)候我們就找到一條路徑了？

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

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

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

// 要求從節(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ā)的路徑

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

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

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

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

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

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

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

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

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)加入到路徑中來(lái)
    dfs(graph, graph[x][i]); // 進(jìn)入下一層遞歸
    path.pop_back(); // 回溯，撤銷本節(jié)點(diǎn)
}

本題整體代碼如下：

總結(jié)

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

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

至于廣搜理論基礎(chǔ)，我們?cè)谙乱黄诤煤弥v解，敬請(qǐng)期待！