西安有专业制作网站的公司吗,瀑布流分享网站源代码下载,php网站编程,财务公司网站建设day01 图论part01
今日任务:图论理论基础/所有可到达的路径
代码随想录图论视频部分还没更新
https://programmercarl.com/kamacoder/图论理论基础.html#图的基本概念
day01
所有可达路径 邻接矩阵 import java.util.Scanner;import java.util.List;import java.util.ArrayL…day01 图论part01
今日任务:图论理论基础/所有可到达的路径
代码随想录图论视频部分还没更新
https://programmercarl.com/kamacoder/图论理论基础.html#图的基本概念
day01
所有可达路径 邻接矩阵 import java.util.Scanner;import java.util.List;import java.util.ArrayList;public class Main{static ListListInteger result new ArrayList();static ListInteger 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(ListInteger 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 ListListInteger result new ArrayList(); // 收集符合条件的路径static ListInteger path new ArrayList(); // 1节点到终点的路径public static void dfs(ListLinkedListInteger 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所以申请 n1 这么大的数组ListLinkedListInteger 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 (ListInteger 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博客
