第十一章：图论part01
图论理论基础
注意
- 图的构造：邻接矩阵和邻接表
深搜理论基础
- 注意一下回溯的过程，使用递归最方便。
- 深搜三部曲：
- 确认递归函数，参数
一般情况，深搜需要 二维数组数组结构保存所有路径，需要一维数组保存单一路径，这种保存结果的数组，我们可以定义一个全局变量，避免让我们的函数参数过多。
例如这样：
List<List<Integer>> result = new ArrayList<>(); // 保存符合条件的所有路径
List<Integer> path = new ArrayList<>(); // 起点到终点的路径
void dfs(int[][] graph, int currentNode) {}
- 确认终止条件
if (终止条件) {
存放结果;
return;
}
另外，其实很多dfs写法，没有写终止条件，其实终止条件写在了， 下面dfs递归的逻辑里了，也就是不符合条件，直接不会向下递归。
- 处理目前搜索节点出发的路径
一般这里就是一个for循环的操作，去遍历 目前搜索节点 所能到的所有节点。
for (选择：本节点所连接的其他节点) {
处理节点;
dfs(图，选择的节点); // 递归
回溯，撤销处理结果
}
98. 所有可达路径
图的储存
邻接矩阵
邻接矩阵 使用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。
本题我们会有n 个节点，因为节点标号是从1开始的，为了节点标号和下标对齐，我们申请 n + 1 * n + 1 这么大的二维数组。
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 节点数
int[][] graph = new int[n + 1][n + 1]; // 邻接矩阵，初始化为0
输入m个边，构造方式如下：
int m = scanner.nextInt(); // 边数
while (m-- > 0) {
int s = scanner.nextInt();
int t = scanner.nextInt();
graph[s][t] = 1; // 表示节点s指向节点t
}
邻接表
List<List<Integer>> graph = new ArrayList<>(n + 1); // 初始化邻接表
for (int i = 0; i <= n; i++) {
graph.add(new LinkedList<>());
}
while (m-- > 0) {
int s = scanner.nextInt();
int t = scanner.nextInt();
graph.get(s).add(t); // 表示s -> t是相连的
}
本题我们使用邻接表 或者 邻接矩阵都可以，因为后台数据并没有对图的大小以及稠密度做很大的区分。
深搜三部曲
- 确认递归函数，参数
首先我们dfs函数一定要存一个图，用来遍历的，需要存一个目前我们遍历的节点，定义为x。
还需要存一个n，表示终点，我们遍历的时候，用来判断当 x==n 时候 标明找到了终点。
（其实在递归函数的参数 不容易一开始就确定了，一般是在写函数体的时候发现缺什么，参加就补什么）
至于 单一路径 和 路径集合 可以放在全局变量
List<List<Integer>> result = new ArrayList<>(); // 收集符合条件的路径
List<Integer> path = new ArrayList<>(); // 1节点到终点的路径
// x：目前遍历的节点
// graph：存当前的图
// n：终点
void dfs(List<List<Integer>> graph, int x, int n) {}
- 确认终止条件
什么时候我们就找到一条路径了？
当目前遍历的节点 为 最后一个节点 n 的时候 就找到了一条 从出发点到终止点的路径。
if (x == n) { // 找到符合条件的一条路径
result.add(new ArrayList<>(path));
return;
}
- 处理目前搜索节点出发的路径
接下来是走 当前遍历节点x的下一个节点。
首先是要找到 x节点指向了哪些节点呢？ 遍历方式是这样的：
for (int i : graph.get(x))
接下来就是将 选中的x所指向的节点，加入到 单一路径来。
在使用邻接矩阵表示图的结构时，graph[x][i]表示从节点 x 到节点 i 是否存在一条边。邻接矩阵是一种二维数组，假设有 n 个节点，那么这个矩阵的大小就是 n x n。矩阵中的每个元素 graph[x][i] 的含义如下：
- 如果 graph[x][i] 为 1，表示节点 x 和节点 i 之间存在一条边。
- 如果 graph[x][i] 为 0，表示节点 x 和节点 i 之间不存在一条边。
if (graph[x][i] == 1) { // 找到 x链接的节点
path.add(i); // 遍历到的节点加入到路径中来
}
进入下一层递归
dfs(graph, i, n); // 进入下一层递归
最后就是回溯的过程，撤销本次添加节点的操作。
path.remove(path.size() - 1);
该过程整体代码：
for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点
if (graph[x][i] == 1) { // 找到 x链接的节点
path.add(i); // 遍历到的节点加入到路径中来
dfs(graph, i, n); // 进入下一层递归
path.remove(path.size() - 1); // 回溯，撤销本节点
}
}
打印结果
例如示例输出是：
[1 3 5]而不是 [1 3 5 ]
即 5 的后面没有空格！
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));
}
}
}
邻接矩阵写法
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 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); // 无论什么路径已经是从1节点出发
dfs(graph, 1, n); // 开始遍历
// 输出结果
if(result.size() == 0) 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.LinkedList;
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(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 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; i++) {
graph.add(new LinkedList<>());
}
while(m-- > 0){
int s = sc.nextInt();
int t = sc.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));
}
}
}
广搜理论基础
使用场景：适合于解决两个点之间的最短路径问题。因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。
也有一些问题是广搜 和 深搜都可以解决的，例如岛屿问题，这类问题的特征就是不涉及具体的遍历方式，只要能把相邻且相同属性的节点标记上就行。
代码框架
其实，我们仅仅需要一个容器，能保存我们要遍历过的元素就可以，那么用队列，还是用栈，甚至用数组，都是可以的。
用队列的话，就是保证每一圈都是一个方向去转，例如统一顺时针或者逆时针。
因为队列是先进先出，加入元素和弹出元素的顺序是没有改变的。
如果用栈的话，就是第一圈顺时针遍历，第二圈逆时针遍历，第三圈有顺时针遍历。
因为栈是先进后出，加入元素和弹出元素的顺序改变了。
那么广搜需要注意 转圈搜索的顺序吗？ 不需要！
模板代码
以这个图为例
image.png
import java.util.LinkedList;
import java.util.Queue;
public class BFS {
static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 表示四个方向
public static void bfs(char[][] grid, boolean[][] visited, int x, int y) {
Queue<int[]> queue = new LinkedList<>(); // 定义队列
queue.offer(new int[]{x, y}); // 起始节点加入队列
visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点
while (!queue.isEmpty()) { // 开始遍历队列里的元素
int[] cur = queue.poll(); // 从队列取元素
int curx = cur[0];
int cury = cur[1]; // 当前节点坐标
for (int i = 0; i < 4; i++) { // 开始向当前节点的四个方向左右上下去遍历
int nextx = curx + dir[i][0];
int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标
// 坐标越界了，直接跳过
if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;
// 如果节点没被访问过
if (!visited[nextx][nexty]) {
queue.offer(new int[]{nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点
visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问
}
}
}
}
public static void main(String[] args) {
char[][] grid = {
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}
};
boolean[][] visited = new boolean[grid.length][grid[0].length];
bfs(grid, visited, 0, 0);
// 输出 visited 数组查看结果
for (int i = 0; i < visited.length; i++) {
for (int j = 0; j < visited[0].length; j++) {
System.out.print(visited[i][j] ? "T " : "F ");
}
System.out.println();
}
}
}
