C++深度优先搜索介绍

🕗 发布于 2025-01-20 08:46 c++ 深度优先 开发语言

C++深度优先搜索介绍

一、引言

在计算机科学领域，搜索算法是解决众多问题的基础。深度优先搜索（Depth-First Search，DFS）作为一种经典的图遍历算法，不仅在图论问题中有着广泛应用，还能用于解决许多其他类型的问题，如迷宫求解、路径规划、游戏人工智能等。在C++ 语言环境下，利用其强大的编程特性，可以高效地实现深度优先搜索算法。本文将深入探讨C++ 中的深度优先搜索，包括其原理、实现方式、应用场景以及常见优化策略。

二、深度优先搜索基本原理

（一）定义

深度优先搜索是一种用于遍历或搜索树或图的算法。其核心思想是从起始节点开始，沿着一条路径尽可能深地探索下去，直到无法继续或达到目标节点。当到达一个无法继续前进的节点（即该节点的所有邻接节点都已被访问过）时，回溯到上一个节点，继续探索其他未访问的路径，直到所有节点都被访问或找到目标节点。

（二）直观理解

可以将深度优先搜索想象成在一个迷宫中探索。从迷宫的入口出发，你总是选择一条通道一直走下去，直到遇到死胡同（即没有新的通道可走）。这时，你会沿着来时的路往回走，直到找到一个还有未探索通道的岔路口，然后继续探索新的通道。这个过程不断重复，直到遍历完整个迷宫或找到出口。

（三）与广度优先搜索的区别

广度优先搜索（Breadth-First Search，BFS）也是一种常见的图遍历算法。与DFS不同，BFS是从起始节点开始，一层一层地向外扩展，先访问距离起始节点近的节点，再访问距离远的节点。而DFS则是沿着一条路径尽可能深地探索。例如，在一个树结构中，BFS会先访问根节点的所有子节点，然后再访问子节点的子节点；而DFS会先访问根节点的一个子节点，然后递归地访问该子节点的子节点，直到到达叶子节点，再回溯到上一层。

三、C++ 实现深度优先搜索

（一）基于邻接矩阵的图表示

在C++ 中，图可以用多种方式表示，其中邻接矩阵是一种简单直观的表示方法。邻接矩阵是一个二维数组，对于一个有n个节点的图，邻接矩阵graph[i][j]表示节点i和节点j之间是否有边相连。如果graph[i][j]的值为1，则表示节点i和节点j之间有边；如果为0，则表示没有边。

#include <iostream>
#include <vector>

const int N = 100;  // 图中节点的最大数量
int graph[N][N];  // 邻接矩阵
bool visited[N];  // 标记节点是否被访问过

// 深度优先搜索函数
void dfs(int node) {
    visited[node] = true;
    std::cout << node << " ";  // 访问节点
    for (int i = 0; i < N; ++i) {
        if (graph[node][i] &&!visited[i]) {
            dfs(i);  // 递归访问未访问的邻接节点
        }
    }
}

int main() {
    // 初始化图
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            graph[i][j] = 0;
        }
        visited[i] = false;
    }

    // 添加边
    graph[0][1] = 1;
    graph[1][0] = 1;
    graph[0][2] = 1;
    graph[2][0] = 1;

    // 从节点0开始进行深度优先搜索
    dfs(0);

    return 0;
}

（二）基于邻接表的图表示

邻接表是另一种常用的图表示方法，它比邻接矩阵更节省空间，特别是对于稀疏图（边的数量远小于节点数量的平方）。邻接表使用一个数组或向量来存储每个节点的邻接节点列表。

#include <iostream>
#include <vector>

const int N = 100;  // 图中节点的最大数量
std::vector<int> graph[N];  // 邻接表
bool visited[N];  // 标记节点是否被访问过

// 深度优先搜索函数
void dfs(int node) {
    visited[node] = true;
    std::cout << node << " ";  // 访问节点
    for (int i = 0; i < graph[node].size(); ++i) {
        int neighbor = graph[node][i];
        if (!visited[neighbor]) {
            dfs(neighbor);  // 递归访问未访问的邻接节点
        }
    }
}

int main() {
    // 初始化图
    for (int i = 0; i < N; ++i) {
        visited[i] = false;
    }

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

    // 从节点0开始进行深度优先搜索
    dfs(0);

    return 0;
}

（三）递归与非递归实现

递归实现：上述代码中使用的是递归方式实现深度优先搜索。递归实现简洁明了，符合DFS的思想，但是当递归深度过大时，可能会导致栈溢出。
非递归实现：可以使用栈来实现非递归的深度优先搜索。在非递归实现中，将起始节点压入栈中，然后不断从栈中弹出节点并访问，将其未访问的邻接节点压入栈中，直到栈为空。

#include <iostream>
#include <vector>
#include <stack>

const int N = 100;  // 图中节点的最大数量
std::vector<int> graph[N];  // 邻接表
bool visited[N];  // 标记节点是否被访问过

// 非递归深度优先搜索函数
void dfs_non_recursive(int start) {
    std::stack<int> stk;
    stk.push(start);

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

        if (!visited[node]) {
            visited[node] = true;
            std::cout << node << " ";  // 访问节点

            for (int i = graph[node].size() - 1; i >= 0; --i) {
                int neighbor = graph[node][i];
                if (!visited[neighbor]) {
                    stk.push(neighbor);
                }
            }
        }
    }
}

int main() {
    // 初始化图
    for (int i = 0; i < N; ++i) {
        visited[i] = false;
    }

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

    // 从节点0开始进行非递归深度优先搜索
    dfs_non_recursive(0);

    return 0;
}

