Graph 🌼

foundation:

https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E5%9B%BE%E8%AE%BA%E6%B7%B1%E6%90%9C%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.md

  • dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。
  • bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。

797. All Paths From Source to Target

Medium

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:

img

1
2
3
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    List<List<Integer>> res;
    List<Integer> temp;
    public void dfs(int[][] graph, int node){ 
        //  here the node is current node that already been added into temp
        if(node == graph.length - 1){
            res.add(new ArrayList<>(temp));
            return;
        }

        for(int i = 0 ; i < graph[node].length; i++){
            temp.add(graph[node][i]); //graph[node][i] is the next node, add the next node
            dfs(graph, graph[node][i]); // do the same thing to the next node
            temp.remove(temp.size() - 1); // back track, temp.size() - 1 is the index
        }
    }

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        res = new ArrayList<>();
        temp = new ArrayList<>();
        temp.add(0); // !!! add 0 into temp
        dfs(graph, 0);
        return res;

    }
}

[toc]