簡單來說樹就是無向、連通、無環的圖，所以前面的DFS、BFS概念可以延用，只不過要注意圖可能會出現環(cycle)所以需要額外變數來記錄是否走過，以免出現無窮迴圈。

DFS V.S. BFS

照慣例刷個題練習一下

列出所有組合適合DFS

Leetcode 797. All Paths From Source to Target

題目：給一個有向無環圖(DAG)列出所有路徑

輸入：graph = [[1,2],[3],[3],[]]

輸出：[0,1,3],[0,2,3]]

限制：

• n == graph.length

• 2 <= n <= 15

• 0 <= graph[i][j] < n

• graph[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.

DFS解法：因為有向無環所以沒有重複走的問題，我們使用深度優先每題路徑走完再換另一條。

// [[4,3,1],[3,2,4],[3],[4],[]] n=5 from 0 to 4
// 1st 0->4
// 2nd 0->3->4
// 3rd-1 0->1->3-4
// 3rd-2 0->1->2->3->4
// 3rd-3 0->1->4

impl Solution {
    pub fn all_paths_source_target(graph: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut ans = Vec::new();
        let mut path = vec![0];
        let n = graph.len() as i32;
        Self::back_tracking(&graph,0,n-1,&mut path,&mut ans);
        ans
    }

    pub fn back_tracking(graph:&Vec<Vec<i32>>,node:i32, target:i32, path:&mut Vec<i32>,ans:&mut Vec<Vec<i32>>) {
        if node==target {
            ans.push(path.clone());
            return
        }
        for &i in &graph[node as usize] {
            path.push(i);
            Self::back_tracking(graph,i,target,path,ans);
            path.pop();
        }
    }
}

BFS解法：從起點開始，列出目前能走的路再從目前能走的路向外延伸

//BFS
//init graph=[[1,2],[3],[3],[]] path:[[0]] ans:[]
//loop path take[0] BFS graph[0] path=[[0,1],[0,2]] ans:[]
//loop path take[0,1] BFS graph[1] push element==n-1 [0,1,3] add to ans path=[[0,2]] ans:[[0,1,3]]
//loop path take[0,2] BFS graph[2] push element==n-1 [0,2,3] path=[] ans:[[0,1,3],[0,2,3]]
use std::collections::VecDeque;
impl Solution {
    pub fn all_paths_source_target(graph: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let finish = graph.len() as i32 -1;
        let mut deque=VecDeque::new();
        let mut ans:Vec<Vec<i32>> = Vec::new();

        deque.push_back(vec![0]);
        while deque.len()>0 {
            let Some(front)=deque.pop_front() else { break};
            let last = *front.last().expect("must have 0");
            for &element in &graph[last as usize] {
                let mut new_path=front.clone();
                new_path.push(element);
                // let new_path=vec![1];
                if(element==finish){
                    ans.push(new_path);
                } else {
                    deque.push_back(new_path);
                }
            }
        }
        ans 
    }
}

DFS vs. BFS 比較

• 時間複雜度：都是** **O(2^n )

• 空間複雜度：

  • DFS: O(n)，一條路徑。

  • BFS: O(2^n)，全部路徑。

最短路徑適合BFS

我們用之前提到的leetcode1091為例，如果改成DFS，會變成比較每一條走到終點的路徑長度全部比完才會回傳答案，相比BFS第一個走到的就是最短路徑時間，DFS效率沒那麼好。

// use DFS to fin shortest path
//start from 0 to 8 directions[(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)]
//if direction (1,0) is 0 go ahead until (n-1,n-1)
// if position is 1 or path bigger than shortest path return
// everytime achive update the shortest path
impl Solution {
    pub fn shortest_path_binary_matrix(mut grid: Vec<Vec<i32>>) -> i32 {
        // check start and finish !=1
        let n = grid.len();
        if(grid[0][0]==1 || grid[n-1][n-1]==1){
            return -1
        }
        //start DFS
        let mut shortest = i32::MAX;
        const directions:[(i32, i32); 8]= [
            (1,0),
            (1,1),
            (0,1),
            (-1,1),
            (-1,0),
            (-1,-1),
            (0,-1),
            (1,-1)
        ];
        Self::DFS(&mut grid,0,0,1,&mut shortest,&directions);
        if(shortest==i32::MAX){
            return -1
        }
        return shortest
    }

    pub fn DFS(grid:&mut Vec<Vec<i32>>, x:i32, y:i32, mut path:i32, shortest: &mut i32,directions:&[(i32, i32); 8]){
        
        if(path>=*shortest){
            return
        }
        if(x as usize==grid[0].len()-1 && y as usize==grid.len()-1){
            *shortest = *shortest.min(&mut path);
            return
        }
        grid[x as usize][y as usize] = 1;
        for (dx,dy) in directions {
            // check boundary
            if(x+dx<0 || x+dx>=grid[0].len() as i32 || y+dy<0 || y+dy>=grid.len() as i32){
                continue
            }
            //check position is 1
            if(grid[(x+dx) as usize][(y+dy) as usize]==1){
                continue
            }
            Self::DFS(grid,x+dx,y+dy,path+1,shortest,directions)
        }
        grid[x as usize][y as usize] = 0;
    }
}

跑測資再matrix很大的情況下會超時

Day27總結

1. Graph DFS、BFS概念跟tree一樣，但需注意是否會重複走訪形成無窮迴圈
2. DFS適合解決列出所有組合、排列
3. BFS適合解決最短路徑