從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
請幫我隨手點開下面的SHOW EMBED並按5個like～ 喜歡的話也可以幫我拍拍手～ (按讚不用錢，感謝支持寫作~)
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:
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:
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.length2 <= n <= 150 <= graph[i][j] < ngraph[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，那麼我們從任何一個點出發， 都保證不可能會再回到同一個點，同時也不可能走回頭路， 也就不存在重複的可能。
讓我們嘗試列出找尋路徑的步驟： 1. 首先從i = 0開始，觀察graph[i]的連接， 例如像Example 1中0就連到1跟2， 也就是說會有 0->1跟0->2這兩條路徑 2. 對於0->1而言，接下來我們要看1的連接， 發現它只連接到3，而3剛好是這個graph的最後一個節點， 因此得到其中一個有效的路徑是0->1->3。 3. 同理，對於0->2而言也剛好只有0->2->3。
因此對於這題，我們可以使用DFS從node 0做遞迴往下， 中途要記住每一步當下走過的路徑，只要有走到終點的路徑， 就將其放到答案的列表裡，最後再將整個結果回傳即可。
列出解題步驟如下： 1. 初始化一個串列res，用以存放結果的路徑 2. 定義一個dfs的函式，輸入為(i, path)， 當中i為當前走到的node，path為走到node i時經過的路徑(包含i)。 3. 在函式中，首先檢查i是否和graph的長度-1相等， 如是，代表走到node n-1的位置了， 該路徑是答案之一，將其加到res上。 4. 若3的檢查解果為否，代表要繼續往下走， 迴圈遍歷graph[i]中的下一個node nxt， 並呼叫dfs，將node nxt和新的path(path加上nxt)代入遞迴。 5. 將(0, [0])代入dfs中開始遞迴。 6. 完成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
如果你／妳覺得這篇文章不錯，請拍手並給5個Like。(點開SHOW EMBED!)
也請記得「Follow」我，隨時收看最新的文章。
