当前位置：首页 > news >正文

代码随想录算法训练营第四十八/九天 | 图 | 深度搜索 | 广度搜索

news 来源：原创 2025/6/20 1:58:10

Day 48 49 总结

自己实现中遇到哪些困难
今日收获，记录一下自己的学习时间
- 11:40 - 14:30
- 12:30 - 13:30, 14:45 - 17:10

图论

深度收缩 & 广度搜索
并查集
最小生成树
拓扑排序
最短路径算法

图论基础

图
- 二维空间里，多个点之间相互连接
图的种类
- 有向图
- 无向图
- 加权
度 Degree
- 连接某个节点的边的数量
- 出度，入度
连通性
- 节点联通情况
- 连通图
  - 任意两个节点存在一条路径
- 强连通图
  - 任务两个节点可以相互到达
- 连通分量
  - 独立的连通子图（无向图中的极大连通子图）
- 强连通分量
  - 有向图中极大强连通子图称之为该图的强连通分量
图的构造
- 邻接表
  - 数组 + 链表
  - 适用于稀疏图，空间利用率高
- 邻接矩阵
  - 二维数组
  - 表达简单，检查连接的速度块，适合稠密图
图的遍历方式
- 深度优先 dfs
- 广度优先 bfs

深度优先搜索

基本理解
- 搜索方向，路径撤销（回溯）
代码框架

