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
图
1. Diameter of Binary Tree

代码链接

all_paths_from_source_to_target

此文原链接:

https://xiangxiaogang.com/2017/01/06/leetcode-0797/

点击阅读原文可访问

  如果还没有关注我，可以长按以下二维码关注

如果还没有关注我，可以长按以下二维码关注