力扣刷题记录--图相关题目

2023-12-26 22:01:07

图的遍历方式主要是深度优先搜索(DFS)和广度优先搜索(BFS),两者大概的区别:

  • dfs是可一个方向去搜,不到黄河不回头,直到遇到绝境了,搜不下去了,再换方向(换方向的过程就涉及到了回溯)。
  • bfs是先把本节点所连接的所有节点遍历一遍,走到下一个节点的时候,再把连接节点的所有节点遍历一遍,搜索方向更像是广度,四面八方的搜索过程。

DFS:
dfs是离不开回溯的,因为它怼着一个方向深搜,当一个方向的搜索满足不了的时候,就需要回溯,回到前面的点换一个方向搜索。递归和回溯是相辅相成的,回溯法的代码框架:

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}

dfs的代码框架:

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本节点所连接的其他节点) {
        处理节点;
        dfs(图,选择的节点); // 递归
        回溯,撤销处理结果
    }
}

可以看出二者差别不大。

对于dfs同样是走着递归3步(来自代码随想录):

  1. 确认递归函数,参数:

通常我们递归的时候,我们递归搜索需要了解哪些参数,其实也可以在写递归函数的时候,发现需要什么参数,再去补充就可以。

一般情况,深搜需要 二维数组数组结构保存所有路径,需要一维数组保存单一路径,这种保存结果的数组,我们可以定义一个全局变量,避免让我们的函数参数过多:

List<List<Integer>> result; // 保存符合条件的所有路径
List<Integer> path; // 起点到终点的路径
void dfs (图,目前搜索的节点)  
  1. 确认终止条件

终止添加不仅是结束本层递归,同时也是我们收获结果的时候。

另外,其实很多dfs写法,没有写终止条件,其实终止条件写在了, 下面dfs递归的逻辑里了,也就是不符合条件,直接不会向下递归。

if (终止条件) {
    存放结果;
    return;
}
  1. 处理目前搜索节点出发的路径

一般这里就是一个for循环的操作,去遍历 目前搜索节点 所能到的所有节点。

for (选择:本节点所连接的其他节点) {
    处理节点;
    dfs(图,选择的节点); // 递归
    回溯,撤销处理结果
}

BFS:

广搜适合于解决两个点之间的最短路径问题。

因为广搜是从起点出发,以起始点为中心一圈一圈进行搜索,一旦遇到终点,记录之前走过的节点就是一条最短路。

借用代码随想录的例子:
给出一个start起始位置,BFS就是从四个方向走出第一步。如果加上一个end终止位置,那么使用BFS的搜索过程如图所示:
在这里插入图片描述
从图中可以看出,从start起点开始,是一圈一圈,向外搜索,方格编号1为第一步遍历的节点,方格编号2为第二步遍历的节点,第四步的时候我们找到终止点end。因为BFS一圈一圈的遍历方式,所以一旦遇到终止点,那么一定是一条最短路径。

而且地图还可以有障碍,如图所示:
在这里插入图片描述
从图中可以看出,如果添加了障碍,我们是第六步才能走到end终点,所以只要BFS只要搜到终点一定是一条最短路径。

至于用什么样的数据结构,其实只要可以保存我们要遍历过的元素就可以,用队列,还是用栈,甚至用数组,都是可以的。用队列的话,就是保证每一圈都是一个方向去转,例如统一顺时针或者逆时针。

因为队列是先进先出,加入元素和弹出元素的顺序是没有改变的。

如果用栈的话,就是第一圈顺时针遍历,第二圈逆时针遍历,第三圈有顺时针遍历。

因为栈是先进后出,加入元素和弹出元素的顺序改变了。

而广搜不需要注意转圈搜索的顺序,只要能搜到就行了,但大家都习惯用队列了,所以大部分还是使用队列来存储遍历过的元素。

以下是代码随想录的c++版模板,针对四方格地图:

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

}

LeetCode 797. 所有可能的路径

添加链接描述

2023.12.26 一刷

思路:

题目要求找出从0到n-1的所有路径,其实graph.length=n,n-1就是graph的下标;
graph[i]就是节点i可以到达的所有节点的列表;

