代码随想录-算法训练营-番外(图论01:图论理论基础,所有可到达的路径)
day01 图论part01
今日任务:图论理论基础/所有可到达的路径
代码随想录图论视频部分还没更新
https://programmercarl.com/kamacoder/图论理论基础.html#图的基本概念day01
所有可达路径
邻接矩阵
import java.util.Scanner;import java.util.List;import java.util.ArrayList;public class Main{static List<List<Integer>> result = new ArrayList<>();static List<Integer> path = new ArrayList<>();public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[][] graph = new int[n + 1][n + 1];for(int i = 0; i < m; i++){graph[sc.nextInt()][sc.nextInt()] = 1;}path.add(1); //先加一个节点dfs(graph, 1, n); if (result.isEmpty()) System.out.println(-1);for(List<Integer> pa : result){for (int i = 0; i < pa.size() - 1; i++) {System.out.print(pa.get(i) + " ");}System.out.println(pa.get(pa.size() - 1));} }private static void dfs(int[][] graph, int x, int n){//n就是结束节点if(x == n){result.add(new ArrayList(path));return;}for(int i = 1; i <= n; i++){if (graph[x][i] == 1) { path.add(i); dfs(graph, i, n); path.remove(path.size() - 1); }}return;}}
邻接表
//感觉graph不用LinkedList而是直接用ArrayList也可以,因为这个场景下不涉及什么增删改而基本都是访问import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Scanner;public class Main {static List<List<Integer>> result = new ArrayList<>(); // 收集符合条件的路径static List<Integer> path = new ArrayList<>(); // 1节点到终点的路径public static void dfs(List<LinkedList<Integer>> graph, int x, int n) {if (x == n) { // 找到符合条件的一条路径result.add(new ArrayList<>(path));return;}for (int i : graph.get(x)) { // 找到 x指向的节点path.add(i); // 遍历到的节点加入到路径中来dfs(graph, i, n); // 进入下一层递归path.remove(path.size() - 1); // 回溯，撤销本节点}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();// 节点编号从1到n，所以申请 n+1 这么大的数组List<LinkedList<Integer>> graph = new ArrayList<>();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);}path.add(1); // 无论什么路径已经是从1节点出发dfs(graph, 1, n); // 开始遍历// 输出结果if (result.isEmpty()) System.out.println(-1);for (List<Integer> pa : result) {for (int i = 0; i < pa.size() - 1; i++) {System.out.print(pa.get(i) + " ");}System.out.println(pa.get(pa.size() - 1));}}}
感谢大佬分享:
代码随想录算法训练营第五十天|Day50 图论_本关任务:创建邻接表存储的无向图,并输出图的邻接表。-CSDN博客