0797. All Paths From Source to Target
0797. All Paths From Source to Target
797. All Paths From Source to Target
Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.The graph is given as follows: the nodes are 0, 1, …, graph.length - 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.Example:Input: [[1,2], [3], [3], []]Output: [[0,1,3],[0,2,3]]Explanation: The graph looks like this:0--->1| |v v2--->3There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.Note:The number of nodes in the graph will be in the range [2, 15].You can print different paths in any order, but you should keep the order of nodes inside one path.
思路
这题直接DFS,递归遍历就好了
-
时间复杂度 O(N)
-
空间复杂度 O(N)
代码
pub fn all_paths_source_target(graph: Vec>) -> Vec> { let mut paths = Vec::with_capacity(graph.len()); let mut path = Vec::with_capacity(graph.len()); path.push(0); find_N(0,&mut path,&mut paths,&graph); return paths;}pub fn find_N(poient:i32,mut path:&mut Vec,mut paths:&mut Vec>,graph:&Vec>){ if poient == (graph.len()-1) as i32 { paths.push(path.clone()); } else { for next in &graph[poient as usize]{ path.push(*next); find_N(*next,&mut path,&mut paths,& graph); path.pop(); } }}
- 执行用时: 12 ms
- 内存消耗: 2.4 MB
####
####
#### 题型与相似题
题型
- DFS
- Graph
相似题
- DFS
- 图
- 543. Diameter of Binary Tree
####
#### 代码链接
all_paths_from_source_to_target
此文原链接:
https://xiangxiaogang.com/2017/01/06/leetcode-0797/
点击阅读原文可访问
如果还没有关注我，可以长按以下二维码关注
