代码随想录Day50：图论（图论理论、深度搜索理论、所有可达路径、广度搜索理论）
一、图论理论
1.1图的种类：整体上一般分为有向图和无向图。此外还有加权有向/无向图
1.2度：无向图中有几条边连接该节点，该节点就有几度。在有向图中，每个节点有出度和入度。出度：从该节点出发的边的个数。入度：指向该节点边的个数。
1.3连通性：在图中表示节点的连通情况，我们称之为连通性。
无向图中，任何两个节点都是可以到达的，我们称之为连通图。如果有节点不能到达其他节点，则为非连通图
在有向图中，任何两个节点是可以相互到达的，我们称之为 强连通图。
在无向图中的极大连通子图称之为该图的一个连通分量。
在有向图中极大强连通子图称之为该图的强连通分量。
1.4图的构造（如何用代码来表示一个图）：一般使用邻接表、邻接矩阵 或者用类来表示。主要是 朴素存储、邻接表和邻接矩阵。
朴素存储，将所有边存下来。
好处：直观，把节点与节点之间关系很容易展现出来。
缺点：如果我们想知道 节点1 和 节点6 是否相连，我们就需要把存储空间都枚举一遍才行。需要全部枚举才知道链接情况。在深搜和广搜的时候，都不会使用这种存储方式。
图中有8条边，我们就定义 8 * 2的数组，即有n条边就申请n * 2这么大的数组。数组第一行：6 7，就表示节点6 指向 节点7，以此类推。
邻接矩阵，使用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。例如： grid[2][5] = 6，表示 节点 2 连接 节点5 为有向图，节点2 指向 节点5，边的权值为6。如果想表示无向图，即：grid[2][5] = 6，grid[5][2] = 6，表示节点2 与 节点5 相互连通，权值为6。
优点：
- 表达方式简单，易于理解
- 检查任意两个顶点间是否存在边的操作非常快
- 适合稠密图（点少边多），在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法。
缺点：
- 遇到稀疏图（点多边少），会导致申请过大的二维数组造成空间浪费 且遍历 边 的时候需要遍历整个n * n矩阵，造成时间浪费
邻接表，使用 数组 + 链表的方式来表示。 邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表。
优点：
- 对于稀疏图的存储，只需要存储边，空间利用率高
- 遍历节点连接情况相对容易
缺点：
- 检查任意两个节点间是否存在边，效率相对低，需要 O(V)时间，V表示某节点连接其他节点的数量。
- 实现相对复杂，不易理解
节点2 指向 节点4、节点3、节点5
节点3 指向 节点4
节点4指向节点1
1.5图的遍历方式
图的遍历方式基本是两大类：
- 深度优先搜索（dfs）
- 广度优先搜索（bfs）
区别：
- dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。
- bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。
二、深度搜索理论dfs
适用场景：岛屿问题，这类问题的特征就是不涉及具体的遍历方式，只要能把相邻且相同属性的节点标记上就行。（广搜 和 深搜都可以解决）
如图一，是一个无向图，我们要搜索从节点1到节点6的所有路径。
那么dfs搜索的第一条路径是这样的： （假设第一次延默认方向，就找到了节点6），图二
此时我们找到了节点6，（遇到目的地或者已经遍历过得节点），应该再去搜索其他方向了。 如图三：
路径2撤销了，改变了方向，走路径3（红色线）， 接着也找到终点6。 那么撤销路径2，改为路径3，在dfs中其实就是回溯的过程（这一点很重要，很多录友不理解dfs代码中回溯是用来干什么的）又找到了一条从节点1到节点6的路径，又到黄河了，此时再回头，下图图四中，路径4撤销（回溯的过程），改为路径5。
又找到了一条从节点1到节点6的路径，又到黄河了，此时再回头，下图图五，路径6撤销（回溯的过程），改为路径7，路径8 和 路径7，路径9， 结果发现死路一条，都走到了自己走过的节点。
那么节点2所连接路径和节点3所链接的路径 都走过了，撤销路径只能向上回退，去选择撤销当初节点4的选择，也就是撤销路径5，改为路径10 。 如图图六：
上图演示中已经把dfs 关键的地方都涉及到了，关键就两点：
- 搜索方向，是认准一个方向搜，直到碰壁之后再换方向
- 换方向是撤销原路径，改为节点链接的下一个路径，回溯的过程。
代码框架（伪代码，注重理解，可以再看看之前回溯部分的笔记）
void dfs(参数) {if (终止条件) {存放结果;return;}for (选择：本节点所连接的其他节点) {处理节点;dfs(图，选择的节点); // 递归回溯，撤销处理结果}
}
三、广度搜索理论bfs
适用场景：解决两个点之间的最短路径问题、岛屿问题，其中岛屿问题广搜和深搜都可以解决。因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。
广搜过程：
假如每次搜索的方向为 上下左右（不包含斜上方），那么给出一个start起始位置，那么BFS就是从四个方向走出第一步。
如果加上一个end终止位置，那么使用BFS的搜索过程如图所示：
我们从图中可以看出，从start起点开始，是一圈一圈，向外搜索，方格编号1为第一步遍历的节点，方格编号2为第二步遍历的节点，第四步的时候我们找到终止点end。正是因为BFS一圈一圈的遍历方式，所以一旦遇到终止点，那么一定是一条最短路径。而且地图还可以有障碍，如图所示：
在第五步，第六步 我只把关键的节点染色了，其他方向周边没有去染色，大家只要关注关键地方染色的逻辑就可以。图中可以看出，如果添加了障碍，我们是第六步才能走到end终点。
广搜代码框架（伪代码，注意理解）
一圈一圈的搜索过程仅仅需要一个容器，能保存我们要遍历过的元素就可以，那么用队列，还是用栈，甚至用数组，都是可以的。用队列的话，就是保证每一圈都是一个方向去转，例如统一顺时针或者逆时针。
广搜不需要注意转圈搜索的顺序，所以用队列（加入元素和弹出元素的顺序不变），还是用栈（加入元素和弹出元素的顺序改变）都是可以的，但都习惯用队列
// 模板针对上面的四方格的地图
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图，也就是一个二维数组
// visited标记访问过的节点，不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {queue<pair<int, int>> que; // 定义队列que.push({x, y}); // 起始节点加入队列visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点while(!que.empty()) { // 开始遍历队列里的元素pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素int curx = cur.first;int cury = cur.second; // 当前节点坐标for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历int nextx = curx + dir[i][0];int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 坐标越界了，直接跳过if (!visited[nextx][nexty]) { // 如果节点没被访问过que.push({nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问}}}}四、实战
98. 所有可达路径（深度搜索）
98. 所有可达路径
1.本题有n 个节点，节点标号是从1开始，对齐处理，需要申请 n + 1 * n + 1数组
2.确认递归函数，参数。dfs函数一定要存一个图，用来遍历的，需要存一个目前我们遍历的节点，定义为x。还需要存一个n，表示终点，我们遍历的时候，用来判断当 x==n 时候 标明找到了终点。
static List<List<Integer>> result = new ArrayList<>(); // 路径集合
static List<Integer> path = new ArrayList<>(); // 单一路径
// x：目前遍历的节点
// graph：存当前的图
// n：终点
void dfs(int[][] graph, int x, int n) 3.确认终止条件。当目前遍历的节点 为 最后一个节点 n 的时候 就找到了一条 从出发点到终止点的路径。此刻就可以进行一条路径的结果处理。
4.处理目前搜索节点出发的路径。接下来是走 当前遍历节点x的下一个节点。首先是要找到 x节点指向了哪些节点，接下来就是将 选中的x所指向的节点，加入到 单一路径来，进入下一层递归，最后就是回溯的过程，撤销本次添加节点的操作。
// 遍历所有可能的下一节点（编号从 1 到 n）
for (int next = 1; next <= n; next++) {// 如果当前节点 x 与 next 有边相连if (graph[x][next] == 1) {path.add(next); // 做选择：加入路径dfs(graph, next, n); // 递归进入下一层path.remove(path.size() - 1); // 回溯：撤销选择}
}邻接矩阵方法代码如下：
import java.util.*;public class Main {// 存储所有从 1 到 n 的合法路径static List<List<Integer>> result = new ArrayList<>();// 当前 DFS 正在探索的路径，回溯用static List<Integer> path = new ArrayList<>();/*** 使用 DFS 深度优先搜索，找出从节点 x 到终点 n 的所有路径** @param graph 邻接矩阵表示的图* @param x 当前访问的节点* @param n 目标节点（终点）*/public static void dfs(int[][] graph, int x, int n) {// 终止条件：到达终点 nif (x == n) {result.add(new ArrayList<>(path)); // 保存当前路径的副本return;}// 遍历所有可能的下一节点（编号从 1 到 n）for (int next = 1; next <= n; next++) {// 如果当前节点 x 与 next 有边相连if (graph[x][next] == 1) {path.add(next); // 做选择：加入路径dfs(graph, next, n); // 递归进入下一层path.remove(path.size() - 1); // 回溯：撤销选择}}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(); // 节点数int m = scanner.nextInt(); // 边数// 创建邻接矩阵（索引 0 不用，使用 1~n）int[][] graph = new int[n + 1][n + 1];// 构建图：读入 m 条边for (int i = 0; i < m; i++) {int u = scanner.nextInt();int v = scanner.nextInt();graph[u][v] = 1; // 表示存在边 u -> v// 若为无向图，还需添加：graph[v][u] = 1;}// 从节点 1 开始，路径初始包含 1path.add(1);// 开始 DFS 搜索所有从 1 到 n 的路径dfs(graph, 1, n);// 输出结果if (result.isEmpty()) {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));}}scanner.close(); }
}