Last Updated on 2022-12-31 by Clay
題目
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.
題目給定一個有向圖，我們要找出所有從 0 到終點的路徑並回傳。
解題思路
DFS
像這種需要走到終點的題目，第一感就是使用深度優先搜索來解題。在走向每一次新的遞迴時，都要把當前路徑記錄下來；當此輪遞迴結束後，要把當前節點從當前路徑中彈出，才不會在更外一層的遞迴時參雜了錯誤的節點。
詳情還請看程式碼。
C++ 範例程式碼
class Solution {
public:
void DFS(vector<vector<int>>& graph, vector<vector<int>>& paths, vector<int>& path, int vertex) {
path.emplace_back(vertex);
if (vertex == graph.size() - 1) {
paths.emplace_back(path);
}
else {
for (int v: graph[vertex]) {
DFS(graph, paths, path, v);
}
}
path.pop_back();
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
// Init
vector<vector<int>> paths;
vector<int> path;
// Finding
DFS(graph, paths, path, 0);
return paths;
}
};Python 範例程式碼
class Solution:
def DFS(self, graph: List[List[int]], paths: List[List[int]], path: List[int], vertex: int) -> None:
path.append(vertex)
if vertex == len(graph) - 1:
paths.append(path.copy())
else:
for v in graph[vertex]:
self.DFS(graph, paths, path, v)
path.pop()
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
# Init
paths: List[List[int]] = []
path: List[int] = []
# Finding
self.DFS(graph, paths, path, 0)
return paths