最短时间学会基于C++实现DFS深度优先搜索

最短时间学会基于C++实现DFS深度优先搜索攻略

什么是DFS深度优先搜索

DFS即深度优先搜索,是一种基于搜索算法的遍历和检索树或图数据结构的算法。DFS算法采用深度优先策略,从根结点出发访问所有可达结点,直到叶子节点。在访问某个结点时,先访问该结点的第一个未访问的相邻节点,然后递归的访问其非相邻节点。其搜索的核心思想是根据某个搜索方向向前搜索到底,直至无法继续下去时就回到上一个结点重新选择另一片区域搜索,直至所有结点都被访问。

实现DFS深度优先搜索

方式一:递归实现DFS深度优先搜索

递归实现DFS深度优先搜索比较简单,只需要实现以下三个步骤:

  1. 判断当前节点是否已经被访问过,如果访问过,返回。
  2. 将当前节点标记为已访问。
  3. 对当前节点的所有未被访问过的临界节点进行访问,递归重复以上步骤。
void dfs(int cur, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[cur] = true;
    for (int i = 0; i < graph[cur].size(); i++) {
        int neighbor = graph[cur][i];
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

方式二:栈实现DFS深度优先搜索

使用栈来实现DFS深度优先搜索的方法,具备更好的可读性和可维护性。由于需要遍历到所有未访问的节点,因此不能直接用栈进行遍历,需要将根节点压入栈内,然后使用while循环进行遍历,直到栈为空。

void dfs(int start, vector<vector<int>>& graph, vector<bool>& visited) {
    stack<int> s;
    s.push(start);
    while (!s.empty()) {
        int cur = s.top();
        s.pop();
        if (visited[cur]) continue;
        visited[cur] = true;
        for (int i = graph[cur].size() - 1; i >= 0; i--) {
            int neighbor = graph[cur][i];
            if (!visited[neighbor]) {
                s.push(neighbor);
            }
        }
    }
}

示例1:图的遍历

例如,我们要遍历一个图,对该图进行DFS深度优先搜索,可以使用以下代码:

int main() {
    vector<vector<int>> graph(5);
    graph[0].push_back(1);
    graph[1].push_back(2);
    graph[2].push_back(3);
    graph[3].push_back(4);
    graph[4].push_back(1);

    vector<bool> visited(5, false);
    dfs(0, graph, visited);

    return 0;
}

以上代码中,我们以图中的0号节点为起始节点,进行深度优先遍历。

示例2:迷宫的搜索

以下代码提供一个方格迷宫搜索的示例,使用DFS深度优先搜索解决,其中,我们使用了递归。

int maze[5][5] = {
    { 0, 0, 0, 0, 1 },
    { 0, 1, 0, 1, 0 },
    { 0, 0, 0, 1, 0 },
    { 1, 1, 0, 0, 0 },
    { 0, 0, 1, 0, 0 }
};

bool visited[5][5];
int dstX = 4, dstY = 4;

bool dfs(int curX, int curY) {
    if (curX < 0 || curY < 0 || curX >= 5 || curY >= 5 || visited[curX][curY] || maze[curX][curY] == 1) {
        return false;
    }
    if (curX == dstX && curY == dstY) {
        return true;
    }
    visited[curX][curY] = true;
    if (dfs(curX-1, curY) || dfs(curX+1, curY) || dfs(curX, curY-1) || dfs(curX, curY+1)) {
        return true;
    }
    visited[curX][curY] = false;
    return false;
}

总结

以上是两种实现DFS深度优先搜索的方法及其示例解决方案。简单的递归实现可以快速实现,但是在处理效率相对较低的情况下会出现栈空间不足的问题,此时栈毕竟是有限大小的,如果栈深度过大会导致程序崩溃。栈实现的方法则可以避免这个问题。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:最短时间学会基于C++实现DFS深度优先搜索 - Python技术站

(0)
上一篇 2023年5月22日
下一篇 2023年5月22日

相关文章

  • 在Python 中将类对象序列化为JSON

    序列化(Serialization)指的是将数据结构或对象状态转换为可以存储或传输的格式的过程。其中,将数据转换成JSON格式是常见的序列化方式之一。Python 中提供了通用的序列化模块 json 来实现将数据转换为JSON格式,其中也包括对象的序列化操作。 下面是将 Python 类对象序列化为 JSON 的完整操作步骤: 导入 JSON 模块 json…

    C 2023年5月23日
    00
  • 详解dll动态库的开发与调用及文件的读写小程序

    详解dll动态库的开发与调用及文件的读写小程序 动态链接库(DLL)是一种非常重要的可执行文件类型,它允许各种应用程序在加载时动态地调用它所包含的函数或者资源。本文将详细说明如何开发和调用DLL动态链接库,并提供文件读写小程序的示例。 DLL动态库开发 1. DLL的定义 首先,我们要定义我们的DLL动态链接库,用到的头文件如下: #ifndef _MY_D…

    C 2023年5月23日
    00
  • C# 格式化JSON的两种实现方式

    下面我会详细讲解“C# 格式化JSON的两种实现方式”的完整攻略。 标准化JSON 在对JSON进行格式化处理之前,我们需要首先将其标准化,这样可以排除语义上的差异,从而方便后续的处理。具体实现方法是:按照字典序对JSON的对对象属性进行排序,这个排序过程会递归遍历对象及其属性。 在C#中,可以使用Newtonsoft.Json库提供的以下类和方法来将JSO…

    C 2023年5月23日
    00
  • 电脑无法启动并提示0xc000000e怎么办

    电脑无法启动并提示0xc000000e的解决方法 问题描述 当电脑启动时,可能会出现以下错误信息: Windows Failed to start. A recent hardware or software change might be the cause. To fix the problem: 1. Insert your Windows insta…

    C 2023年5月23日
    00
  • C语言 存储类详解及示例代码

    “C语言 存储类详解及示例代码”是一篇介绍C语言中存储类的文章。本文讲解了C语言中的四种存储类(自动存储类、静态存储类、寄存器存储类、外部存储类)的特点、使用方法以及示例代码。 自动存储类 自动存储类是指在函数或代码块内定义的变量。它们通常在代码块内使用,并且在代码块外是不可见的。自动存储类变量的值在函数或代码块的开始处自动初始化为随机值。例如,在以下代码中…

    C 2023年5月24日
    00
  • C++面向对象中构造函数使用详解

    C++面向对象中构造函数使用详解 在C++面向对象编程中,构造函数是一个非常重要的概念,它负责对象的初始化和内存分配等工作。本文将详细讲解C++面向对象中构造函数的使用,包括构造函数的声明、定义以及调用,以及构造函数的默认参数和重载等概念。 构造函数的声明与定义 构造函数的声明和普通函数的声明类似,都需要指定函数名、参数列表和返回类型。但是,构造函数没有返回…

    C 2023年5月22日
    00
  • C语言 strlen()函数

    当我们需要获取一个字符串的长度时,可以使用C语言中的 strlen() 函数。下面是该函数的完整使用攻略: 函数原型 size_t strlen(const char *str); 函数参数 str:要计算长度的字符串。必须为C风格的字符串,以\0结尾。 函数返回值 函数返回值为该字符串的长度,不包括\0。 使用示例一 下面是一个简单的示例,展示如何使用 s…

    C 2023年5月9日
    00
  • 基于C语言打造高效通讯录的示例代码

    针对“基于C语言打造高效通讯录的示例代码”的完整攻略,我们可以分为以下几个步骤来进行讲解: 1.设计数据结构 在打造通讯录的代码中,我们需要首先设计合理的数据结构来储存通讯录信息。在此我们可以采用链表数据结构来实现。所以在数据结构的设计中,需要定义一个结构体来存储每位通讯录人员的信息,然后私有一个指向实体的指针来实现链表。 2.实现通讯录基本功能 通讯录的基…

    C 2023年5月24日
    00
合作推广
合作推广
分享本页
返回顶部