Java之深度优先(DFS)和广度优先(BFS)及相关题目

目录

一.深度优先遍历和广度优先遍历

1.深度优先遍历

2.广度优先遍历

二.图像渲染

1.题目描述

2.问题分析

3代码实现

1.广度优先遍历

2.深度优先遍历

三.岛屿的最大面积

1.题目描述

2.问题分析

3代码实现

1.广度优先遍历

2.深度优先遍历

四.岛屿的周长

1.题目描述

2.问题分析

3代码实现

1.广度优先遍历

2.深度优先遍历

---

一.深度优先遍历和广度优先遍历

1.深度优先遍历

图的深度优先搜索(Depth First Search) .
1) 深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点，可以这样理解:每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。

2)我们可以看到，这样的访问策略是优先往纵向挖掘深入而不是对一个结点的所有邻接结点进行横向访问。

3)显然，深度优先搜索是一个递归的过程(可以用栈来模拟)

例如这个图进行深度优先遍历:V1--->V2--->V5--->V3--->V6-->V4

具体的代码实现

 public class Graph {   public ArrayList<String> vertexList;//存储顶点的集合public int[][] edges;    //存储图对应的邻接矩阵public int numOfEdges;    //表示边的数目public boolean[] isVisted;  //记录某个节点是否被访问//初始化public Graph(int n) {edges = new int[n][n];vertexList = new ArrayList<>(n);isVisted = new boolean[n];}//得到第一个邻接节点的下标w//如果存在就返回对应的下标,否则就返回-1public int getFirstNeighbor(int index) {for (int i = 0; i < getNumOfVertex(); i++) {if (edges[index][i] > 0) {return i;}}return -1;}//根据前一个邻接节点的下标来获取下一个邻接节点public int getNextNeighbor(int v1, int v2) {for (int i = v2 + 1; i < getNumOfVertex(); i++) {if (edges[v1][i] > 0) {return i;}}return -1;}//返回结点i对应的数据public String getValueByIndex(int i) {return vertexList.get(i);}//深度优先遍历算法//对dfs进行重载,遍历所有的结点,并进行dfs//避免不连通的情况出现public void dfs() {isVisted = new boolean[getNumOfVertex()];//遍历所有的结点for (int i = 0; i < getNumOfVertex(); i++) {if (!isVisted[i]) {dfs(i);}}}public void dfs(int i) {//首先访问此结点,输出System.out.print(getValueByIndex(i) + "-->");//将该结点设置成已经访问过isVisted[i] = true;//查找i结点的第一个邻接节点int w = getFirstNeighbor(i);while (w != -1) {//存在if (!isVisted[w]) {dfs(w);}//如果w结点已经被访问过了w = getNextNeighbor(i, w);}}
}

2.广度优先遍历

图的广度优先搜索(Breadth First Search) .

1)广度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，广度优先遍历的策略就是首先访问第一个邻接结点，然后依次访问初始访问结点的相邻接点，然后访问初始节点的第一个邻接结点的邻接顶点,初始节点第二个邻接结点的邻接节点.....，

2)广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点

例如这个图进行广度优先遍历:V1--->V2--->V4--->V5--->V6-->V3

