DFS和BFS

DFS（深度优先搜索） 和 BFS（广度优先搜索） 是两种经典的图遍历算法，广泛应用于树、图等数据结构的搜索问题。下面我们详细介绍它们的原理、区别以及C++实现模板。

---

1. DFS（深度优先搜索）

核心思想

• DFS 从起点开始，沿着一条路径尽可能深入地搜索，直到无法继续为止，然后回溯到上一个节点，继续搜索其他路径。
• 使用 栈（递归或显式栈）来实现。

特点

• 适合解决 连通性、路径搜索、拓扑排序 等问题。
• 空间复杂度较低（与递归深度相关）。
• 不一定能找到最短路径。

应用场景

• 图的连通性检测。
• 寻找所有可能的路径。
• 拓扑排序。
• 解决回溯问题（如八皇后、数独）。

C++ 模板

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

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    // 标记当前节点为已访问
    visited[node] = true;
    cout << "Visited node: " << node << endl;

    // 遍历当前节点的所有邻居
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited); // 递归访问邻居
        }
    }
}

int main() {
    // 示例：图的邻接表表示
    vector<vector<int>> graph = {
        {1, 2},    // 节点 0 的邻居
        {0, 3, 4}, // 节点 1 的邻居
        {0, 5},    // 节点 2 的邻居
        {1},       // 节点 3 的邻居
        {1},       // 节点 4 的邻居
        {2}        // 节点 5 的邻居
    };

    int startNode = 0; // 从节点 0 开始 DFS
    vector<bool> visited(graph.size(), false); // 记录节点是否被访问过
    dfs(startNode, graph, visited);

    return 0;
}

---

2. BFS（广度优先搜索）

核心思想

• BFS 从起点开始，逐层扩展搜索，先访问离起点最近的节点，再访问更远的节点。
• 使用 队列 来实现。

特点

• 适合解决 最短路径、层级遍历 等问题。
• 空间复杂度较高（与队列大小相关）。
• 一定能找到最短路径（在无权图中）。

应用场景

• 无权图的最短路径。
• 层级遍历（如二叉树的层次遍历）。
• 连通性检测。

C++ 模板

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

void bfs(int startNode, vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false); // 记录节点是否被访问过
    queue<int> q;

    // 从起点开始 BFS
    q.push(startNode);
    visited[startNode] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << "Visited node: " << node << endl;

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

int main() {
    // 示例：图的邻接表表示
    vector<vector<int>> graph = {
        {1, 2},    // 节点 0 的邻居
        {0, 3, 4}, // 节点 1 的邻居
        {0, 5},    // 节点 2 的邻居
        {1},       // 节点 3 的邻居
        {1},       // 节点 4 的邻居
        {2}        // 节点 5 的邻居
    };

    int startNode = 0; // 从节点 0 开始 BFS
    bfs(startNode, graph);

    return 0;
}

---

3. DFS 和 BFS 的区别

特性	DFS	BFS
数据结构	栈（递归或显式栈）	队列
搜索方式	深度优先	广度优先
空间复杂度	较低（与递归深度相关）	较高（与队列大小相关）
最短路径	不一定能找到最短路径	一定能找到最短路径（无权图）
适用场景	路径搜索、回溯问题	最短路径、层级遍历

---

4. DFS 和 BFS 的选择

• 如果需要 找到最短路径 或 层级遍历，优先选择 BFS。
• 如果需要 遍历所有可能的路径 或 解决回溯问题，优先选择 DFS。

---

5. 总结

• DFS 和 BFS 是图遍历的基础算法，各有优缺点。
• DFS 使用栈实现，适合深度搜索；BFS 使用队列实现，适合广度搜索。
• 根据具体问题选择合适的算法。