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博客