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

数据结构与算法——深度优先搜索（DFS）和广度优先搜索（BFS）

article 2024/11/16 14:36:58

引言

深度优先搜索（DFS）

广度优先搜索（BFS）

区别与联系

岛屿数量（LeetCode 200）

经典例题

引言

深度优先搜索（DFS）

定义与原理：

深度优先搜索是一种用于遍历或搜索树或图的算法。它从根节点（或起始节点）开始，沿着树的深度遍历树的节点，尽可能深地搜索树的分支。
当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这个过程一直进行到已发现从源节点可达的所有节点为止。
深度优先搜索通常使用递归或栈来实现。

关键点：

递归与回溯：DFS通过递归函数或栈来实现，当一条路走不通时，会回溯到上一个节点，尝试其他路径。
深度优先：每次尽可能深地遍历图或树，直到无法再深入。

应用场景：

迷宫问题：在迷宫中寻找从起点到终点的路径。
图的连通性问题：判断图中的所有节点是否都连通。
拓扑排序：在有向无环图（DAG）中进行拓扑排序。

广度优先搜索（BFS）

定义与原理：

广度优先搜索是一种用于遍历或搜索树或图的算法。它从根节点（或起始节点）开始，先访问离根节点最近的节点，然后逐层向下访问。
它通过队列来实现，队列中保存的是待访问的节点。

关键点：

队列：BFS使用队列来保存待访问的节点，按照先进先出的原则进行访问。
广度优先：每次尽可能广地遍历图或树的一层节点。

应用场景：

最短路径问题：在无权图或有权图中寻找从一个顶点到另一个顶点的最短路径。
社交网络中的人际关系分析：分析社交网络中的好友关系，找出两个用户之间的最短路径。
层次遍历：在树形结构中进行层次遍历。

区别与联系

区别：

搜索策略：DFS是深度优先，一条路走到底；BFS是广度优先，逐层遍历。
数据结构：DFS通常使用递归或栈；BFS使用队列。
完备性：BFS是一种完备搜索，只要问题有解就一定能找到；DFS则可能陷入无限循环，不是完备搜索。
适用性：DFS适合深度较大、目标节点层次较浅的情况；BFS适合目标节点层次较深或需要找到最短路径的情况。

联系：

两者都是图论和树形结构中的基本搜索算法。
在某些情况下，可以相互转换或结合使用以达到更好的搜索效果。例如，在解决某些复杂问题时，可以先使用BFS找到可能的解空间，再使用DFS进行深入搜索。

岛屿数量（LeetCode 200）

题目描述：
给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设整个网格的四周都被水包围着。

示例

深度优先搜索（DFS）解题思路：

遍历网格：首先，我们需要遍历整个网格，对于每个遇到的 '1'（陆地），我们将其视为一个岛屿的起点。
深度优先搜索：当我们找到一个岛屿的起点时，我们启动DFS来遍历这个岛屿的所有陆地，并将它们标记为已访问（例如，将它们更改为 '0' 或其他非陆地标记）。这样可以确保我们不会重复计算同一个岛屿。
计数：每当我们通过DFS遍历完一个岛屿的所有陆地后，我们就将岛屿的计数增加1。
继续遍历：我们继续遍历网格，直到我们检查完所有的格子。

#include <vector>  
using namespace std;  
  
class Solution {  
public:  
    int numIslands(vector<vector<char>>& grid) {  
        if (grid.empty() || grid[0].empty()) return 0;  
        int rows = grid.size();  
        int cols = grid[0].size();  
        int count = 0;  
  
        for (int i = 0; i < rows; ++i) {  
            for (int j = 0; j < cols; ++j) {  
                if (grid[i][j] == '1') {  
                    dfs(grid, i, j);  
                    ++count;  
                }  
            }  
        }  
  
        return count;  
    }  
  
private:  
    void dfs(vector<vector<char>>& grid, int i, int j) {  
        int rows = grid.size();  
        int cols = grid[0].size();  
  
        // 检查边界条件和当前格子是否为陆地  
        if (i < 0 || j < 0 || i >= rows || j >= cols || grid[i][j] != '1') {  
            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); // 右  
    }  
};

广度优先搜索（BFS）解题思路：
使用BFS来遍历整个网格。当我们遇到一个'1'时，表示发现了一个岛屿，我们从这个'1'开始进行BFS遍历，将所有与之相连的'1'都标记为已访问（比如，可以标记为'0'或另一个不同的字符）。在BFS的过程中，我们不断地将相邻的'1'加入队列中，并继续遍历，直到队列为空。每完成一次BFS遍历，岛屿数量就加一。最后返回岛屿的总数.

#include <vector>  
#include <queue>  
using namespace std;  
  
class Solution {  
public:  
    int numIslands(vector<vector<char>>& grid) {  
        if (grid.empty() || grid[0].empty()) return 0;  
        int rows = grid.size();  
        int cols = grid[0].size();  
        int count = 0;  
          
        for (int i = 0; i < rows; ++i) {  
            for (int j = 0; j < cols; ++j) {  
                if (grid[i][j] == '1') {  
                    ++count;  
                    bfs(grid, i, j);  
                }  
            }  
        }  
          
        return count;  
    }  
      
private:  
    void bfs(vector<vector<char>>& grid, int row, int col) {  
        int rows = grid.size();  
        int cols = grid[0].size();  
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向  
        queue<pair<int, int>> q;  
          
        // 将起始点加入队列，并标记为已访问  
        q.push({row, col});  
        grid[row][col] = '0';  
          
        while (!q.empty()) {  
            auto curr = q.front();  
            q.pop();  
            int x = curr.first;  
            int y = curr.second;  
              
            // 遍历四个方向  
            for (auto& dir : directions) {  
                int nx = x + dir.first;  
                int ny = y + dir.second;  
                  
                // 检查新坐标是否越界且为陆地  
                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == '1') {  
                    // 加入队列并标记为已访问  
                    q.push({nx, ny});  
                    grid[nx][ny] = '0';  
                }  
            }  
        }  
    }  
};