KamaCoder 98 所有可达路径
题目链接：98.所有可达路径
文档讲解：图论理论基础 | 图论深度优先搜索理论 | 代码随想录
视频讲解：图论理论基础 | 图论深度优先搜索理论 | 所有可达路径
思路与感想：这是我接触图论的第一题，用到了图论中的深搜进行解决，卡哥说这是深搜的一道裸题，我从中知道了图论深搜的模板其实就是之前回溯算法的模板，所以上手起来还是比较容易的。KamaCoder上面也做了一些题目了，对于ACM代码模式也有些熟悉起来了，听说图论上大部分题目都要在KamaCoder上做了，我也挺开心正好再强化一下ACM代码模式，到时候面试的时候也不至于写的乱七八糟。依旧三部曲，第一步确定深搜函数的参数，一般就graph，当前遍历的节点x，path的终点n。这个graph一般在力扣的核心代码模式里面会直接给出，但是ACM模式就要自己去创建这个graph。卡哥介绍了三种图的构造方法，第一种是朴素存储，就是创建一个n * 2的数组，[[起点1，连接点1]，[起点1,连接点2]........]，当然也可以采用Map的key和value来记录这个连接，这种方法的优点在于比较灵活，缺点也很明显就是当你要取到某个起点的连接方式的时候你需要遍历这个数组，就是On的时间复杂度。第二种方法就是邻接矩阵，创建一个n * n的二维数组，graph[起点1][连接点1]、graph[起点3][连接点2]，这样通过两个下标值就可以确定从某个点指向某个点的连接了，值得话可以设置为权值，如果没权值光有连接就设置为1，至于0就说明两个点之间没有连接。这个方法的缺点就在于空间复杂度为On2，而且很容易造成空间浪费，极端地来讲如果n很大，但是呢里面只有两个点之间存在连接，相当于整个数组可能只有那个位置值不为0，其它都是0了。第三种方法就是邻接表，可以想象成左边由一个长度为n的纵向一维数组，每个位置右边都有一个长度不定的链表，链表存储的是左边数组里面的所有可以连接的点，个人感觉很想哈希表处理哈希冲突时拉链法形成的结构。这个优点就是左边一维数组空间虽定，但右边链表可以根据实际情况分配容量，不至于没有连接却分配空间浪费了。总结一下适用情形，如果图中边比较少点比较多的情况就可以用邻接表，如果点和边都很多就可以用邻接矩阵。一般来说都推荐邻接矩阵，因为邻接表既有数组又有链表创建起来会比较麻烦。接下来讲讲在ACM模式下解决这道题目需要注意的点。首先就是导包操作，记得导入util下的List和ArrayList，这俩不能直接用。深搜函数里面的for循环操作其实就是遍历以当前遍历的点x的所有可能连接点，而这一标志就是graph[x][i]等于1，就说明有这个连接。最后输出result的时候记得每个路径的最后一个数输出的时候后面不能带空格所有要特殊打印。
收获：1.重温ACM代码模式；2.图论中的深搜模板；3.图论深搜过程；4.图论创建的三种方法
import java.util.Scanner; import java.util.List; import java.util.ArrayList; public class Main { static List<List<Integer>> result = new ArrayList<>(); // 记录所有有效path static List<Integer> path = new ArrayList<>(); // 记录每一个path public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 接收N个节点数 int m = sc.nextInt(); // 接收M条连接 int[][] graph = new int[n + 1][n + 1]; // 创建邻接矩阵 for (int i = 0; i < m; i++) { int s = sc.nextInt(); int t = sc.nextInt(); graph[s][t] = 1; // 邻接矩阵初始化，有连接就初始化为1 } path.add(1); // 开启深搜 dfs(graph, 1, n); if (result.isEmpty()) { // 如果搜出来结果为空说明没有路径能够从1到n System.out.println(-1); } for (List<Integer> pa : result) { // 遍历所有可能的path for (int i = 0; i < pa.size() - 1; i++) { // 把path中的元素一个个输出 System.out.print(pa.get(i) + " "); } System.out.println(pa.get(pa.size() - 1)); // 最后一个元素特殊处理，尾部不留空格 } } public static void dfs(int[][] graph, int x, int n) { if (x == n) { // 当前遍历的节点正好是path终点，收获结果 result.add(new ArrayList<>(path)); return; } for (int i = 1; i <= n; i++) { // 以当前遍历节点x为基准，遍历它的所有连接 if (graph[x][i] == 1) { // 必须要有连接 path.add(i); // 添加与它连接的元素到path中 dfs(graph, i, n); // 往下深搜递归 path.remove(path.size() - 1); // 回溯撤销上一次移动 } } } }LeetCode 797 所有可能的路径
题目链接：797.所有可能的路径
思路与感想：本题是力扣上的，采用的核心代码模式，所以无需进行图的创建，题目直接在方法中给了graph。这一题跟上一题的区别在于这个终点需要自己求，然后graph的含义优点不一样，核心思路其实都是一样的。
收获：1.不同含义的graph如何体现在深搜中
// DFS深搜 class Solution { List<Integer> path = new ArrayList<>(); // 存储每一个有效路径 List<List<Integer>> result = new ArrayList<>(); // 存储所有有效路径 public List<List<Integer>> allPathsSourceTarget(int[][] graph) { int end = 0; // path的终点 for (int i = 0; i < graph.length; i++) { if (graph[i].length == 0) { continue; } end = Math.max(end,graph[i][graph[i].length - 1]); // 是graph中的最大值 } path.add(0); // 每一个path都是从起点0开始的 dfs(graph, 0, end); // 开启深搜，0作为起点，graph[graph.length - 2][0] + 1作为n个节点 return result; } void dfs(int[][] graph, int x, int end) { if (x == end) { // 当前遍历到的x等于终点值n - 1，注意n是节点个数，n - 1才是终点值 result.add(new ArrayList<>(path)); // 收获有效路径 return; } for (int i = 0; i < graph[x].length; i++) { // 遍历当前遍历到的x点在graph中连接的点 path.add(graph[x][i]); // 添加进path中 dfs(graph, graph[x][i], end); // 进入下一层递归 path.remove(path.size() - 1); // 回溯撤销最近一次移动 } } }今天算法花了大概五个小时，主要看了图论一些入门概念还有深搜广搜思想，写了两道深搜的题目。早上实验课的爬虫半个小时代码就跑通了之后就一直听歌看并发那块的八股，感觉还是很有收获的。把线程进程还有并发并行异步这些小概念重温了一下，以及线程的六种状态，用户态和内核态两种CPU特权级别的区别，虚拟线程和普通线程之间的区别，以及乐观锁和悲观锁以及基于乐观锁的无锁并发，以及其中的CAS算法，虽然好多地方都没看懂，不过JUC这块既然是重点就先做一个大致了解后面再照着源码边理解边背。下午感觉状态不好而且犯困不想去健身，结果一下课还是跑到健身房去了，下午把务虚笔记看完了，没怎么看懂，下一本拜读毕飞宇老师的推拿。
