算法打卡：第十一章 图论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. 广搜理论基础

思想：一圈一圈的搜索，每次遍历当前节点连接的所有节点

使用场景：解决两点之间的最短路径问题

解决方式：用队列/栈/数组，只要能保存遍历过的元素。用队列时，先加入起始节点并标记为访问；然后遍历队列，计算当前节点的连接节点，如果连接节点没有被访问过则加入队列。