图论 | part01

98. 可达路径

给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个程序，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。

【输入描述】

第一行包含两个整数 N，M，表示图中拥有 N 个节点，M 条边

后续 M 行，每行包含两个整数 s 和 t，表示图中的 s 节点与 t 节点中有一条路径

【输出描述】

输出所有的可达路径，路径中所有节点的后面跟一个空格，每条路径独占一行，存在多条路径，路径输出的顺序可任意。

如果不存在任何一条路径，则输出 -1。

注意输出的序列中，最后一个节点后面没有空格！ 例如正确的答案是1 3 5,而不是1 3 5， 5后面没有空格！

【输入示例】

5 5 1 3 3 5 1 2 2 4 4 5

【输出示例】

1 3 5 1 2 4 5

提示信息

用例解释：

有五个节点，其中的从 1 到达 5 的路径有两个，分别是 1 -> 3 -> 5 和 1 -> 2 -> 4 -> 5。

因为拥有多条路径，所以输出结果为：

1 3 5 1 2 4 5

或

1 2 4 5 1 3 5

都算正确。

数据范围：

• 图中不存在自环
• 图中不存在平行边
• 1 <= N <= 100
• 1 <= M <= 500

public class Main { public static List<Integer> path = new ArrayList<>(); public static List<List<Integer>> res = new ArrayList<>(); public static void main(String[] args) { Scanner scanner = new Scanner(System.in); if (!scanner.hasNext()) return; // 防止空输入 int n = scanner.nextInt(); int m = scanner.nextInt(); int[][] graph = new int[n + 1][n + 1]; for (int i = 0; i < m; i++) { int s = scanner.nextInt(); int t = scanner.nextInt(); graph[s][t] = 1; } path.add(1); dfs(graph, 1, n); if (res.isEmpty()) { System.out.println(-1); } else { for (List<Integer> list : res) { for (int i = 0; i < list.size(); i++) { System.out.print(list.get(i)); if (i != list.size() - 1) { System.out.print(" "); } } System.out.println(); } } } public static void dfs(int[][] graph, int now, int end) { if (now == end) { res.add(new ArrayList<>(path)); return; } // 遍历所有可能的下一个节点 (1 到 n) for (int i = 1; i <= end; i++) { // 确保不越界，虽然上面修正了数组大小，但逻辑上 i 最大也就是 n if (graph[now][i] == 1) { path.add(i); dfs(graph, i, end); path.remove(path.size() - 1); // 回溯 } } } }

解题：

本题使用的是深度优先搜索方法

1. 输入处理：

• • 读取节点数 NN和边数 MM。
  • 使用二维数组int[][] graph = new int[n + 1][n + 1]构建邻接矩阵。graph[s][t] = 1表示存在一条从节点 ss指向节点 tt的有向边。
  • 注意：数组大小设为 N+1N+1 是为了方便直接使用 1-based 的节点编号，避免索引转换。

1. 初始化搜索：

• • path.add(1);：将起点 1 加入当前路径。
  • dfs(graph, 1, n);：从节点 1 开始进行深度优先搜索，目标是节点 NN。

1. 结果输出：

• • 检查res是否为空。
  • 如果为空，说明没有找到任何路径，输出-1。
  • 如果不为空，遍历res中的每一条路径，按格式打印（节点间空格分隔，行末无空格）。

在DFS中

• 终止条件：当now == end时，说明已经成功走到终点。此时将path的一个新副本（new ArrayList<>(path)）加入结果集res。必须新建副本，因为path对象在后续回溯中会被修改。
• 遍历邻居：循环检查从 1 到 NN的所有节点i。
• 剪枝/判断：if (graph[now][i] == 1)确保只沿着存在的有向边走。
• 回溯机制：

1. 1. path.add(i)：进入下一层递归前，记录当前步骤。
   2. dfs(...)：深入探索。
   3. path.remove(...)：当递归返回（无论是找到终点还是无路可走），需要把最后加入的节点移除，恢复到进入该分支前的状态，以便尝试下一个可能的邻居节点。这是解决“所有路径”问题的关键。