C++ DFS与BFS算法实现详解

在C++中，深度优先搜索（DFS）和广度优先搜索（BFS）是图或树遍历的两种基础算法。它们常用于解决连通性、路径查找、拓扑排序等问题。下面分别给出基于邻接表存储的无向图的DFS和BFS实现代码。

1. 深度优先搜索（DFS）

DFS使用递归或栈来实现，优先深入访问未访问的邻接节点。

以下是一个用递归实现的DFS示例：

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

class Graph {
    int n;
    vector<vector<int>> adj;

public:
    Graph(int n) : n(n), adj(n) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u); // 无向图
    }

    void dfs(int start) {
        unordered_set<int> visited;
        dfsHelper(start, visited);
    }

private:
    void dfsHelper(int u, unordered_set<int>& visited) {
        visited.insert(u);
        cout << u << " ";

        for (int v : adj[u]) {
            if (!visited.count(v)) {
                dfsHelper(v, visited);
            }
        }
    }
};

// 使用示例
int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);

    cout << "DFS traversal: ";
    g.dfs(0);
    cout << endl;

    return 0;
}

2. 广度优先搜索（BFS）

BFS使用队列实现，逐层访问相邻节点，适合求最短路径。

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

class Graph {
    int n;
    vector<vector<int>> adj;

public:
    Graph(int n) : n(n), adj(n) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void bfs(int start) {
        unordered_set<int> visited;
        queue<int> q;

        visited.insert(start);
        q.push(start);

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            cout << u << " ";

            for (int v : adj[u]) {
                if (!visited.count(v)) {
                    visited.insert(v);
                    q.push(v);
                }
            }
        }
    }
};

// 使用示例
int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);

    cout << "BFS traversal: ";
    g.bfs(0);
    cout << endl;

    return 0;
}

• 图使用 vector<vector<int>> 存储邻接表，适合稀疏图。
• DFS用递归实现更简洁，注意标记已访问节点避免重复。
• BFS必须使用队列，确保按层次访问。
• 使用 unordered_set 记录访问状态，效率较高。