從LeetCode學演算法 - 119 Graph (2) / DFS (21)

0797. All Paths From Source to Target (Medium)

寫在前面

(基礎+進階+面試篇)從 LeetCode 學演算法 + 面試成功指南**

(3591元特價中: 2023/06/30 23:59後截止)
https://hiskio.com/bundles/eCP23B397?s=tc

(3990元長期有效) https://bit.ly/lc2022all

容筆者工商一下，
「從Leetcode學演算法｜進階篇」 這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/lc2022adv

Question

Given a directed acyclic graph (DAG ) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order .

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

Example 1

1
2
3
Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Example 2

1
2
Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

Constraints

n == graph.length
2 <= n <= 15
0 <= graph[i][j] < n
graph[i][j] != i (i.e., there will be no self-loops).
All the elements of graph[i] are unique .
The input graph is guaranteed to be a ** DAG**.

分析/解題

給定一個有向無環圖(directed acyclic graph, DAG)，
當中有n個nodes，分別被標記為0到n - 1，
找出所有可以從node 0走到node n - 1的路徑，
並且以任意排序的方式回傳。

graph的給定方式如以下敘述：
graph[i] 代表所有從node i可以造訪的nodes的串列。
(直接造訪，也就是指node i到graph[i][j]之間會有一個有方向的edge(邊))

我們這篇再來談談graph。
之前我們在第115篇 提到過，
在graph當中，有方向性的(a -> b和 b -> a被視為不一樣的邊)圖，
被稱為有向圖(directed graph) ；而如果有向圖中，
不存在環(cycle，也就是圖上存在一個點a，從點a出發，
有一條路徑可以再走回點a)的話，
則稱為有向無環圖，簡寫為DAG。

既然題目保證圖是DAG，那麼我們從任何一個點出發，
都保證不可能會再回到同一個點，同時也不可能走回頭路，
也就不存在重複的可能。

讓我們嘗試列出找尋路徑的步驟：

首先從i = 0開始，觀察graph[i] 的連接，
例如像Example 1中0就連到1跟2，
也就是說會有 0->1 跟0->2 這兩條路徑
對於0->1而言，接下來我們要看1的連接，
發現它只連接到3，而3剛好是這個graph的最後一個節點，
因此得到其中一個有效的路徑是0->1->3。
同理，對於0->2而言也剛好只有0->2->3。

因此對於這題，我們可以使用DFS從node 0做遞迴往下，
中途要記住每一步當下走過的路徑，只要有走到終點的路徑，
就將其放到答案的列表裡，最後再將整個結果回傳即可。

列出解題步驟如下：

初始化一個串列res，用以存放結果的路徑
定義一個dfs的函式，輸入為**(i, path)** ，
當中i為當前走到的node，path為走到node i時經過的路徑(包含i )。
在函式中，首先檢查i是否和graph的長度-1相等，
如是，代表走到node n-1 的位置了，
該路徑是答案之一，將其加到res上 。
若3的檢查解果為否，代表要繼續往下走，
迴圈遍歷graph[i] 中的下一個node nxt，
並呼叫dfs，將node nxt 和新的path(path加上nxt )代入遞迴。
將**(0, [0])** 代入dfs中開始遞迴。
完成5後，將res回傳即可。

依此，寫成程式碼如下：

Java

在Java的部分，我們的res顯然是二維的，
因此我們可以使用ArrayList來放入其中。
在helper(或dfs)中，因為不能像Python使用子函式，
這邊參數就需要graph、i、path、res；
又因為path是反覆遞迴下去利用的，
我們在記錄時使用backtracking的方式，
選擇在每次進入helper函式時，將path給加上當前走到的node i，
在離開時，則要記得將其收回，因此分別會在頭尾做path.add(i) ，
以及path.remove(path.size()-1) 。

其他要留意的部分是，由於在放到res的時候，
對於ArrayList來說是一個指向性質的放置，並不會直接複製一份path，
所以在res.add的時候，必須要使用new ArrayList(path) 的手法，
將path複製一份出來才行；不然後面我們在backtracking的時候，
就會同步影響到res的結果喲！

Python

在Python的部分由於可以使用子函式，
我們可以不需要再將res跟graph加到參數，
就會簡潔一點；
同時，在進行dfs的時候，我們這邊改成用
path + [nxt] 的方式，就會直接形成一個新的list。
這樣一來，path的部分就不需要再回頭處理backtracking的問題，
同時res也可以直接進行append(path)，不需要另行複製。
(因為前面path + [nxt]時已經複製完path並形成一個新的list了)

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(V * 2^V)，因為單一條最多是O(V)，最多可能有O(2^V)條)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

想看看其他題目嗎？
歡迎從第零篇 找你想要的！

同時追蹤粉專以獲得更多新文章的通知：
跟著Desolve學程式

另外，「從Leetcode學演算法｜基礎篇」 已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算 (差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊：
https://bit.ly/lc2022base