DFS深度优先搜索

这篇具有很好参考价值的文章主要介绍了DFS深度优先搜索。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


一、DFS的概念

DFS的定义

DFS(Depth-First Search)深度优先搜索,是一种常用的图遍历算法,用于在图或树数据结构中遍历所有节点。

DFS的搜索方式

深度优先搜索,AcWing算法基础(C++代码),深度优先,算法,c++
深度优先搜索,AcWing算法基础(C++代码),深度优先,算法,c++

深度优先搜索从一个起始节点开始,沿着一条路径尽可能远地访问节点,直到到达不能继续前进的节点,然后返回上一层继续探索其他路径。这个过程是递归的,通过不断地深入进入节点的子节点,直到遍历完整个图。

DFS采用的数据结构

深度优先搜索使用栈(Stack)数据结构来保存需要探索的节点。每次访问一个节点时,将其标记为已访问,并将其未访问的邻居节点压入栈中。然后从栈中弹出一个节点,继续访问该节点的未访问邻居节点,直到栈为空。

空间复杂度: O ( n ) O(n) O(n)

DFS的特点

DFS不保证找到最短路径。因为它首先沿着一条路径尽可能远地深入。如果需要找到最短路径,可以考虑使用其他算法,如广度优先搜索(BFS)或 Dijkstra 算法。一般最小步数、最短距离、最小操作次数等问题采用BFS。思路奇怪或是对空间要求高的使用深度优先搜索(DFS)。

DFS 在解决许多图论问题和遍历问题上非常有用,如查找图中的路径、连通性检测、拓扑排序等。它也可以应用于树的遍历,例如先序遍历、中序遍历和后序遍历。


二、DFS的实战应用

1.排列数字

题目描述:
给定一个整数 n n n,将数字 1 ∼ n 1∼n 1n 排成一排,将会有很多种排列方法。

现在,请你按照字典序将所有的排列方法输出。

输入格式:
共一行,包含一个整数 n n n

输出格式:
按字典序输出所有排列方案,每个方案占一行。

数据范围:
1 ≤ n ≤ 7 1≤n≤7 1n7

输入样例:

3

输出样例:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

实现思路
深度优先搜索,AcWing算法基础(C++代码),深度优先,算法,c++


代码实现:
1.使用bool类型数组来表示是否占用

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

const int N = 10;
int n, path[N];
bool st[N]; // 状态数组

void dfs(int u) // 第几个数字,一共几个数字
{
    if (u == n)// 递归到最后一个数字
    {
        for (int i = 0; i < n; i++) cout << path[i] << ' '; // 输出保存的结果
        puts(" ");
    }

    for (int i = 1; i <= n; i++)
        if (!st[i]) // 没有被用过的数
        {
            path[u] = i;
            st[i] = true; // i被用过
            dfs(u + 1);// 走到下一层
            st[i] = false;// 恢复现场
        }
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	dfs(0);
	return 0;
}

2.使用整型变量补码的每位来表示是否占用

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

const int N = 10;
int n, path[N];

void dfs(int u, int state) // 第几个数字,一共几个数字
{
    if (u == n)// 递归到最后一个数字
    {
        for (int i = 0; i < n; i++) cout << path[i] << ' '; // 输出保存的结果
        puts(" ");
    }

    for (int i = 0; i < n; i++)
        if (!(state >> i & 1)) // 没有被用过的数
        {
            path[u] = i + 1;
            dfs(u + 1, state + (1 << i));
        }
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	dfs(0, 0);
	return 0;
}

2.n-皇后问题

题目描述:
n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。

深度优先搜索,AcWing算法基础(C++代码),深度优先,算法,c++
现在给定整数 n n n,请你输出所有的满足条件的棋子摆法。

输入格式共一行,包含整数 n n n

输出格式:
每个解决方案占 n n n 行,每行输出一个长度为 n n n 的字符串,用来表示完整的棋盘状态。

其中, 表示某一个位置的方格状态为空, Q Q Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后,输出一个空行。

注意:行末不能有多余空格。

输出方案的顺序任意,只要不重复且没有遗漏即可。

数据范围:
1 ≤ n ≤ 9 1≤n≤9 1n9

输入样例:

4

输出样例:

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

代码实现:文章来源地址https://www.toymoban.com/news/detail-767572.html

//在此处,为了模拟坐标轴,使用u替换y,使用i替换x
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
const int N=20;//此处x轴和y轴的长度为10,开20是大了,但是对角线长度约1.414*10(根号2),所以数组开大有好处
int n;//此处存储输入的行数&列数,
char q[N][N];//构建棋盘,大一些没坏处,注意类型需要为char(一开始无语写了个int)
bool col[N],dg[N],udg[N];//col是Column(列)的缩写,dg是diagonal(对角)的缩写,(反对角线前面的u想不出了)
//设udg的方程为y=x+b则b=y-x,替换后b=u-i,防止出现负数,则加上n,则有b=u+n-i(其实b=n+i-u也可,目的是一个对角线能单独映射)
//设dg的方程为y=-x+b,b=y+x,替换后b=i+u,perfect
void dfs(int u){//已经操作了u行
    if(u==n){//好家伙,已经操作完u行了,一个输出了
        for(int i=0;i<n;i++){
            cout<<q[i]<<endl;
        }
        cout<<endl;
        /*这种写法也可,但是如果上面的看不懂建议补习C语言基础
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cout<<q[i][j];
            }
            cout<<endl;
        }
        cout<<endl;
        */
        return;
    }
    for(int i=0;i<n;i++){//到这一步说明还没有dfs搜索完
        if(!col[i] and !dg[i+u] and !udg[u+n-i]){//这个点在各种映射下都是合法的
            q[u][i]='Q';
            col[i]=dg[i+u]=udg[u+n-i]=true;//这些点用掉啦
            dfs(u+1);//继续往下一层探
            q[u][i]='.';
            col[i]=dg[i+u]=udg[u+n-i]=false;//出来后这些点恢复原状
        }
    }
}
int main(){
    cin>>n;//输入行数
    for(int i=0;i<n;i++){//搭建一个“船新”的棋盘
            for(int j=0;j<n;j++){
                q[i][j]='.';
            }
        }
    dfs(0);//0代表目前已经操作了0行,并且需要对第1行进行操作(在数组中映射为0行)
    return 0;
}

