本文主要是介绍代码随想录算法训练营第50天|卡码网 98. 所有可达路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
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);}}}}
这篇关于代码随想录算法训练营第50天|卡码网 98. 所有可达路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!