算法打卡：第十一章 图论part01
今日收获：图论理论基础，深搜理论基础，所有可达路径，广搜理论基础（理论来自代码随想录）
1. 图论理论基础
（1）邻接矩阵
邻接矩阵存储图，x和y轴的坐标表示节点的个数
优点：
- 表达方式简单，易于理解
- 易于检查两个顶点间是否存在边
- 适合稠密图，此时邻接矩阵是一种空间效率较高的表示方法，矩阵中的格子利用率高。
缺点：
- 遇到稀疏图，会导致申请过大的二维数组造成空间浪费。
- 遍历边的时候需要遍历整个n * n矩阵，造成时间浪费。
（2）邻接表
邻接表使用 数组 + 链表 的方式来表示。数组的长度是节点个数，节点的边用链表连接。
优点：
- 对于稀疏图的存储，只需要存储边，空间利用率高
- 遍历节点连接情况相对容易
缺点：
- 检查任意两个节点间是否存在边，效率相对低，需要遍历数组中某个节点连接的整个链表
- 实现相对复杂，不易理解
（3）图的遍历方式
- 深度优先搜索（dfs）
- 广度优先搜索（bfs）
2. 深搜理论基础
（1）思想
一条道走到黑，不到黄河不死心，不撞南墙不回头（走投无路或者找到了就回到上一个节点再重复，即回溯）
（2）代码框架
void dfs(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本节点所连接的其他节点) {
处理节点;
dfs(图，选择的节点); // 递归
回溯，撤销处理结果
}
}3. 所有可达路径
题目链接：98. 所有可达路径
思路：回溯算法
（1）邻接矩阵
a. 首先根据节点的个数创建二维数组，然后遍历节点之间的边，如果存在边则二维数组对应位置设为1。
b. 在回溯函数中，遍历所有的节点，如果当前所处的节点位置和遍历节点之间存在边，则将当前遍历节点添加到路径中，递归调用回溯函数，函数结束后取消路径中的当前遍历节点
c. 如果当前所处的节点位置是终点，则收获结果
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
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++){
int s=sc.nextInt();
int t=sc.nextInt();
graph[s][t]=1;
}
path.add(1); // 出发点
dfs(graph,1,N); // 开始深度搜索
// 输出结果
if (result.size()==0){
System.out.println("-1");
}else {
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));
}
}
}
public static void dfs(int[][] graph,int current,int N){
if (current==N){ // 走到终点
result.add(new ArrayList<>(path));
return;
}
for (int i=1;i<N+1;i++){ // 从小到大遍历节点
if (graph[current][i]==1){ // 存在边
path.add(i); // 走到下一个节点
dfs(graph,i,N);
path.remove(path.size()-1); // 回溯
}
}
}
}（2）邻接表
a. 首先创建存储整型链表的列表作为图，将列表中的每个节点都添加一个链表。遍历边时，将结尾节点添加到列表中起点的链表中。
b. 回溯函数中，遍历当前所处位置节点的连接节点时，获取其链表，然后再遍历链表中的元素
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.LinkedList;
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();
// 存储图的邻接表
List<LinkedList<Integer>> graph=new ArrayList<>(N+1);
for (int i=0;i<N+1;i++){
graph.add(new LinkedList<Integer>());
}
for (int i=0;i<M;i++){
int s=sc.nextInt();
int t=sc.nextInt();
graph.get(s).add(t);
}
path.add(1); // 出发点
dfs(graph,1,N); // 开始深度搜索
// 输出结果
if (result.size()==0){
System.out.println("-1");
}else {
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));
}
}
}
public static void dfs(List<LinkedList<Integer>> graph,int current,int N){
if (current==N){ // 走到终点
result.add(new ArrayList<>(path));
return;
}
for (int i:graph.get(current)){ // 从小到大遍历节点
path.add(i); // 走到下一个节点
dfs(graph,i,N);
path.remove(path.size()-1); // 回溯
}
}
}总结：打印二维数组最好使用增强for循环遍历
（3）相似题目
题目链接：797. - 力扣（LeetCode）
思路：回溯算法。首先添加起点0，当前位置也为0，然后遍历当前位置连接的节点，将连接节点加入路径列表中再调用函数深度搜索；当前连接节点上的路径深度搜索之后，去掉路径列表中的当前节点。
方法：
class Solution {
List<List<Integer>> result=new ArrayList<>();
List<Integer> path=new ArrayList<>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
int n=graph.length-1;
path.add(0);
dfs(graph,0,n);
return result;
}
public void dfs(int[][] graph,int current,int n){
if (current==n){
result.add(new ArrayList<>(path));
return;
}
for (int i:graph[current]){
path.add(i);
dfs(graph,i,n);
path.remove(path.size()-1);
}
}
}4. 广搜理论基础
思想：一圈一圈的搜索，每次遍历当前节点连接的所有节点
使用场景：解决两点之间的最短路径问题
解决方式：用队列/栈/数组，只要能保存遍历过的元素。用队列时，先加入起始节点并标记为访问；然后遍历队列，计算当前节点的连接节点，如果连接节点没有被访问过则加入队列。