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

算法入门：BFS与DFS详解（C++实现）

news 2025/7/16 13:06:29

深度优先与广度优先是算法世界的两大基石，掌握它们如同获得探索算法宇宙的钥匙

一、初识BFS与DFS

什么是BFS和DFS？

BFS（广度优先搜索）：逐层遍历数据结构，先访问离起点最近的节点
DFS（深度优先搜索）：沿着分支深入到底部，再回溯探索其他分支

核心应用场景

算法	典型应用场景
BFS	最短路径问题、社交网络好友推荐、连通块分析
DFS	路径存在性判断、拓扑排序、解决回溯问题、图连通性检测

二、BFS算法详解

算法思想

BFS采用分层遍历策略，如同水波纹扩散：

从起点开始遍历
先访问所有相邻节点
再访问相邻节点的相邻节点
依此类推直到遍历完成

核心数据结构：队列

#include <queue>
queue<int> q; // 创建队列q.push(startNode); // 起点入队
while (!q.empty()) {int cur = q.front(); // 取队首q.pop();            // 队首出队// 处理当前节点for (相邻节点) {if (节点未访问) {q.push(相邻节点); // 新节点入队}}
}

完整BFS示例：网格最短路径

#include <iostream>
#include <queue>
#include <vector>
using namespace std;const int N = 100;
int grid[N][N];      // 网格地图
int dist[N][N];      // 存储到每个点的距离
bool visited[N][N];  // 标记数组
int dx[4] = {1, -1, 0, 0}; // 方向数组：上下左右
int dy[4] = {0, 0, 1, -1};int bfs(int startX, int startY, int endX, int endY, int n, int m) {queue<pair<int, int>> q;q.push({startX, startY});visited[startX][startY] = true;dist[startX][startY] = 0;while (!q.empty()) {auto [x, y] = q.front();q.pop();// 到达终点if (x == endX && y == endY) return dist[x][y];// 遍历四个方向for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];// 检查边界和访问状态if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && grid[nx][ny] != 0) {visited[nx][ny] = true;dist[nx][ny] = dist[x][y] + 1;q.push({nx, ny});}}}return -1; // 无法到达终点
}int main() {// 示例：5x5网格，1表示可通过，0表示障碍int n = 5, m = 5;vector<vector<int>> exampleGrid = {{1,1,1,1,1},{1,0,1,0,1},{1,1,1,1,1},{1,0,0,0,1},{1,1,1,1,1}};// 初始化gridfor (int i = 0; i < n; i++) for (int j = 0; j < m; j++) grid[i][j] = exampleGrid[i][j];int result = bfs(0, 0, 4, 4, n, m);cout << "最短路径长度: " << result << endl;return 0;
}

BFS算法特性

时间复杂度：O(V+E)（V为顶点数，E为边数）
空间复杂度：O(V)
保证找到最短路径（当边权相等时）
不适合深度极大的搜索树

三、DFS算法详解

算法思想

DFS采用深度探索策略：

从起点选择一条路径深入
走到尽头后回溯
选择未探索的分支继续深入
重复直到所有路径被探索

实现方式：递归 vs 栈

递归实现（推荐）：

void dfs(int node, vector<bool>& visited, vector<vector<int>>& graph) {visited[node] = true;// 处理当前节点for (int neighbor : graph[node]) {if (!visited[neighbor]) {dfs(neighbor, visited, graph);}}
}

栈实现：

void dfs(int start, vector<vector<int>>& graph) {stack<int> s;vector<bool> visited(graph.size(), false);s.push(start);visited[start] = true;while (!s.empty()) {int cur = s.top();s.pop();// 处理当前节点for (int neighbor : graph[cur]) {if (!visited[neighbor]) {visited[neighbor] = true;s.push(neighbor);}}}
}

完整DFS示例：图的连通分量

#include <iostream>
#include <vector>
using namespace std;void dfs(int node, vector<bool>& visited, vector<vector<int>>& graph) {visited[node] = true;cout << "访问节点: " << node << endl; // 处理当前节点for (int neighbor : graph[node]) {if (!visited[neighbor]) {dfs(neighbor, visited, graph);}}
}int main() {int n = 6; // 节点数量vector<vector<int>> graph(n);// 构建图：无向图示例graph[0] = {1, 2};graph[1] = {0, 3};graph[2] = {0, 3, 4};graph[3] = {1, 2, 5};graph[4] = {2};graph[5] = {3};vector<bool> visited(n, false);int components = 0;for (int i = 0; i < n; i++) {if (!visited[i]) {components++;cout << "连通分量 #" << components << ":" << endl;dfs(i, visited, graph);}}cout << "总连通分量数: " << components << endl;return 0;
}

DFS算法特性

时间复杂度：O(V+E)
空间复杂度：O(h)（h为最大递归深度）
适合解决连通性问题
可能陷入深度极大的路径
不保证找到最短路径

四、BFS vs DFS 对比指南

特性	BFS	DFS
数据结构	队列	栈/递归
空间占用	高（存储整层节点）	低（仅当前路径）
最优解	保证最短路径（等权图）	不一定
适用场景	最短路径、最近邻居	所有解、连通性检测
实现复杂度	中等	简单
内存风险	宽图可能内存溢出	深图可能栈溢出

选择策略：

求最短路径 → BFS
检查路径存在性 → DFS
图宽度大深度小 → DFS
图深度大宽度小 → BFS
需要所有可能解 → DFS

五、实战应用：岛屿问题

问题描述

给定一个由'1'(陆地)和'0'(水)组成的网格，计算岛屿数量。岛屿由水平或垂直相邻的陆地组成。

BFS解法

int numIslandsBFS(vector<vector<char>>& grid) {if (grid.empty()) return 0;int n = grid.size(), m = grid[0].size();int islands = 0;int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == '1') {islands++;queue<pair<int, int>> q;q.push({i, j});grid[i][j] = '0'; // 标记为已访问while (!q.empty()) {auto [x, y] = q.front();q.pop();for (int k = 0; k < 4; k++) {int nx = x + dx[k], ny = y + dy[k];if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == '1') {grid[nx][ny] = '0';q.push({nx, ny});}}}}}}return islands;
}

DFS解法

void dfs(vector<vector<char>>& grid, int x, int y) {if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == '0') return;grid[x][y] = '0'; // 标记为已访问// 四个方向递归dfs(grid, x + 1, y);dfs(grid, x - 1, y);dfs(grid, x, y + 1);dfs(grid, x, y - 1);
}int numIslandsDFS(vector<vector<char>>& grid) {if (grid.empty()) return 0;int n = grid.size(), m = grid[0].size();int islands = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == '1') {islands++;dfs(grid, i, j);}}}return islands;
}