具体的代码实现

     public class Graph {   public ArrayList<String> vertexList;//存储顶点的集合public int[][] edges;    //存储图对应的邻接矩阵public int numOfEdges;    //表示边的数目public boolean[] isVisted;  //记录某个节点是否被访问//初始化public Graph(int n) {edges = new int[n][n];vertexList = new ArrayList<>(n);isVisted = new boolean[n];}//得到第一个邻接节点的下标w//如果存在就返回对应的下标,否则就返回-1public int getFirstNeighbor(int index) {for (int i = 0; i < getNumOfVertex(); i++) {if (edges[index][i] > 0) {return i;}}return -1;}//根据前一个邻接节点的下标来获取下一个邻接节点public int getNextNeighbor(int v1, int v2) {for (int i = v2 + 1; i < getNumOfVertex(); i++) {if (edges[v1][i] > 0) {return i;}}return -1;}//返回结点i对应的数据public String getValueByIndex(int i) {return vertexList.get(i);}//深度优先遍历算法//对dfs进行重载,遍历所有的结点,并进行dfs//避免不连通的情况出现public void dfs() {isVisted = new boolean[getNumOfVertex()];//遍历所有的结点for (int i = 0; i < getNumOfVertex(); i++) {if (!isVisted[i]) {dfs(i);}}}public void bfs(int i) {int u;    //表示队列头结点对应的下标int w;    //邻接节点w//队列,记录结点访问的顺序LinkedList<Integer> queue = new LinkedList<>();System.out.print(getValueByIndex(i) + "-->");//标记为已访问isVisted[i] = true;queue.offer(i);while (!queue.isEmpty()) {//取出队列的头结点下标u = queue.poll();w = getFirstNeighbor(u);while (w != -1) {//找到存在的//是否访问过if (!isVisted[w]) {System.out.print(getValueByIndex(w) + "-->");//标记访问过isVisted[w] = true;queue.add(w);}//以u为前驱节点找w后面的下一个邻接点w = getNextNeighbor(u, w);//体现出广度优先}}}
}

二.图像渲染

1.题目描述

有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。

你也被给予三个整数 sr ,  sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。

为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。

最后返回 经过上色渲染后的图像 。

力扣: 力扣

2.问题分析

这是一道典型的BFS和DFS的问题,

先来考虑广度优先遍历的方法:我们可以先把初始点像素相同的的上下左右点全部涂完色,然后再把第一次涂上色的格子的上下左右点涂上色,以此类推,直到没有可以涂色的格子

假设所有格子都可以涂色,那么广度优先的涂色顺序如下图所示进行涂色处理,这个过程中我们需要使用一个队列进行模拟,每一次寻找上下左右可以涂色的位置(不越界,像素值相同)进行涂色,并且入队列,把像素值替换为color

再来考虑深度优先遍历,深度优先遍历自然就是使用递归来实现,每一次我们访问上方的格子(默认的访问顺序是上下左右),直到不能访问,然后访问不能访问上班的格子的下边的格子,此格子不能访问再访问左边格子,不能访问再访问右边格子,一层一层的递归下去.......

3代码实现

