前往
大廳
主題

LeetCode - 797. All Paths From Source to Target 解題心得

Not In My Back Yard | 2022-05-29 12:00:13 | 巴幣 0 | 人氣 98

題目連結:


題目意譯:
給定一個有著編號為 0 到 n - 1 的 n 個節點之有向無環圖(Directed Acyclic Graph,DAG),找出所有從節點 0 到節點 n - 1 的所有可能的路徑並按任意順序回傳。

圖按照以下方式給定:graph[i] 為一列表包含著你可以從節點 i 拜訪的所有節點(即,節點 i 和節點 graph[i][j] 之間有一條有向邊)。

限制:
n == graph.length
2 ≦ n ≦ 15
0 ≦ graph[i][j] < n
graph[i][j] != i(即不存在自環(Self-loops))
graph[i] 中所有元素相異。
輸入的圖必為一個 DAG。



範例測資:
範例 1:
輸入: graph = [[1,2],[3],[3],[]]
輸出: [[0,1,3],[0,2,3]]
解釋: 有兩條路徑:0 → 1 → 3 和 0 → 2 → 3。

範例 2:
輸入: graph = [[4,3,1],[3,2,4],[3],[4],[]]
輸出: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]


解題思維:
由於輸入給定的 graph 即是一個鄰接表(Adjacency List,如這題)。

因此我們可以從節點 0 開始依據深度優先搜尋(Depth First Search,DFS,如這題)的精神來走到下一個節點,然後過程中記錄其路徑。每次遇到節點 n - 1 時,把路徑記錄下來最後即可求得所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作