MediumRating 1383
797. All Paths From Source to Target
backtrackingdepth-first-searchbreadth-first-searchgraph
解題說明
All Paths From Source to Target
題目描述： 給定一個有向無環圖（DAG），節點編號 0 到 n-1。找出所有從節點 0 到節點 n-1 的路徑。graph[i] 表示從節點 i 可以到達的所有節點。
解題思路：
- 回溯法（DFS）：由於是 DAG（無環），可以直接用 DFS 枚舉所有路徑，不需要 visited 陣列來避免循環。
- 從節點 0 開始，維護當前路徑 path。每到一個節點，將其加入 path。
- 如果到達終點 n-1，就將當前 path 加入結果。
- 對當前節點的所有鄰居遞迴探索，探索完後回溯（移除最後一個節點）。
- 因為圖是 DAG，保證不會有無限遞迴的問題。
C++ 解法
複雜度分析
時間複雜度：O(2^n * n) — 最壞情況下，DAG 中可能有指數級的路徑數，每條路徑長度最多為 n
空間複雜度：O(n) — 遞迴深度最多為 n（不計算答案所需空間）
虛擬碼
1. Initialize result list and path = [0]
2. Call DFS from node 0
3. DFS(node):
a. If node == n-1: add copy of path to result, return
b. For each neighbor in graph[node]:
- Append neighbor to path
- DFS(neighbor)
- Remove last element from path (backtrack)
4. Return result其他解法
-
BFS 方法：使用佇列存儲 (當前路徑) 的方式進行 BFS。每次從佇列取出一條路徑，擴展最後一個節點的鄰居。缺點是需要存儲大量中間路徑，空間消耗較大。
-
動態規劃 / 記憶化搜尋：dp[node] 記錄從 node 到 n-1 的所有路徑。從終點往回推導。對於本題因為需要列舉所有路徑，記憶化的加速效果有限，但代碼結構上更清晰。
延伸思考
- 如果圖中可能存在環，你會怎麼修改算法？
- 如果只需要找到路徑的數量而不是列出所有路徑，能否用更高效的方法？
- 如果要找最短路徑或最長路徑，應該如何修改？