这篇博客探讨了深度优先遍历（DFS）和广度优先遍历（BFS）在解决岛屿数量、省份数量、树节点链接和寻找子树等图论问题中的应用。通过实例解析了两种遍历方法的实现细节，如DFS的递归和BFS的队列辅助，并展示了它们如何在不同场景下解决问题。
深度优先遍历
通常采用方法递归实现，主要思路是找到一条路后一头钻到底（符合递归方法中只有触底return后，才会执行后续语句）（堆栈也可实现）
广度优先遍历
通常采用队列辅助实现，主要思路是遇到一个节点后，将其周遭所有符合条件的节点都记录起来，逐个处理。
岛屿数量
岛屿定义：数组由1 0组成，一整片1即为一个岛屿。
①深度优先遍历：
public int numIslands(char[][] grid) {
int res = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
res++;
}
}
}
return res;
}
public void dfs(char[][] grid, int i, int j) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
return;
}
grid[i][j] = '0';
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
使用递归思路，遍历地图上所有格子，每当遇到一个1数值，深度遍历将其连接的1全部标记（将走过的格子值设置为0即可），后续遍历就可以无视走过的格子。
需要注意对边界的判断需要优先于值判断。
②广度优先遍历：
public int numIslands(char[][] grid) {
int res = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
bfs(grid, i, j);
res++;
}
}
}
return res;
}
public void bfs(char[][] grid, int i, int j) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {i, j});
while (!queue.isEmpty()) {
int[] cur = queue.remove();
int row = cur[0];
int col = cur[1];
if (row < grid.length && col < grid[0].length && row >= 0 && col >= 0 && grid[row][col] == '1') {
grid[row][col] = '0';
queue.add(new int[] {row + 1, col});
queue.add(new int[] {row - 1, col});
queue.add(new int[] {row, col + 1});
queue.add(new int[] {row, col - 1});
}
}
}
遍历全部格子，遇到1时开始遍历：（深度使用函数递归，广度使用队列辅助）
队列记录所有有延展可能性的格子，每次弹出一个进行判断，若在值为1，说明还有可能扩展，则标记后将其相邻格子加入队列，以便后续判断。
省份数量
二维数组i,j值对应城市i与城市j是否相连，相连则属于同一个省份。
①深度优先遍历
public int findCircleNum(int[][] isConnected) {
int provinces = 0;
boolean[] visited = new boolean[isConnected.length];
for (int i = 0; i < isConnected.length; i++) {
if (!visited[i]) {
dfs(isConnected, i, visited);
provinces++;
}
}
return provinces;
}
public void dfs(int[][] isconnected, int i, boolean[] visited) {
for (int j = 0; j < isconnected.length; j++) {
if (isconnected[i][j] == 1 && !visited[j]) {
visited[j] = true;
dfs(isconnected, j, visited);
}
}
}
从每个城市单独出发去查找其与其他城市的连接性，在遍历过城市后也需要标记（创建visited数组记录）；主函数中的循环是查找基准城市（可看作i），在方法内再向其余城市发散判断连接（可连接的城市看作j），标记后再以j城市进行发散。
②广度优先遍历
public int findCircleNum(int[][] isConnected) {
int provinces = 0;
boolean[] visited = new boolean[isConnected.length];
for (int i = 0; i < isConnected.length; i++) {
if (!visited[i]) {
bfs(isConnected, i, visited);
provinces++;
}
}
return provinces;
}
public void bfs(int[][] isconnected, int i, boolean[] visited) {
Queue<Integer> queue = new LinkedList<>();
queue.add(i);
while (!queue.isEmpty()) {
Integer city = queue.remove();
visited[city] = true;
for (int j = 0; j < isconnected.length; j++) {
if (isconnected[city][j] == 1 && !visited[j]) {
queue.add(j);
}
}
}
}
依旧用队列辅助遍历，主函数内选基准城市，在方法内开始发散遍历，每次将所有与基准城市相连的城市标记并加入队列，后续不断弹出重复上述操作即可。
上述两题都是每次碰到所需区域就将结果+1，主要处理都是在将相关区域进行标记处理，类似第一题，经过标记处理后，保证每次遇到1即为新的岛屿。
填充每个节点的下一个右侧节点指针 II
题目给出一个树，目的是在每一层横向加一个链表指向。
public Node connect(Node root) {
if (root == null) {
return null;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
Node pre = null;
for (int i = 0; i < size; i++) {
Node remove = queue.remove();
if (pre != null) {
pre.next = remove;
}
pre = remove;
if (remove.left != null) {
queue.add(remove.left);
}
if (remove.right != null) {
queue.add(remove.right);
}
}
}
return root;
}
既然是横向加链表，第一个想到广度优先遍历，在本次的广度优先仍然使用队列先入先出辅助实现，但需要进行切换行的判断，每到新行都需要重新记录行链表的头结点（代码中每次取的size就是每一行包含的节点数，那么每次遍历size个节点就是每次遍历一行；这点清楚后，每一行头结点的清楚在for遍历前进行即可），边向右遍历边记录。
另一棵树的子树
判断树中是否包含目标子树。
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
return bfs(root, subRoot);
}
private boolean bfs(TreeNode sTree, TreeNode tTree) {
if (sTree == null) {
return false;
}
return check(sTree, tTree) || bfs(sTree.left, tTree) || bfs(sTree.right, tTree);
}
private boolean check(TreeNode sTree, TreeNode tTree) {
if (sTree == null && tTree == null) {
return true;
}
if (sTree == null || tTree == null || sTree.val != tTree.val) {
return false;
}
if (sTree.val == tTree.val) {
return check(sTree.left, tTree.left) && check(sTree.right, tTree.right);
}
return false;
}
持续深度遍历，每次遍历都进行判断：
两者都为空：符合子树条件，并且说明探到底后完全相同，可以返回。
某一方为空：不符合条件
两节点值不同：不符合条件
值相同时：进行左右叶子结点的判断。
二进制矩阵中的最短路径
矩阵中从左上角顺着0走到右下角的最短距离。
public int shortestPathBinaryMatrix(int[][] grid) {
int res = 1;
int[][] dir = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, 1}, {1, -1}};
boolean[][] visited = new boolean[grid.length][grid[0].length];
Queue<int[]> queue = new LinkedList<>();
if (grid[0][0] != 0) {
return -1;
}
if (grid.length == 1) {
return 1;
}
queue.add(new int[] {0, 0});
while (!queue.isEmpty()) {
int size = queue.size();
for (int k = 0; k < size; k++) {
int[] pos = queue.remove();
int i = pos[0];
int j = pos[1];
for (int l = 0; l < 8; l++) {
int row = i + dir[l][0];
int col = j + dir[l][1];
if (row >= 0 && col >= 0 && row < grid.length && col < grid.length && grid[row][col] == 0 && !visited[row][col]) {
if (row == grid.length - 1 && col == grid.length - 1) {
return res + 1;
}
queue.add(new int[] {row, col});
visited[row][col] = true;
}
}
}
res++;
}
return -1;
}
采用广度优先遍历，队列辅助实现，每次只遍历队列size个节点，进行判断（越界、判断0值）、记录（每次遍历完size个节点，说明一圈0都遍历过了，所以结果统一加一）、标记（走过的0位置需要标记）。
被围绕的区域
类似围棋，将被X包围的O区域转换为X。
public void solve(char[][] board) {
for (int i = 0; i < board.length; i++) {
bfs(i, 0, board);
bfs(i, board[0].length - 1, board);
}
for (int i = 0; i < board[0].length; i++) {
bfs(0, i, board);
bfs(board.length - 1, i, board);
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
if (board[i][j] == '!') {
board[i][j] = 'O';
}
}
}
}
private void dfs(int i, int j, char[][] board) {
if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != 'O') {
return;
}
board[i][j] = '!';
bfs(i - 1, j, board);
bfs(i + 1, j, board);
bfs(i, j - 1, board);
bfs(i, j + 1, board);
}
private void bfs(int i, int j, char[][] board) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {i, j});
while (!queue.isEmpty()) {
int[] pos = queue.remove();
int row = pos[0];
int col = pos[1];
if (row >= 0 && col >= 0 && row < board.length && col < board[0].length && board[row][col] == 'O') {
queue.add(new int[] {row + 1, col});
queue.add(new int[] {row - 1, col});
queue.add(new int[] {row, col + 1});
queue.add(new int[] {row, col - 1});
board[row][col] = '!';
}
}
}
题目第一思路是找到包围的O，将其遍历改为X；但实际反过来想，将不用转换的O找到，其余都是需要更改的，再进行遍历修改值即可。
那么不用转换的O有什么特点：都处在边界，从边界O蔓延开来的都是不需要转换的。
那么就是找所有边界O后，开始深度/广度优先遍历，将找到的O先用！标记起来，后续遍历矩阵时，先将O变为X，再将！变为O即可实现。
所有可能的路径
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> res = new ArrayList<>();
dfs(graph, res, new ArrayList<>(), 0);
return res;
}
private void dfs(int[][] graph, List<List<Integer>> res, List<Integer> temp, int i) {
if (i == graph.length - 1) {
temp.add(i);
res.add(new ArrayList<>(temp));
temp.remove(temp.size() - 1);
return;
}
temp.add(i);
for (int j = 0; j < graph[i].length; j++) {
dfs(graph, res, temp, graph[i][j]);
}
temp.remove(temp.size() - 1);
}
找到所有路径，第一想法就是深度优先（广度也可以实现，但全部路径同步延伸，记录是个难点）。
思路就是记录当前节点值（从题目了解节点值和长度有关系），遍历是利用连接性二维矩阵前进到连通的位置。
注意遍历结束仍没找到路径后，需要将记录队列中节点回退一个，即temp.remove(temp.size() - 1);
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
