C++怎么实现图的深度优先搜索(DFS)_C++图算法与DFS遍历实现-C++-PHP中文网

C++怎么实现图的深度优先搜索(DFS)_C++图算法与DFS遍历实现

裘德小鎮的故事

发布： 2025-11-18 14:11:03

原创

327人浏览过

答案：文章介绍了C++中使用邻接表和递归实现图的深度优先搜索（DFS）的方法，包括图的表示、DFS遍历逻辑、完整代码示例及注意事项。

c++怎么实现图的深度优先搜索(dfs)_c++图算法与dfs遍历实现

深度优先搜索（DFS）是一种用于遍历或搜索图和树的算法。在C++中，可以通过递归或栈来实现图的DFS。下面介绍如何用邻接表表示图，并使用递归方式实现DFS遍历。

图的表示：邻接表

在C++中，通常使用vector<vector<int>>来表示无权图的邻接表。每个节点对应一个vector，存储与其相邻的节点。

例如，一个包含n个节点的图：

vector<vector<int>> graph(n);

添加边（假设是无向图）：

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

graph[u].push_back(v);
graph[v].push_back(u);

DFS递归实现

使用布尔数组visited[]记录节点是否被访问过，防止重复访问。

纳米搜索

纳米搜索：360推出的新一代AI搜索引擎

查看详情

核心思路：从起始节点开始，标记为已访问，然后递归访问其所有未访问的邻接节点。

void dfs(int node, vector<bool>& visited, vector<vector<int>>& graph) {
    visited[node] = true;
    cout << node << " ";

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

完整示例代码

以下是一个完整的C++程序，演示如何构建图并进行DFS遍历：

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

void dfs(int node, vector<bool>& visited, vector<vector<int>>& graph) {
    visited[node] = true;
    cout << node << " ";

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

int main() {
    int n = 5; // 节点数
    vector<vector<int>> graph(n);

    // 添加边
    graph[0].push_back(1);
    graph[1].push_back(0);

    graph[0].push_back(2);
    graph[2].push_back(0);

    graph[1].push_back(3);
    graph[3].push_back(1);

    graph[2].push_back(4);
    graph[4].push_back(2);

    vector<bool> visited(n, false);

    cout << "DFS traversal: ";
    dfs(0, visited, graph);
    cout << endl;

    return 0;
}

注意事项与扩展

该实现适用于无向无权图。若图为有向图，添加边时只需单向添加。对于带权图，可使用vector<vector<pair<int, int>>>存储邻接点及其权重。

非递归版本可用stack模拟递归过程，避免深层递归导致的栈溢出。

基本上就这些，掌握邻接表和递归访问逻辑就能灵活应用DFS解决连通性、路径查找等问题。

百景图相关攻略
OKEX官网地址	江南百景图保安堂药铺获取攻略	PPT设置两幅图同时做动画效果的操作方法
C++ 递归函数在图数据结构中的应用？	如何通过 PHP 递归函数创建自相关图形	江南百景图草龟怎么获取探秘草龟捕获技巧
江南百景图水中亭怎么获取获取途径	江南百景图黄泥怎么获取黄泥搜集窍门	江南百景图桃花涎怎么获取怎么搞到桃花涎的技巧
江南百景图鼓怎么获取打鼓技巧获取途径	江南百景图花篮怎么放在空地上如何在空地摆放花篮	美图持有多少比特币和以太坊？具体数量介绍
c++中如何计算图的入度和出度_c++图入度出度计算方法