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

尼克

发布时间：2025-10-22 13:36:01

888人浏览过

来源于php中文网

原创

图的深度优先搜索从起始顶点开始沿路径深入访问，使用邻接表和递归或栈实现；需标记访问状态避免重复，对不连通图需多次调用DFS以遍历所有节点。

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

图的深度优先搜索（DFS）是一种用于遍历或搜索图中节点的算法。它从一个起始顶点开始，沿着一条路径尽可能深入地访问未访问过的邻接点，直到无法继续前进，再回溯并尝试其他分支。C++ 中可以通过邻接表或邻接矩阵结合递归或栈来实现 DFS。

使用邻接表和递归实现 DFS

邻接表是表示图的一种高效方式，尤其适用于稀疏图。使用 vector> 存储每个顶点的邻接点，配合布尔数组记录访问状态。

步骤说明：

创建图的邻接表结构
维护一个 visited 数组防止重复访问
从指定起点开始递归访问所有未访问的邻接点

代码示例：

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

#include 
#include 
using namespace std;

class Graph {
    int V; // 顶点数量
    vector> adj; // 邻接表

    void dfsUtil(int v, vector& visted) {
        visted[v] = true;
        cout << v << " ";

        for (int neighbor : adj[v]) {
            if (!visted[neighbor]) {
                dfsUtil(neighbor, visted);
            }
        }
    }

public:
    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u); // 无向图，若为有向图则删除此行
    }

    void dfs(int start) {
        vector visited(V, false);
        dfsUtil(start, visited);
    }
};

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

    cout << "从顶点 0 开始的 DFS 遍历: ";
    g.dfs(0);
    return 0;
}

使用栈实现非递归 DFS

递归本质是系统调用栈，也可以手动使用 stack 实现 DFS，避免递归带来的栈溢出风险，尤其在图较大时更安全。

微信 WeLM

WeLM不是一个直接的对话机器人，而是一个补全用户输入信息的生成模型。

下载

核心思路：

用 stack 存储待访问的顶点
每次取出栈顶，标记为已访问并输出
将其未访问的邻接点压入栈

非递归实现代码片段：

void dfsIterative(int start) {
    vector visited(V, false);
    stack stk;
    stk.push(start);

    while (!stk.empty()) {
        int curr = stk.top();
        stk.pop();

        if (visited[curr]) continue;
        visited[curr] = true;
        cout << curr << " ";

        // 逆序压入邻接点，保证顺序一致（可选）
        for (auto it = adj[curr].rbegin(); it != adj[curr].rend(); ++it) {
            if (!visited[*it]) {
                stk.push(*it);
            }
        }
    }
}

注意事项与优化建议

DFS 实现时需注意以下几点：

确保图的索引从 0 或 1 开始统一，避免越界
无向图添加边时要双向插入
访问数组大小初始化为 V，并初始为 false
若图不连通，需对每个未访问顶点调用 DFS 才能遍历全图

基本上就这些。根据实际需求选择递归或迭代方式，邻接表适合大多数场景。理解状态标记和回溯机制是掌握 DFS 的关键。

C++ 怎么实现二叉树 C++节点定义与前中后序遍历【数据结构】

C++ 怎么实现链表反转 C++ 单链表头插法与递归反转代码【数据结构】

C多线程并发处理方式_C语言线程并发处理策略

c++如何实现斐波那契数列_c++递归与非递归写法【算法】

c++中堆和栈的区别是什么_c++内存管理基础【笔记】

c++速学教程(入门到精通)

c++怎么学习？c++怎么入门？c++在哪学？c++怎么学才快？不用担心，这里为大家提供了c++速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！

下载

相关标签:

edge 栈 ai c++ ios stream 递归 int 栈算法

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：c++如何求两个数的最大公约数_c++求GCD算法实现方法下一篇：c++怎么使用std::chrono精确测量时间_c++ chrono高精度计时用法

作者最新文章

Linux怎么查看内存使用 Linux查询内存剩余及占用分析【详解】

2026-01-26 09:10

MAC怎么设置程序全屏_MAC窗口全屏与退出全屏快捷键【小白入门】

2026-01-26 09:19

c++中如何生成随机数_c++ rand与srand用法【指南】

2026-01-26 09:19

iphone日历总有垃圾广告怎么办_苹果手机清除日历弹窗【清理】

2026-01-26 09:21

iQOO手机怎么开启双WiFi加速_iQOO网络加速设置教程【诀窍】

2026-01-26 09:23

BIOS设置丢失？CMOS电池耗尽或重置异常【配置还原】

2026-01-26 09:24

OPPO手机充电慢是怎么回事 OPPO手机无法快充的原因与解决办法【一文搞懂】

2026-01-26 09:27

C++怎么保留两位小数 C++控制输出精度iomanip使用教程【格式】

2026-01-26 09:31

Linux怎么统计文件行数 Linux计算文件字数wc命令用法【技巧】

2026-01-26 09:41

电脑怎么禁止程序联网？在电脑防火墙中设置应用访问权限【教程】

2026-01-26 09:43

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI 编程开发 AI 聊天问答

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI 编程开发 AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI 编程开发 Agent智能体

腾讯元宝

腾讯混元平台推出的AI助手

文档处理 AI 聊天问答

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI 编程开发 AI 文本写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

AI 文本写作中文写作

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接图画生成

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI 编程开发 AI 文本写作

智谱清言 - 免费全能的AI助手

AI 编程开发 Agent智能体

相关专题

string转int

在编程中，我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算，或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章，欢迎大家前来学习阅读。

421

2023.08.02

int占多少字节

int占4个字节，意味着一个int变量可以存储范围在-2,147,483,648到2,147,483,647之间的整数值，在某些情况下也可能是2个字节或8个字节，int是一种常用的数据类型，用于表示整数，需要根据具体情况选择合适的数据类型，以确保程序的正确性和性能。本专题为大家提供相关的文章、下载、课程内容，供大家免费下载体验。

543

2024.08.29