广度优先搜索（BFS） vs 深度优先搜索（DFS）：算法对比与 C++ 实现

目录

一、BFS 和 DFS 的核心思想

1. BFS（广度优先搜索）

2. DFS（深度优先搜索）

二、BFS 和 DFS 的对比

三、C++ 代码实现

1. BFS 实现（邻接表表示的无向图）

2. DFS 实现（递归与迭代两种方式）

四、关键细节说明

1. BFS 的关键点

2. DFS 的关键点

五、应用场景对比

六、总结

一、BFS 和 DFS 的核心思想

1. BFS（广度优先搜索）

• 核心思想：按“层级”逐层遍历，先访问离起点最近的节点，再逐步向外扩散。

• 类比：类似水波扩散，一层一层向外推进。

• 数据结构：队列（FIFO）。

• 适用场景：最短路径（未加权图）、社交网络层级关系、迷宫最短路径。

2. DFS（深度优先搜索）

• 核心思想：沿着一条路径尽可能深入，直到无法继续时回溯，尝试其他分支。

• 类比：走迷宫时，遇到岔路选择一条路走到头，再返回选择其他路。

• 数据结构：栈（LIFO）或递归调用栈。

• 适用场景：拓扑排序、连通性检测、回溯问题（如八皇后）、图的环路检测。

二、BFS 和 DFS 的对比

三、C++ 代码实现

1. BFS 实现（邻接表表示的无向图）

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

void bfs(const vector<vector<int>>& graph, int start) {
    vector<bool> visited(graph.size(), false);
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " "; // 访问节点

        // 遍历当前节点的所有邻居
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

// 示例图结构
vector<vector<int>> graph = {
    {1, 2},     // 节点0的邻居
    {0, 3, 4},  // 节点1的邻居
    {0, 5, 6},  // 节点2的邻居
    {1},        // 节点3的邻居
    {1},        // 节点4的邻居
    {2},        // 节点5的邻居
    {2}         // 节点6的邻居
};

int main() {
    cout << "BFS遍历结果: ";
    bfs(graph, 0); // 输出: 0 1 2 3 4 5 6
    return 0;
}

2. DFS 实现（递归与迭代两种方式）

// 递归实现
void dfsRecursive(const vector<vector<int>>& graph, int node, vector<bool>& visited) {
    visited[node] = true;
    cout << node << " "; // 访问节点

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfsRecursive(graph, neighbor, visited);
        }
    }
}

// 迭代实现（显式栈）
void dfsIterative(const vector<vector<int>>& graph, int start) {
    vector<bool> visited(graph.size(), false);
    stack<int> s;
    s.push(start);
    visited[start] = true;

    while (!s.empty()) {
        int node = s.top();
        s.pop();
        cout << node << " ";

        // 反向遍历邻居以保证与递归顺序一致
        for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) {
            if (!visited[*it]) {
                visited[*it] = true;
                s.push(*it);
            }
        }
    }
}

int main() {
    cout << "DFS递归遍历结果: ";
    vector<bool> visited(graph.size(), false);
    dfsRecursive(graph, 0, visited); // 输出: 0 1 3 4 2 5 6

    cout << "\nDFS迭代遍历结果: ";
    dfsIterative(graph, 0);          // 输出: 0 1 3 4 2 5 6
    return 0;
}

四、关键细节说明

1. BFS 的关键点

• 队列操作：每次从队头取出节点，并将未访问的邻居加入队尾。

• 最短路径：BFS 首次访问到目标节点时，路径一定是最短的（适用于未加权图）。

• 空间复杂度：最坏情况下需存储所有节点（如完全二叉树最后一层）。

2. DFS 的关键点

• 递归与栈：递归隐式使用系统栈，迭代显式使用栈。

• 遍历顺序：迭代实现中，若按正序访问邻居，结果可能与递归顺序不同（需反向遍历邻居）。

• 应用场景：适合探索所有可能性（如回溯问题），但可能陷入深层分支无法及时返回。

五、应用场景对比

六、总结

• BFS 适合“广度优先”问题，如最短路径；DFS 适合“深度优先”问题，如回溯和连通性。

• 代码实现：BFS 用队列，DFS 用栈或递归，注意遍历顺序和空间消耗。

• 选择依据：根据问题特性（如是否需要最短路径、内存限制）选择算法。