Day50--图论--98. 所有可达路径（卡码网），797. 所有可能的路径

Day50–图论–98. 所有可达路径（卡码网），797. 所有可能的路径

刷今天的内容之前，要先去《代码随想录》网站，先看完：图论理论基础和深度优先搜索理论基础。做完之后可以看题解。有余力，把广度优先搜索理论基础也看了。

98. 所有可达路径（卡码网）

方法：回溯

思路：

本题的方法是回溯，具体思路都在代码注释中已有体现。

递归三部曲：

1. 确定递归参数和返回值：private static void dfs(int node, int target)
2. 确定终止条件：如果遍历到的node就是末尾，得到一条path，返回。if (node == target) res.add(new ArrayList(path));
3. 递归中的处理操作：一个for循环，遍历当前node结点的邻接表nodeList。递归完，记得回溯！记得回溯！记得回溯！

import java.util.*;

public class Main {

    // 类变量，不用传递参数
    private static List<List<Integer>> graph = new ArrayList<>();
    private static List<List<Integer>> res = new ArrayList<>();
    private static List<Integer> path = new ArrayList<>();

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        // 创建n+1个，方便下标
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        // 输入边
        for (int i = 0; i < m; i++) {
            int from = in.nextInt();
            int to = in.nextInt();
            graph.get(from).add(to);
        }

        // 从1开始
        path.add(1);
        dfs(1, n);
        // 输出结果
        if (res.size() == 0) {
            System.out.println(-1);
        } else {
            print();
        }
    }

    private static void dfs(int node, int target) {
        // 如果该结点就是target，得到一条path，返回。
        if (node == target) {
            res.add(new ArrayList(path));
            return;
        }

        // 遍历这个node的邻接表nodeList
        List<Integer> nodeList = graph.get(node);
        for (int i : nodeList) {
            // path中加入元素
            path.add(i);
            // 下一层递归
            dfs(i, target);
            // 回溯：从path中移除元素
            path.remove(path.size() - 1);
        }
    }

    // 打印结果
    private static void print() {
        for (List<Integer> path : res) {
            // 先打第一个元素
            System.out.print(path.get(0));
            // 后面的元素都是空格+元素
            for (int i = 1; i < path.size(); i++) {
                System.out.print(" " + path.get(i));
            }
            // 打一个换行
            System.out.println("");
        }
    }
}

797. 所有可能的路径

思路：

和上一题是同一道题，不过不用自己处理输入和输出。

class Solution {

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int target = graph.length - 1;
        path.add(0);
        dfs(graph, 0, target);
        return res;
    }

    private void dfs(int[][] graph, int node, int target) {
        if (node == target) {
            res.add(new ArrayList(path));
            return;
        }

        for (int i = 0; i < graph[node].length; i++) {
            path.add(graph[node][i]);
            dfs(graph, graph[node][i], target);
            path.remove(path.size() - 1);
        }
    }
}