可以采用图的深度优先搜索:
1.确认递归函数,参数
为了深度优先遍历,就需要把图作为参数;此外还需要知道当前遍历到了哪个节点,所以需要把节点也作为参数进行传递;

public void dfs(int[][] graph,int node)

2.确认终止条件
题目要求收集从0到n-1的路径,因此只要传进来参数节点是n-1(即graph.length-1)就视为路径完整,就将记录的路径收集进入res;

if(node == graph.length-1){
    res.add(new ArrayList<>(path));
    return;
}

3.处理目前搜索节点出发的路径
遍历到当前节点node后,需要知道节点node与谁相连,即graph[node][i],用i从0到graph[node].length-1遍历所有node可以到达的节点,依次加入path并进行邻接节点的dfs,然后进行回溯,将路径中的当前节点去除;:

for(int i=0;i<graph[node].length;i++){
    // 记录邻接的节点
    int nextNode = graph[node][i];
    path.add(nextNode);
    dfs(graph,nextNode);
    path.remove(path.size()-1);
}

LeetCode 200. 岛屿数量

原题链接

一、深搜:

核心思想:
为了避免在递归过程重复计算之前已经遍历过的“陆地”,在dfs过程中需要将搜索过的“1”,置为“0”;
需要遍历grid的所有网格,一旦碰到为“1”的陆地,计数器就+1,然后进行dfs,将所有与之相连的“1”全部置为“0”。由于在深搜中会将邻接的“1”都置为“0”,因此不用担心重复计算岛屿的数量。

深搜代码如下:

//  解法1:深搜
class Solution {
    public int numIslands(char[][] grid) {
        int count=0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j] == '1'){
                    count++;
                    dfs(grid,i,j);
                }
            }
        }
        return count;
    }
    public void dfs(char[][] grid,int i,int j){
        // 当超出网格界限或遍历到“0”,就可以返回了
        if(i<0||i>=grid.length||j<0||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);

    }
}

二、广搜:
由于广搜需要搭配used数组标记已经访问过的陆地,因此遍历过程中不必像深搜一样将“1”的陆地置为“0”,只需对应网格标记为访问过即可;

遍历所有网格过程时,只有当前网格未访问过,且网格为“1”(陆地),才将岛屿数量+1,并进行bfs;

在bfs中,需要先将入队的网格标记为访问过,然后沿4个方向进行bfs,只有当要访问的网格未被访问,且为“1”,就将其入队(防止重复访问网格),并且立即将入队网格标记为访问过;

广搜代码如下:

//  解法2:广搜
class Solution {
    boolean[][] used;// 标记访问过的网格
    // 作为原始坐标方向偏移,与原坐标相加,依次是上下左右
    int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
    public int numIslands(char[][] grid) {
        int count=0;
        used = new boolean[grid.length][grid[0].length];
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                // 只有当未访问过且为1的陆地才可以+1
                if(!used[i][j] && grid[i][j] == '1'){
                    count++;
                    bfs(grid,i,j);
                }
            }
        }
        return count;
    }
    public void bfs(char[][] grid,int i,int j){
        Queue<int[]> que = new ArrayDeque<>();// 队列,用于暂存访问节点
        que.offer(new int[]{i,j});// 将当前网格入队
        used[i][j] = true;//只要一入队就必须标记为访问过

        while(!que.isEmpty()){
            // 队头先出队,找出与之邻接的符合要求的网格入队
            int[] cur = que.poll();
            int curI = cur[0];
            int curJ = cur[1];
            // 依次遍历上下左右四个方向的网格
            for(int d=0;d<4;d++){
                int nextI = curI+dir[d][0];
                int nextJ = curJ+dir[d][1];
                // 当超出网格界限,就可以继续下一个方向了
                if(nextI<0||nextI>=grid.length||nextJ<0||nextJ>=grid[0].length)continue;
                // 只有当下一个网格未访问过,且为‘1’,才加入队列
                if(!used[nextI][nextJ] && grid[nextI][nextJ]=='1'){
                    que.offer(new int[]{nextI,nextJ});
                    used[nextI][nextJ]=true;// 记得一加入队列就标记访问过
                }
            } 
        }
        
    }
}

文章来源:https://blog.csdn.net/qq_41857397/article/details/135045528
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。