当前位置：首页 > news >正文

代码随想录算法训练营第50天|卡码网 98. 所有可达路径

news 2025/11/24 7:39:36

1.卡码网 98. 所有可达路径

题目链接：https://kamacoder.com/problempage.php?pid=1170
文章链接：https://www.programmercarl.com/kamacoder/0098.所有可达路径.html#总结

1.图的存储
本题我们使用邻接表或者邻接矩阵都可以，因为后台数据并没有对图的大小以及稠密度做很大的区分。
若是邻接矩阵：
邻接矩阵使用二维数组来表示图结构。邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。
本题我们会有n 个节点，因为节点标号是从1开始的，为了节点标号和下标对齐，我们申请（n + 1） *（ n + 1）这么大的二维数组。

Scanner src = new Scanner(System.in);
int n = src.nextInt();// 节点数
int m = src.nextInt();// 边数// 邻接矩阵
int[][] matrix = new int[n+1][n+1];// 输入m个边，构造方式如下：
for (int i=0;i<m;i++) {int r = src.nextInt();int c = src.nextInt();matrix[r][c] = 1;
}

若是邻接表：
邻接表使用数组 + 链表的方式来表示。邻接表是从边的数量来表示图，有多少边才会申请对应大小的链表。有多少节点数申请对应大小的一维数组或列表。

Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();// 节点编号从1到n，所以申请 n+1 这么大的数组或列表
List<LinkedList<Integer>> graph = new ArrayList<>(n + 1);
for (int i = 0; i <= n; i++) {graph.add(new LinkedList<>());
}while (m-- > 0) {int s = scanner.nextInt();int t = scanner.nextInt();// 使用邻接表表示 s -> t 是相连的graph.get(s).add(t);
}

以下使用邻接矩阵。

2.深度优先搜索
a.确认递归函数，参数
首先dfs函数一定要存一个图，用来遍历的，需要存一个目前我们遍历的节点，定义为x。
还需要存一个n，表示终点，我们遍历的时候，用来判断当 x==n 时候标明找到了终点。

static List<List<Integer>> res = new ArrayList<>(); // 收集符合条件的路径
static List<Integer> lineList = new ArrayList<>(); // 0节点到终点的路径
// r：目前遍历的节点
// matrix：存当前的图
// n：终点public static void process(int[][] matrix,int r,int n) {}

b.确认终止条件
当目前遍历的节点为最后一个节点 n 的时候就找到了一条从出发点到终止点的路径。

// 当前遍历的节点x 到达节点n 
if (r == n) {res.add(new ArrayList(lineList));// 找到符合条件的一条路径return;
}

c.处理目前搜索节点出发的路径。走当前遍历节点x的下一个节点。
首先是要找到 x节点指向了哪些节点呢？
接下来就是将选中的x所指向的节点，加入到单一路径来。
最后递归、回溯。

for (int i=1;i<=n;i++) {// 遍历节点r链接的所有节点if (matrix[r][i] == 1) { //寻找边 找到 r链接的节点// 处理节点lineList.add(i);// 遍历到的节点加入到路径中来// 递归process(matrix,i,n);// 进入下一层递归// 撤销当前节点 回溯lineList.remove(lineList.size()-1);}
}

总代码：

// 邻接矩阵
public class Main{static List<List<Integer>> res = new ArrayList<>();static List<Integer> lineList = new ArrayList<>();public static void main(String[] args) {Scanner src = new Scanner(System.in);int N = src.nextInt();// 节点数int M = src.nextInt();// 边数// 邻接矩阵int[][] matrix = new int[N+1][N+1];for (int i=0;i<M;i++) {int r = src.nextInt();int c = src.nextInt();matrix[r][c] = 1;}lineList.add(1);process(matrix,1,N);// 输出结果if (res.isEmpty()) System.out.println(-1);for (List<Integer> pa : res) {for (int i = 0; i < pa.size() - 1; i++) {System.out.print(pa.get(i) + " ");}System.out.println(pa.get(pa.size() - 1));}}public static void process(int[][] matrix,int r,int n) {if (r == n) {res.add(new ArrayList(lineList));return;}for (int i=1;i<=n;i++) {if (matrix[r][i] == 1) { //寻找边// 处理节点lineList.add(i);// 递归process(matrix,i,n);// 撤销当前节点 回溯lineList.remove(lineList.size()-1);}}}}