图论① dfs | Java | LeetCode 797，Kama 98 邻接表实现(未完成)

797 所有可能路径

https://leetcode.cn/problems/all-paths-from-source-to-target/description/
输入：graph = [[1,2],[3],[3],[]]

题目分析，这里

class Solution {//这个不是二维数组，而是listList<List<Integer>> res = new ArrayList<List<Integer>>();List<Integer> path = new ArrayList<>();public List<List<Integer>> allPathsSourceTarget(int[][] graph) {path.add(0);dfs(graph, 0);return res;}public void dfs(int graph[][], int x) {if(x == graph.length-1) { //横向的所有节点res.add(new ArrayList<>(path));return;}//列for(int i=0; i<graph[x].length; i++) {path.add(graph[x][i]);dfs(graph, graph[x][i]);path.remove(path.size()-1);}}
}

Kama 98

题目链接 https://kamacoder.com/problempage.php?pid=1170

邻接矩阵实现

import java.util.*;public class Main {static List<List<Integer>> res = new ArrayList<List<Integer>>();static List<Integer> path = new ArrayList<Integer>();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循环for(int i=0; i<M; i++) {int s = sc.nextInt();int t = sc.nextInt();graph[s][t] = 1;}path.add(1);dfs(graph, 1);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 dfs(int[][]graph, int x) {//节点个数int n = graph.length-1;if(x == n) {res.add(new ArrayList<>(path));return;}for(int i=1; i<=n; i++) {if(graph[x][i] == 1) {path.add(i);dfs(graph ,i);path.remove(path.size()-1);}}}
}

出错点

1 与力扣上的题目不一样，首先需要自己设置输入输出

输入的时候，这里for循环是因为告知了有多少条有向边

for(int i=0; i<M; i++) {int s = sc.nextInt();int t = sc.nextInt();graph[s][t] = 1;
}

2 力扣直接给出了图 int graph[][]，而且输入样例中 输入：graph = [[1,2],[3],[3],[]]，直接表明这个二维数组不是 n×n 的，因此graph.length获得节点的个数，graph[index].length获得以节点index为起点 的边的总数，

• 力扣797
  

• 对比：在卡玛98题中，我们在用邻接矩阵创建图的时候，graph是n×n的：int[][]graph = new int[N+1][N+1];。因此在回溯（DFS）的时候，for循环条件不一样，也要多一个if判断
  

3 static的使用，在Kama的ACM模式下 public static void main(String[] args)是入口函数，直接运行了，因此这里定义的函数和变量都需要用 static描述，否则必须要先实例化类Main才能调用函数

4 Kama的输出：遍历 List<List<Integer>> res

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));}

邻接表实现(未完成)

LinkedList

链表是一种常见的数据结构，用于存储和组织数据。它由一系列节点（Node）组成，每个节点包含两个主要部分：数据域（Data）和指针域（Pointer）。

数据域存储节点所需的数据或信息，可以是任意类型的数据，如整数、字符、对象等。指针域则指向链表中的下一个节点，将节点连接起来形成链表结构。

链表中的节点并不一定按照物理上的连续位置存储，而是通过指针域相互连接。这使得链表能够灵活地插入、删除和修改节点，而无需像数组那样进行元素的移动。

链表的优点是可以高效地插入和删除节点，而无需移动其他节点。然而，由于链表中的节点不是连续存储的，访问特定位置的节点需要从头部开始遍历，因此随机访问的效率较低。

在Java中，LinkedList（链表）是Java集合框架提供的一个实现了List接口的类。它是基于双向链表结构实现的，可以用于存储和操作元素的有序集合。

【Java】链表LinkedList

LinkedList和ArrayList是Java集合框架中的两种不同的List实现。