到了这里,关于DFS深度优先搜索的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++算法】dfs深度优先搜索(上) ——【全面深度剖析+经典例题展示】

    💃🏼 本人简介:男 👶🏼 年龄:18 📕 ps:七八天没更新了欸,这几天刚搞完元宇宙,上午一直练🚗,下午背四级单词和刷题来着,还在忙一些学弟学妹录制视频和准备开学一些事,一直没空出时间来,等 20号练完车,也马上开学了QAQ。不过今天倒是空出来一些时间,恰好这

    2024年02月02日
    浏览(43)
  • 【Python搜索算法】深度优先搜索(DFS)算法原理详解与应用,示例+代码

    目录 1 基本原理 2 DFS算法流程 3 时间复杂度 4 空间复杂度 5 DFS算法应用案例: 5.1 解决路径查找问题  5.2 解决图的连通性问题 5.3  拓扑排序 5.4  在树结构中进行深度遍历 深度优先搜索(DFS)是一种重要的图遍历算法,用于探索图中的节点和边。 DFS 是一种递归或栈(堆栈)

    2024年02月06日
    浏览(60)
  • 数据结构与算法基础-学习-24-图的遍历之DFS(深度优先搜索)和BFS(广度优先搜索)

    目录 一、遍历定义 二、遍历实质 三、DFS 四、BFS 五、宏定义 六、自定义类型 七、函数实现 1、DFS(邻接矩阵实现) 2、DFS(邻接表实现) 3、BFS(邻接矩阵实现) 4、BFS(邻接表实现) 5、打印邻接矩阵遍历顺序  6、打印邻接表遍历顺序 八、遍历算法效率分析 1、DFS 2、BFS 九

    2024年02月03日
    浏览(72)
  • C++深度优先搜索(DFS)算法的应用:树中可以形成回文的路径数

    深度优先搜索(DFS) 状态压缩 给你一棵 树(即,一个连通、无向且无环的图),根 节点为 0 ,由编号从 0 到 n - 1 的 n 个节点组成。这棵树用一个长度为 n 、下标从 0 开始的数组 parent 表示,其中 parent[i] 为节点 i 的父节点,由于节点 0 为根节点,所以 parent[0] == -1 。 另给你一

    2024年02月04日
    浏览(40)
  • 【数据结构与算法】图遍历算法 ( 深度优先搜索 DFS | 深度优先搜索和广度优先搜索 | 深度优先搜索基本思想 | 深度优先搜索算法步骤 | 深度优先搜索理论示例 )

    图 的 遍历 就是 对 图 中的 结点 进行遍历 , 遍历 结点 有如下两种策略 : 深度优先搜索 DFS 广度优先搜索 BFS \\\" 深度优先搜索 \\\" 英文名称是 Depth First Search , 简称 DFS ; DFS 基本思想 : 访问第一个邻接结点 : 从 起始点 出发 , 该 起始点 可能有 若干 邻接结点 , 访问 第一个 邻接结点

    2024年02月02日
    浏览(45)
  • c++深度优先搜索DFS

    目录 介绍 实现过程 模板 例题详解 1.枚举排列 2.迷宫寻路 3.八皇后 剪枝与优化 作业 今天我们来学习一个极其重要的算法:深度优先搜索。 深度优先搜索,又叫DFS,是遍历图或者数的一种算法,本质就是递归。具体方法:先以一个节点为起点,向一个方向扩展,再以新的节

    2024年01月16日
    浏览(41)
  • 深度优先搜索(DFS)算法

    目录 算法思想 时间复杂度和空间复杂度 算法实现 算法优缺点 应用领域 深度优先搜索(DFS)算法的思想是从图的某个起始顶点开始,沿着一条路径尽可能深入地访问图中的所有顶点,直到不能继续为止,然后返回并探索其他路径。具体而言,DFS算法使用栈数据结构来实现,

    2024年02月05日
    浏览(45)
  • 深度优先搜索(DFS)(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法,总是以“深度”作为前进的。实现方式是有很多,最

    2024年02月08日
    浏览(48)
  • C++ 更多的DFS深度优先搜索...

    目录 DFS模版 剪枝 DFS的两种状态 使用全局变量存储 使用函数参数存储传递 众所周知,DFS是一种省督有限搜索,可以想象成一棵树根节点K开始递归到最深层的节点,通常用来枚举符合题目的所有可能情况或者个数。 话说,这个代码和全排列有什么不同吗哈哈哈哈哈 剪枝时

    2024年02月13日
    浏览(66)
  • [算法日志]图论: 深度优先搜索(DFS)

    ​ 深度优先搜索算法是一种遍历图这种数据结构的算法策略,其中心思想是朝图节点的一个方向不断跳转,当该节点无下一个节点或所有方向都遍历完时,便回溯朝上一个节点的另一个方向继续遍历。这种搜索策略与回溯法有异曲同工之妙。 正因为和回溯法有相似之处,所

    2024年02月03日
    浏览(62)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包