void dfs(参数) {if (终止条件) {存放结果;return;}for (选择：本节点所连接的其他节点) {处理节点;dfs(图，选择的节点); // 递归回溯，撤销处理结果}
}

98. 所有可达路径

题目连接：98. 所有可达路径

题目描述：

给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个函数，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。

输入：

N个节点，M个边

s节点与 t节点是相连的

输出：

~~所有从1出发的路径~~ 找出并返回所有从节点 1 到节点 n 的路径

实现思路：

用 N*N 的邻接表保存节点的连接信息，通过dfs收集所有路径。

~~使用visted变量记录当前访问过哪些节点，用于撤销操作~~ 有向无环，不需要visted记录

使用for循环遍历邻接表中当前节点的行，搜索所有相邻节点

path变量保存临时搜索路径，result变量收集所有路径

代码实现：

public class Main {public static List<Integer> path = new ArrayList<>();public static List<List<Integer>> result = new ArrayList<>();public static int[][] graph;public static void main (String[] args) {/* code */Scanner in = new Scanner(System.in);String[] firstLine = in.nextLine().split(" ");int N = Integer.valueOf(firstLine[0]);int M = Integer.valueOf(firstLine[1]);graph = new int[N+1][N+1];visited = new boolean[N+1];for (int i=0; i<M; i++) {String[] line = in.nextLine().split(" ");int row = Integer.valueOf(line[0]);int col = Integer.valueOf(line[1]);graph[row][col] = 1;}        path.add(1);dfs1(1, N);if (result.size() == 0) System.out.println(-1);else {for (List<Integer> p : result) {for (int i=0; i<p.size()-1; i++)System.out.print(p.get(i) + " ");System.out.println(p.get(p.size()-1));}            }}public static void dfs1 (int node, int N) {// 到达路径末尾，收集路径if (node == N) { // 找到从1到N的路径result.add(new ArrayList<>(path));return;}for (int i=1; i<=N; i++) {if (graph[node][i] == 0) continue;path.add(i);dfs1(i, N);path.remove(path.size()-1);}            }}

99. 岛屿数量

题目连接：99. 岛屿数量

题目描述：

给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入：

N行，M列的矩阵

矩阵的具体数字，1代表一个岛，0代表水。

输出：

输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

实现思路：

使用一个visted矩阵，标记都有哪些岛屿是访问过的。

按序访问每一个未访问过的岛屿，以该岛屿为起始点，进行深度搜索, 本次dfs结束之后，孤岛数量+1

深度搜索：

确定四个方向，上，右，下，左

分别dfs这四个分支

代码实现：

public class Main {public static void main (String[] args) {/* code */Scanner in = new Scanner(System.in);String[] firstLine = in.nextLine().split(" ");int N = Integer.valueOf(firstLine[0]);int M = Integer.valueOf(firstLine[1]);int[][] graph = new int[N][M];boolean[][] visited = new boolean[N][M];for (int i=0; i<N; i++) {for (int j=0; j<M; j++) {graph[i][j] = in.nextInt();   }}        // for (int i=0; i<N; i++) {//     System.out.println(Arrays.toString(graph[i]));// }int ct = 0;for (int i=0; i<N; i++) {for (int j=0; j<M; j++) {if (graph[i][j] == 1 && !visited[i][j]) {// System.out.println("start:" + i + " " + j);dfs(graph, visited,i,j, N, M);ct++;}}}System.out.println(ct);}public static void dfs(int[][] graph, boolean[][] visited, int x, int y, int N, int M) {int[] directions = {-1,0, 0,1, 1,0, 0,-1}; // 上右下左visited[x][y] = true;for (int i=0; i<4; i++) {int directX = directions[i*2];int directY = directions[i*2+1];if (directX+x >= 0 && directX+x < N && directY+y >= 0 && directY+y < M &&graph[directX+x][directY+y]==1 && !visited[directX+x][directY+y]) {// System.out.println("dfs:" + (directX+x) + " " + (directY+y));dfs(graph, visited, directX+x, directY+y, N, M);}}}}

广度优先搜索

BFS，求点与点之间最短路径，以起始点为圆心，按圈搜索

搜索过程

起始点，起始点的四个方向
队列保存顺（逆）时针的邻居

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; // 只要加入队列立刻标记，避免重复访问}}}}

99. 岛屿数量

题目连接：99. 岛屿数量

题目描述：

输入：

N行，M列的矩阵

矩阵的具体数字，1代表一个岛，0代表水。

输出：

输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

实现思路：

使用一个visted矩阵，标记都有哪些岛屿是访问过的。

按序访问每一个未访问过的岛屿，以该岛屿为起始点，进行广度搜索, 本次bfs结束之后，孤岛数量+1

广度搜索：

确定四个方向，上，右，下，左

使用一个队列将这个四个岛屿存储起来，然后bfs

代码实现：

public class Main {public static void main (String[] args) {/* code */Scanner in = new Scanner(System.in);String[] firstLine = in.nextLine().split(" ");int N = Integer.valueOf(firstLine[0]);int M = Integer.valueOf(firstLine[1]);int[][] graph = new int[N][M];boolean[][] visited = new boolean[N][M];for (int i=0; i<N; i++) {for (int j=0; j<M; j++) {graph[i][j] = in.nextInt();   }}        int ct = 0;for (int i=0; i<N; i++) {for (int j=0; j<M; j++) {if (graph[i][j] == 1 && !visited[i][j]) {// System.out.println("start:" + i + " " + j);bfs(graph, visited,i,j, N, M);ct++;}}}System.out.println(ct);}public static void bfs(int[][] graph, boolean[][] visited, int X, int Y, int N, int M) {int[] directions = {-1,0, 0,1, 1,0, 0,-1}; // 上右下左Deque<int[]> queue = new LinkedList<>();queue.add(new int[]{X, Y});visited[X][Y] = true;while (!queue.isEmpty()) {int[] land = queue.poll();int x = land[0];int y = land[1];for (int i=0; i<4; i++) {int directX = directions[i*2];int directY = directions[i*2+1];if (directX+x >= 0 && directX+x < N && directY+y >= 0 && directY+y < M &&graph[directX+x][directY+y]==1 && !visited[directX+x][directY+y]) {queue.add(new int[]{directX+x,directY+y});visited[directX+x][directY+y] = true;}}}}}

100. 岛屿的最大面积

题目连接：100. 岛屿的最大面积

题目描述：

输入：

N行，M列的矩阵

矩阵的具体数字，1代表一个岛，0代表水。

输出：

输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。

实现思路：

使用一个visted矩阵，标记都有哪些岛屿是访问过的。

按序访问每一个未访问过的岛屿，以该岛屿为起始点，进行广度搜索, 本次bfs结束之后，得到当前岛屿的面积，保存最大面积。

广度搜索：

确定四个方向，上，右，下，左

使用一个队列将这个四个岛屿存储起来，然后bfs

代码实现：

// bfs
public class Main {public static void main (String[] args) {/* code */Scanner in = new Scanner(System.in);String[] line0 = in.nextLine().split(" ");int N = Integer.valueOf(line0[0]);int M = Integer.valueOf(line0[1]);int[][] graph = new int[N][M];boolean[][] visited = new boolean[N][M];for (int i=0; i<N; i++) {for (int j=0; j<M; j++)graph[i][j] = in.nextInt();}int max = 0;for (int i=0; i<N; i++) {for (int j=0; j<M; j++)if (graph[i][j] == 1 && !visited[i][j])max = Math.max(bfs(graph, visited, i, j, N, M), max);}System.out.println(max);}public static int bfs(int[][] graph, boolean[][] visited, int X, int Y, int N, int M) {int[] directions = {-1,0,  0,1,  1,0, 0 ,-1};int area = 0;Deque<int[]> queue = new LinkedList<>();queue.add(new int[]{X,Y});visited[X][Y] = true;while (!queue.isEmpty()) {int[] loc = queue.poll();area++;for (int i=0; i<4; i++) {int x = loc[0] + directions[i*2];int y = loc[1] + directions[i*2+1];if (x >= 0 && x < N && y >= 0 && y < M &&graph[x][y] == 1 && !visited[x][y]) {queue.add(new int[] {x, y});visited[x][y] = true;                        }}}return area;}}// dfs
public class Main {public static void main (String[] args) {int max = 0;for (int i=0; i<N; i++) {for (int j=0; j<M; j++)if (graph[i][j] == 1 && !visited[i][j])max = Math.max(dfs(graph, visited, i, j, N, M), max);}System.out.println(max);}public static int dfs(int[][] graph, boolean[][] visited, int X, int Y, int N, int M) {int[] directions = {-1,0,  0,1,  1,0, 0 ,-1};int area = 1;visited[X][Y] = true;for (int i=0; i<4; i++) {int x = X + directions[i*2];int y = Y + directions[i*2+1];if (x >= 0 && x < N && y >= 0 && y < M &&graph[x][y] == 1 && !visited[x][y]) {area += dfs(graph, visited, x, y, N, M);}}return area;}

101. 孤岛的总面积

题目连接：100. 岛屿的最大面积

题目描述：

输入：

N行，M列的矩阵

矩阵的具体数字，1代表一个岛，0代表水。

输出：

现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。

实现思路：

使用一个visted矩阵，标记都有哪些岛屿是访问过的。

按序访问每一个未访问过的岛屿，以该岛屿为起始点，进行广度搜索, 本次bfs结束之后，将访问这个孤岛上的所有地块，得到岛屿面积。判断该岛屿是否存在一个地块接触边缘，如果是孤岛就合并面积，不是的话放弃计算面积。

广度搜索：

确定四个方向，上，右，下，左

使用一个队列将这个四个岛屿存储起来，然后bfs，遇到边界的格子就标记一下这个岛

代码实现：

102. 沉没孤岛

题目连接：102. 沉没孤岛

题目描述：

输入：

N行，M列的矩阵

矩阵的具体数字，1代表一个岛，0代表水。

输出：

输出将孤岛“沉没”之后的岛屿矩阵。注意：每个元素后面都有一个空格

实现思路：

使用一个visted矩阵，标记都有哪些岛屿是访问过的。

按序访问每一个未访问过的岛屿，以该岛屿为起始点，进行广度搜索, 本次bfs结束之后，将访问这个孤岛上的所有地块，得到岛屿面积。判断该岛屿是否存在一个地块接触边缘，如果是孤岛就将该孤岛变成水域.

搜索过程可以简化, 只从四个边开始搜索, 将搜索到的岛屿标记成2, 然后重新打印新的地图.

广度搜索：

确定四个方向，上，右，下，左

使用一个队列将这个四个岛屿存储起来，然后bfs，遇到边界的格子就标记一下这个岛

代码实现：

public class Main {static boolean isIsolated;public static void main (String[] args) {/* code */Scanner in = new Scanner(System.in);String[] line0 = in.nextLine().split(" ");int N = Integer.valueOf(line0[0]);int M = Integer.valueOf(line0[1]);int[][] graph = new int[N][M];boolean[][] visited = new boolean[N][M];for (int i=0; i<N; i++) {for (int j=0; j<M; j++)graph[i][j] = in.nextInt();}for (int i=0; i<N; i++) {if (graph[i][0] == 1 && !visited[i][0])bfs(graph, visited, i, 0, N, M);if (graph[i][M-1] == 1 && !visited[i][M-1])bfs(graph, visited, i, M-1, N, M);}for (int j=0; j<M; j++) {if (graph[0][j] == 1 && !visited[0][j])bfs(graph, visited, 0, j, N, M);if (graph[N-1][j] == 1 && !visited[N-1][j])bfs(graph, visited, N-1, j, N, M);            }for (int i=0; i<N; i++) {for (int j=0; j<M; j++) {if (graph[i][j] == 2)System.out.print(1+" ");elseSystem.out.print(0+" ");}System.out.println();}}public static int bfs(int[][] graph, boolean[][] visited, int X, int Y, int N, int M) {int[] directions = {-1,0,  0,1,  1,0, 0 ,-1};Deque<int[]> queue = new LinkedList<>();queue.add(new int[]{X,Y});visited[X][Y] = true;while (!queue.isEmpty()) {int[] loc = queue.poll();graph[loc[0]][loc[1]] = 2;for (int i=0; i<4; i++) {int x = loc[0] + directions[i*2];int y = loc[1] + directions[i*2+1];if (x >= 0 && x < N && y >= 0 && y < M &&graph[x][y] == 1 && !visited[x][y]) {queue.add(new int[] {x, y});visited[x][y] = true;                        }}}return 0;}
}

103. 水流问题

题目连接：103. 水流问题

题目描述：

现有一个 N × M 的矩阵，每个单元格包含一个数值，这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界，而矩阵的右边界和下边界被视为第二组边界。

矩阵模拟了一个地形，当雨水落在上面时，水会根据地形的倾斜向低处流动，但只能从较高或等高的地点流向较低或等高并且相邻（上下左右方向）的地点。我们的目标是确定那些单元格，从这些单元格出发的水可以达到第一组边界和第二组边界。

输入：

N行，M列的矩阵

矩阵的具体数字，代表当前格子的高度

输出：

输出所有满足条件的格子: 从该格子出发的水,可以流向上左并且可以流向上右.

实现思路：

遍历所有格子, 进行bfs, 在bfs的过程当中, 修改两个全局变量, 表示搜索路径是否到达过一二边界.

bfs完成之后, 检查结果, 如果两个边界都到达过, 就放入结果集合中.

输出结果集合当中的坐标.

代码实现：

public class Main {static boolean arrivedA;static boolean arrivedB;public static void main (String[] args) {/* code */Scanner in = new Scanner(System.in);String[] line0 = in.nextLine().split(" ");int N = Integer.valueOf(line0[0]);int M = Integer.valueOf(line0[1]);int[][] graph = new int[N][M];for (int i=0; i<N; i++) {for (int j=0; j<M; j++)graph[i][j] = in.nextInt();}List<int[]> result = new ArrayList<>();for (int i=0; i<N; i++) {for (int j=0; j<M; j++) {arrivedA = false;arrivedB = false;;bfs(graph, i, j, N, M);if (arrivedA && arrivedB)result.add(new int[]{i,j});}}// 打印结果集合for (int[] res : result) {System.out.println(res[0] + " " + res[1]);}}public static void bfs(int[][] graph, int X, int Y, int N, int M) {boolean[][] visited = new boolean[N][M];int[] directions = {-1,0,  0,1,  1,0, 0 ,-1};Deque<int[]> queue = new LinkedList<>();queue.add(new int[]{X,Y});visited[X][Y] = true;while (!queue.isEmpty()) {int[] loc = queue.poll();// 检查是否达到边界if (loc[0] == 0 || loc[1] == 0) arrivedA = true;if (loc[0] == N-1 || loc[1] == M-1) arrivedB = true;for (int i=0; i<4; i++) {int x = loc[0] + directions[i*2];int y = loc[1] + directions[i*2+1];if (x >= 0 && x < N && y >= 0 && y < M &&graph[x][y] <= graph[loc[0]][loc[1]] && !visited[x][y]) {queue.add(new int[] {x, y});visited[x][y] = true;                        }}}return ;}
}

104.建造最大岛屿

题目连接: 104. 建造最大岛屿

题目描述：

现有一个 N × M 的矩阵，每个单元格值为 1 或 0, 分别代表陆地和水.

可以选择一块水, 变成陆地, 然后和其他陆地连接成更大的岛屿.

输入：

N行，M列的矩阵 + 矩阵的具体数字，代表当前格子的高度

输出：

填平一格水域可以得到的最大岛屿面积.

实现思路：

遍历所有水域, 使用bfs来遍历所有与该水域相邻的岛屿, 求出岛屿面积, 记录最大岛屿面积.

考虑到特殊情况, 不存在水域的时候, 还需要遍历陆地来得到最大现存岛屿.

代码实现：

就是单纯bfs然后记录最大值

优化版本就是, 使用岛屿面积做标记, 再遍历水, 计算可以得到的最大面积.

110. 字符串接龙

题目连接: 110. 字符串接龙

题目描述：

初始字符串 xxx, 结果字符串 yyy, 中间字符串 xyz.

所有中间字符串只能使用一次, 如果两个字符串只差一个字符的话, 可以完成转换.

请问最少需要几步, 可以将初字符串经过中间字符串集合的转换,变成结果字符串.

实现思路：

求最短路径, 使用 bfs. 节点为字符串, 如果两个字符串只差一位字符, 那么这两个字符串存在一条路径.

使用HashMap 存储邻接表. Key 为字符串, value为一个数组保存了所有与该字符串存在路径关系的字符串,

HashMap构成的visited变量记录哪些节点被访问过(要求节点只能访问一次)

代码实现：

import java.util.Scanner;
public class Main {public static void main (String[] args) {/* code */Scanner in = new Scanner(System.in);int N = Integer.valueOf(in.nextLine());String[] line0 = in.nextLine().split(" ");String startStr = line0[0];String endStr = line0[1];HashMap<String, List<String>> graph = new HashMap<>();HashMap<String, Boolean> visited = new HashMap<>();for (int i=0; i<N; i++) {String s = in.nextLine();List<String> neighbours = new LinkedList<>();for (String key : graph.keySet()) {if (hasConnection(s, key)) {neighbours.add(key);graph.get(key).add(s);}}graph.put(s, neighbours);visited.put(s, false);}// 接入初始字符List<String> neighbours = new LinkedList<>();for (String key : graph.keySet()) {if (hasConnection(startStr, key)) {neighbours.add(key);}}graph.put(startStr, neighbours);visited.put(startStr, false);// 接入结束字符for (String key : graph.keySet()) {if (hasConnection(endStr, key)) {graph.get(key).add(endStr);}}visited.put(endStr, false);System.out.println(graph);System.out.println(bfs(graph, visited, startStr, endStr));}public static int bfs(HashMap<String, List<String>> graph, HashMap<String, Boolean> visited, String startStr, String endStr) {Deque<String> queue = new LinkedList<>();queue.add(startStr);int steps = 0;while (!queue.isEmpty()) {int idx = queue.size();for (int i=0; i<idx; i++) {String s = queue.poll();if (s.equals(endStr)) return steps+1;for (String next : graph.get(s)) {if (visited.get(next) == true) continue;visited.put(next, true);queue.add(next);}}steps++;}return 0;}public static boolean hasConnection(String s1, String s2) {int diff = 0;for (int i=0; i<s1.length(); i++) {if (s1.charAt(i) != s2.charAt(i))diff++;}return diff == 1;}
}

105.有向图的完全可达性

题目连接: 105. 有向图的完全可达性

题目描述：

给定一个有向图，包含 N 个节点，节点编号分别为 1，2，...，N。现从 1 号节点开始，如果可以从 1 号节点的边可以到达任何节点，则输出 1，否则输出 -1。

实现思路：

邻接矩阵表示节点之间的连接性, 使用 BFS 遍历所有节点. Visted数组记录哪些节点被访问过. 如果从1号节点开始的 BFS 结束之后, 所有节点都被visit过了, 说明可以从1号节点到达所有节点,

正常BFS就行

代码实现：

为了避免超时,使用中途退出判断,不能使用stream计算

return Arrays.stream(visited).sum() == N ? 1 : -1;

public class Main {public static void main (String[] args) {/* code */Scanner in = new Scanner(System.in);String[] line0 = in.nextLine().split(" ");int N = Integer.valueOf(line0[0]);int M = Integer.valueOf(line0[1]);// 使用邻接表,而非邻接矩阵List<List<Integer>> graph = new ArrayList<>(N);for (int i=0; i<N; i++) {List<Integer> list = new LinkedList<>();graph.add(list);}for (int $=0; $<M; $++) {int i = in.nextInt()-1;int j = in.nextInt()-1;graph.get(i).add(j);}System.out.println(bfs(graph, N));}public static int bfs(List<List<Integer>> graph, int N) {Deque<Integer> queue = new LinkedList<>();int[] visited = new int[N];queue.add(0);visited[0] = 1;while (!queue.isEmpty()) {int node = queue.poll();List<Integer> arr = graph.get(node);for (int next : arr) {if (visited[next] == 0) {queue.add(next);visited[next] = 1;}}}return Arrays.stream(visited).sum() == N ? 1 : -1;}
}

Day 48 49 总结

图论

深度收缩 & 广度搜索

并查集

最小生成树

拓扑排序

最短路径算法

图论基础

深度优先搜索

98. 所有可达路径

题目描述：

实现思路：

代码实现：

99. 岛屿数量

题目描述：

实现思路：

代码实现：

广度优先搜索

99. 岛屿数量

题目描述：

实现思路：

代码实现：

100. 岛屿的最大面积

题目描述：

实现思路：

代码实现：

101. 孤岛的总面积

题目描述：

实现思路：

代码实现：

102. 沉没孤岛

题目描述：

实现思路：

代码实现：

103. 水流问题

题目描述：

实现思路：

代码实现：

104.建造最大岛屿

题目描述：

实现思路：

代码实现：

110. 字符串接龙

题目描述：

实现思路：

代码实现：

105.有向图的完全可达性

题目描述：

实现思路：

代码实现：

相关文章：