c++ dfs和bfs代码 c++深度广度优先搜索算法-C++-PHP中文网

c++ dfs和bfs代码 c++深度广度优先搜索算法

裘德小鎮的故事

发布： 2025-12-01 12:52:03

原创

216人浏览过

DFS和BFS是图遍历的基础算法，DFS用递归深入访问，BFS用队列实现层级遍历，均需标记已访问节点避免重复。

c++ dfs和bfs代码 c++深度广度优先搜索算法

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

1. 深度优先搜索（DFS）

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

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

Cowriter

AI 作家，帮助加速和激发你的创意写作

107

查看详情

#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使用队列实现，逐层访问相邻节点，适合求最短路径。

立即学习“C++免费学习笔记（深入）”；

#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;
}

登录后复制

关键点说明：