day48 图论章节刷题Part01（深搜理论基础、98. 所有可达路径、广搜理论基础）
深搜理论基础
二叉树的递归法就是dfs，而二叉树的迭代法就是bfs（广度优先搜索）
与二叉树中的递归三部曲和回溯算法中的回溯三部曲一样，深搜也可以以三部曲的形式进行分析：
1、确认递归函数，参数
一般情况，深搜需要 二维数组数组结构保存所有路径，需要一维数组保存单一路径，这种保存结果的数组可以定义一个全局变量，避免让我们的函数参数过多。
void dfs (图，目前搜索的节点)
2、确认终止条件
终止条件很重要，死循环，栈溢出等这些问题都是因为终止条件没有想清楚。终止添加不仅是结束本层递归，同时也是收获结果的时候。
另外，很多dfs写法没有写终止条件，其实终止条件写在了下面dfs递归的逻辑里了，也就是不符合条件，直接不会向下递归。
3、处理目前搜索节点出发的路径
一般这里就是一个for循环的操作，去遍历 目前搜索节点 所能到的所有节点。
for (选择：本节点所连接的其他节点) {
处理节点;
dfs(图，选择的节点); // 递归
回溯，撤销处理结果
}
98. 所有可达路径
图的存储
图的存储方式有两种：邻接表和邻接矩阵。
邻接矩阵
邻接矩阵使用二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。
本题有n 个节点，因为节点标号是从1开始的，为了节点标号和下标对齐，申请 n + 1 * n + 1 的二维数组。
int[][] graph = new int[n + 1][n + 1];
输入m个边，构造方式如下：
for (int i = 0; i < m; i++) {
int s = scanner.nextInt();
int t = scanner.nextInt();
// 使用邻接矩阵表示无向图，1 表示 s 与 t 是相连的
graph[s][t] = 1;
}
邻接表
邻接表使用 数组 + 链表 的方式来表示。 邻接表是从边的数量来表示图，有多少边才会申请对应大小的链表。
首先构造一个数组，数组里的元素是一个链表。
// 节点编号从1到n，所以申请 n+1 这么大的数组
List<LinkedList<Integer>> graph = new ArrayList<>(n + 1);
输入m个边，构造方式如下：
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);
}
本题我们使用邻接表 或者 邻接矩阵都可以，因为后台数据并没有对图的大小以及稠密度做很大的区分。
深搜三部曲
1、确认递归函数，参数
dfs函数一定要存一个图（用来遍历），存一个目前我们遍历的节点，定义为x。还需要存一个n，表示终点，当 x==n 时候 标明找到了终点。（其实在递归函数的参数 不容易一开始就确定了，一般是在写函数体的时候发现缺什么，参加就补什么）
单一路径 和 路径集合 放在全局变量
2、确认终止条件
当目前遍历的节点 为 最后一个节点 n 的时候 就找到了一条 从出发点到终止点的路径。
3、处理目前搜索节点出发的路径
当前遍历节点x的下一个节点。首先是要找到 x节点指向了哪些节点，将选中的x所指向的节点，加入到 单一路径中，进入下一层递归，最后回溯，撤销本次添加节点的操作。
整体代码如下：
邻接矩阵
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main{
static List<List<Integer>> result=new ArrayList<>();
static List<Integer> path=new ArrayList<>();
public static void dfs(int[][] graph,int x,int 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);
}
}
}
public static void main (String[] args) {
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
int m=scan.nextInt();
int[][] graph=new int[n+1][n+1];
while(m-->0){
int s=scan.nextInt();
int t=scan.nextInt();
graph[s][t]=1;
}
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));
}
}
}
邻接链表
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.LinkedList;
public class Main{
static List<List<Integer>> result=new ArrayList<>();
static List<Integer> path=new ArrayList<>();
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)){
path.add(i);
dfs(graph,i,n);
path.remove(path.size()-1);
}
}
public static void main (String[] args) {
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
int m=scan.nextInt();
List<LinkedList<Integer>> graph=new ArrayList<>(n+1);
for (int i = 0; i <= n; i++) {
graph.add(new LinkedList<>());
}
while(m-->0){
int s=scan.nextInt();
int t=scan.nextInt();
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));
}
}
}
广搜理论基础
广搜的使用场景
广搜的搜索方式适合于解决两个点之间的最短路径问题。因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。
有一些问题是广搜 和 深搜都可以解决的，例如岛屿问题，这类问题的特征就是不涉及具体的遍历方式，只要能把相邻且相同属性的节点标记上就行。
代码框架
我们需要一个容器保存遍历过的元素，队列、栈、数组都可以。
用队列可以保证每一圈都是一个方向去转，例如统一顺时针或者逆时针；用栈就是第一圈顺时针遍历，第二圈逆时针遍历，第三圈又顺时针遍历。一般来说大家习惯用队列。