四、深度优先搜索的应用场景

（一）迷宫求解

在迷宫问题中，可以将迷宫的每个格子看作一个节点，相邻的格子之间有边相连。从起点开始，使用深度优先搜索来探索迷宫，直到找到终点。在搜索过程中，需要标记已经访问过的格子，以避免重复访问。

（二）路径规划

在地图导航等路径规划问题中，地图可以看作是一个图，城市或地点是节点，道路是边。深度优先搜索可以用于寻找从一个地点到另一个地点的路径。当然，实际应用中可能需要结合其他算法（如A*算法）来提高搜索效率。

（三）游戏人工智能

在一些策略游戏中，深度优先搜索可以用于评估不同的行动策略。例如，在国际象棋中，计算机可以使用深度优先搜索来探索不同的走法，并评估每种走法的优劣，从而选择最优的走法。

（四）图的连通性检测

通过深度优先搜索可以判断一个图是否连通。从任意一个节点开始进行深度优先搜索，如果能够访问到图中的所有节点，则说明图是连通的；否则，图是不连通的。

五、深度优先搜索的优化策略

（一）剪枝优化

在搜索过程中，如果发现某些路径不可能得到最优解或者不符合问题的约束条件，可以提前终止对这些路径的搜索，这就是剪枝。例如，在求解0 - 1背包问题时，如果当前已经放入背包的物品重量加上下一个物品的重量超过了背包的容量，就可以直接跳过该物品，不再继续搜索包含该物品的路径。

（二）记忆化搜索

对于一些重复计算的子问题，可以使用记忆化搜索来避免重复计算。在深度优先搜索过程中，将已经计算过的子问题的结果记录下来，当再次遇到相同的子问题时，直接从记录中获取结果，而不需要重新计算。例如，在计算斐波那契数列时，可以使用记忆化搜索来提高计算效率。

六、总结

深度优先搜索是一种强大而灵活的算法，在C++ 中可以通过多种方式高效实现。它在许多领域都有着广泛的应用，理解和掌握深度优先搜索对于解决各种编程问题至关重要。通过不断练习和应用，结合不同的优化策略，可以进一步提高深度优先搜索算法的效率和实用性。在实际编程中，需要根据具体问题的特点选择合适的图表示方法和实现方式，以充分发挥深度优先搜索的优势。

原文地址：https://blog.csdn.net/abcdeWA/article/details/145241523

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：PyQt5超详细教程终篇
下一篇：同城生鲜配送系统架构与功能分析

语言模型的价值定位与技术突破：从信息处理到创新认知
当前语言模型的核心价值主要体现在信息综合与处理能力上，用户友好的交互界面是其成功关键。在模型计算机制方面，推理能力的实现包括chain-of-thought和自适应计算两种范式，而内部计算过程研究将成
阅读更多2025-01-21
Python绘制数据地图-MovingPandas
是一个用于时空数据分析的 Python 库，它扩展了 Pandas 和 GeoPandas，使得处理和分析带有时间戳的地理数据变得更加方便。请注意，这个示例非常基础，只是简单地绘制了每个时间点的位置。
阅读更多2025-01-21
《数字图像处理（面向新工科的电工电子信息基础课程系列教材）》重印变更的彩插
禹晶、肖创柏、廖庆敏《数字图像处理（面向新工科的电工电子信息基础课程系列教材）》第一次重印变更的彩插
阅读更多2025-01-21
Redis-HyperLogLog
是Redis的高级数据结构，它在做的时候非常有用，每个HyperLogLog的键可以计算接近2^64不同元素的基数，而大小只需要12KB。目前只支持3个命令，PFADDPFCOUNTPFMERGE。底
阅读更多2025-01-21
SpringBoot集成 jakarta mail 实现发送邮件
3、如上示例只验证了简单内容的邮件，也支持附件、HTML内容、抄送等邮件。2、MailAccount实例配置。验证结果：皆成功收到邮件。
阅读更多2025-01-21
gitlab使用多数据库
如果现有的gitlabhq_production已经有了ci的相关数据，那么就通过停止puma/rails服务，然后备份gitlabhq_production库，在将备份的sql写入到gitlabhq
阅读更多2025-01-21
基于springboot+thymeleaf+Redis仿知乎网站问答项目源码
基于springboot+thymeleaf+Redis仿知乎网站问答项目源码，可以作为毕业设计项目参考学习按照需要一定动手能力发文章，发视频，发想法，提问回答，注册登录开发环境使用技术：spring
阅读更多2025-01-21
JavaWeb开发学习笔记——MySQL
跟着黑马程序员学习MySQL注意，以下笔记中[]中都是可省略内容，如果不省略，那么直接写即可，不带[]
阅读更多2025-01-21
CycleGAN - CycleGAN网络：无监督图像到图像转换的生成对抗网络
CycleGAN是一种基于生成对抗网络（GAN）的无监督学习模型，旨在解决没有成对图像数据的图像到图像转换问题。其核心思想是通过引入循环一致性损失来确保生成的图像在转换回原始域时，能够保持与输入图像相
阅读更多2025-01-21
IF=58.7|肠-脑-肝轴新突破
本研究通过多组学联合分析，发现HE与患者粪便中的R.gnavus通过PDC及其代谢物PEA有关，提升了人们对HE发病机制的了解，为HE的治疗和预防策略开辟了新的途径。
阅读更多2025-01-21

C++深度优先搜索介绍