1.广度优先遍历

    int[] dx = {-1, 1, 0, 0};int[] dy = {0, 0, -1, 1};public int[][] floodFill(int[][] image, int sr, int sc, int color) {int m = image.length;int n = image[0].length;int curColor = image[sr][sc];if (image[sr][sc] == color) {return image;}LinkedList<int[]> queue = new LinkedList<>();queue.offer(new int[]{sr, sc});image[sr][sc] = color;while (!queue.isEmpty()) {int[] poll = queue.poll();int x = poll[0], y = poll[1];for (int i = 0; i < 4; ++i) {int mx = x + dx[i], my = y + dy[i];//没有越界,并且像素值和初始像素值相同if (mx >= 0 && mx < m && my >= 0 && my < n && image[mx][my] == curColor) {queue.offer(new int[]{mx, my});image[mx][my] = color;}}}return image;}

2.深度优先遍历

    int[] dx = {-1, 1, 0, 0};int[] dy = {0, 0, -1, 1};public int[][] floodFill(int[][] image, int sr, int sc, int color) {int currColor = image[sr][sc];if (currColor != color) {dfs(image, sr, sc, currColor, color);}return image;}public void dfs(int[][] image, int x, int y, int curColor, int color) {if (image[x][y] == curColor) {image[x][y] = color;}for (int i = 0; i < 4; ++i) {int mx = x + dx[i], my = y + dy[i];if (mx >= 0 && mx < image.length && my >= 0 && my < image[0].length && image[mx][my] == curColor) {dfs(image, mx, my, curColor, color);}}}

三.岛屿的最大面积

1.题目描述

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

力扣:力扣

2.问题分析

这一题上一题相似,上一题是把像素相同的格子全部涂上颜色,这一题是寻找面积最大的岛屿,把能涂的格子全部涂上颜色,这一题是把一个岛屿的面积全部遍历从而求出面积,在给出的海域中有很多的岛屿,我们只需要每次记录面积最大的岛屿的面积,最后直接返回即可

广度优先遍历:遍历整个矩阵grid,找到为陆地(1),然后在这片陆地上进行遍历,把遍历到的陆地格子置为0,也就是海洋,队列中没有陆地格子了,说明这个岛屿全部都遍历完了,和记录的最大面积对比,最终直到全部的矩阵格子遍历完成,返回最大的面积

深度优先遍历:和广度优先的思路一样,唯一不一样的点就是找到岛屿后的遍历顺序,具体看代码

3代码实现

1.广度优先遍历

    public int maxAreaOfIsland(int[][] grid) {int ans = 0;int[] dx = {-1, 1, 0, 0};int[] dy = {0, 0, -1, 1};for (int i = 0; i < grid.length; ++i) {for (int j = 0; j < grid[0].length; ++j) {if (grid[i][j] == 0)continue;LinkedList<int[]> queue = new LinkedList<>();queue.offer(new int[]{i, j});int count = 1;grid[i][j] = 0;while (!queue.isEmpty()) {int[] poll = queue.poll();for (int z = 0; z < 4; ++z) {int mx = poll[0] + dx[z], my = poll[1] + dy[z];if (mx >= 0 && my >= 0 && mx < grid.length && my < grid[0].length && grid[mx][my] != 0) {count++;grid[mx][my] = 0;queue.offer(new int[]{mx, my});}}}ans = Math.max(ans, count);}}return ans;}

2.深度优先遍历

    public int maxAreaOfIsland(int[][] grid) {int ans = 0;for (int i = 0; i < grid.length; ++i) {for (int j = 0; j < grid[0].length; ++j) {ans = Math.max(ans, dfs(grid, i, j));}}return ans;}public int dfs(int[][] grid, int x, int y) {if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0)return 0;grid[x][y] = 0;int[] dx = {-1, 1, 0, 0};int[] dy = {0, 0, -1, 1};int ans = 1;for (int i = 0; i < 4; ++i) {int mx = x + dx[i], my = y + dy[i];ans += dfs(grid, mx, my);}return ans;}

四.岛屿的周长

1.题目描述

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

力扣:力扣

2.问题分析

求面积我们可以求出来,但是求周长确实不容易想出来.但是经过我们仔细观察,我们就可以发现,如果岛屿的一边是水或者是边界地区的话,那么这一条边就可以作为周长的一部分(周长+1)

 广度优先遍历:这一道题使用这个方法,没必要创建队列,我们只需要把这个二维数组遍历完成,判断每一块陆地的周长,这样我们就可以求出总的边长了,如果这一道题是有很多个岛屿,求周长最大的岛屿的周长,我们还是需要用到队列的

深度优先遍历:深度优先遍历和上边的几题一样的思路,具体看代码

3代码实现

1.广度优先遍历

    static int[] dx = {0, 1, 0, -1};static int[] dy = {1, 0, -1, 0};public int islandPerimeter(int[][] grid) {int m = grid.length, n = grid[0].length;int ans = 0;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == 1) {for (int x = 0; x < 4; ++x) {int mx = i + dx[x], my = j + dy[x];if (mx < 0 || my < 0 || mx >= m || my >= n || grid[mx][my] == 0) {ans++;}}}}}return ans;}

2.深度优先遍历

    static int[] dx = {0, 1, 0, -1};static int[] dy = {1, 0, -1, 0};public int islandPerimeter(int[][] grid) {int m = grid.length, n = grid[0].length;int ans = 0;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == 1) {ans += dfs(i, j, grid, m, n);return ans;}}}return ans;}public int dfs(int x, int y, int[][] grid, int m, int n) {if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y] == 0)return 1;if (grid[x][y] == 2)return 0;grid[x][y] = 2;int sum = 0;for (int i = 0; i < 4; ++i) {int mx = x + dx[i], my = y + dy[i];sum += dfs(mx, my, grid, m, n);}return sum;}