C语言递归+DFS(深度优先搜索算法)详解 图文并茂,手把手教你画树状图

这篇具有很好参考价值的文章主要介绍了C语言递归+DFS(深度优先搜索算法)详解 图文并茂,手把手教你画树状图。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一.标准定义

二.跳台阶(典型递归题目)

三.递归实现指数型枚举

四.递归实现排列型枚举

五.递归实现组合型枚举

六.DFS算法模板


一.标准定义

深度优先搜索算法(Depth First Search,简称DFS):一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

 深度优先遍历树怎么画,c语言,深度优先,开发语言,dfs,算法

说人话,其实就是沿着一条路一直搜索,知道条件不符合,就回头走到分岔口,选择另一条路继续搜索,俗称:“不撞南墙不回头”搜索。

这种一直进行下去又返回的操作是不是很像递归,dfs名字听起来高大上,其实本质就是递归。那我们就先从一道典型的递归题开始说起吧。

二.跳台阶(典型递归题目)

上楼梯的同学,每次可以走一个台阶,也可以走两个台阶,现在有N个台阶,请问有多少种不同的方法?(先爬1阶再爬2阶和先爬2阶再爬1阶是不同的方法)

我们可以自己在草稿纸上算算,看看有什么规律。

N=1,1种;

N=2,1+1/2   2种

N=3 1+1+1/1+2/2+1   3种

N=4 1+1+1+1/2+2/1+2+1/2+1+1/1+1+2   5种

...... 

很显然,其实你会发现答案成斐波那契数列(当然,本题答案是从斐波拉契数列第二项开始的)。这就把题目转换成我们熟悉的问题了。

对于斐波那契数列,我们可以引用一种”递归搜索树“的方法,来让整个过程更加直观。 深度优先遍历树怎么画,c语言,深度优先,开发语言,dfs,算法

我们先沿着左边①这条路一直往下算,直到遇到了f(2)(因为我们知道f(1),f(2)的值),然后撞到了”南墙“,我们就开始回溯,算f(1),两者累加算出f(3)的值,接着回溯算f(2)的值...... 

这个过程其实就体现了什么加”深度搜索“,什么叫”回溯“。

我们简单看一下这道题的代码。

#include<stdio.h>
int fun1(int n)
{
	if (n == 1)
		return 1;
	else if (n == 2)
		return 2;
	else
		return fun1(n - 1) + fun1(n - 2);
}

深度优先遍历树怎么画,c语言,深度优先,开发语言,dfs,算法

什么?觉得简单?我们开始上强度了。 

再讲下面题之前,我先给出dfs算法基本套路。

三.DFS算法模板

1.创建一个数组,存储状态和结果。

2.函数内部

①判断是否撞了南墙

②执行赋值,改状态的操作

③再次调用函数

④恢复现场

四.递归实现指数型枚举

我们先看看这道题。可以尝试运用树形图的方法找找思路。

深度优先遍历树怎么画,c语言,深度优先,开发语言,dfs,算法

通过判断一个数选不选的思路,我们可以画出树状图。

这是我没画完的树状图,你看,这样就能找到2个答案了。 

深度优先遍历树怎么画,c语言,深度优先,开发语言,dfs,算法

我们把图补全,8个答案就已经全部找到了。 

深度优先遍历树怎么画,c语言,深度优先,开发语言,dfs,算法 接着,我们进行代码实现,注意看我的注释>

如何让程序知道一个数选没选呢?那就需要使用一个状态数组,存储一个数的状态,是选了还是没选还是还没考虑到。

#include <stdio.h>
int n;
int st[20] = { 0 };//记录每个数的状态,0代表还没考虑,1代表选了,2代表没选
void dfs(int x)//x表示当前枚举到了哪个位置
{
	//判断是不是撞了"南墙"了
	if (x > n)
	{
		for (int i = 1; i <= n; i++)
		{
			if (st[i] == 1)
			{
				printf("%d ", i);
			}
		}
		printf("\n");
		return;
	}

	//选
	st[x] = 1;
	dfs(x + 1);
	st[x] = 0;//恢复现场(下面有解释)

	//回溯以后,就该不选了
	st[x] = 2;
	dfs(x + 1);
	st[x] = 0;
}

int main()
{
	scanf("%d", &n);
	dfs(1);//把位置1传过去
	return 0;
}

代码配合树状图更好理解,一定要切记,当一条路走不通的时候才会发生回溯!!!

为什么要恢复现场?其实就是为了恢复到上一个分岔口的状态,把数字标记为还没有考虑。这个操作可以让回溯的过程更加清晰。

看到这里,不知道你的精神状态是怎样的?如果你感到->

深度优先遍历树怎么画,c语言,深度优先,开发语言,dfs,算法

不要慌张,熟能生巧~

五.递归实现排列型枚举

同样的,上例题

深度优先遍历树怎么画,c语言,深度优先,开发语言,dfs,算法

当n=3时,由高中学的排列组合知识,那么就有A3 3=3*2*1=6种排列方式,符合输出结果。

我们可以根据依次枚举一个位置上选哪个数的思路,来画个树状图,试试呢?

深度优先遍历树怎么画,c语言,深度优先,开发语言,dfs,算法

我们一起来看看代码如何实现的

#include <stdio.h>
#include <stdbool.h>

int n = 0;
bool st[10];//因为一个数只能出现一次,所以用一个状态数组存一下一个数是否已经被选。
//true表示选过,false表示未被选。
int arr[10] = { 0 };//存的是答案,例如123/321/312

//x表示枚举到的位置
void dfs(int x)
{
	if (x>n)
	{
		for (int i = 1; i <= n; i++)
		{
			printf("%d", arr[i]);
		}
		printf("\n");
		return;
	}
	
	for (int i = 1; i <= n; i++)
	{
		if (!st[i])//如果st[i]是false
		{
			st[i] = true;
			arr[x] = i;
			dfs(x + 1);
			//恢复现场
			st[i] = false;
			arr[x] = 0;
		}
	}
}
int main()
{
	scanf("%d", &n);
	dfs(1);
	return 0;
}

大家可以运用编译器的调试功能,一步步看怎么运行的。或者自己口述整个过程的逻辑,来加深自己的理解。 

(对了,如果题目要ac的话,注意在输出的时候使用%5d就能保留5个场宽啦~)

六.递归实现组合型枚举

加油,最后一个类型了!

                                                    深度优先遍历树怎么画,c语言,深度优先,开发语言,dfs,算法

我们来看题。

深度优先遍历树怎么画,c语言,深度优先,开发语言,dfs,算法

深度优先遍历树怎么画,c语言,深度优先,开发语言,dfs,算法

 当n=5,r=3时,由高中学的排列组合知识,不考虑顺序,那么就有C5 3=C5 2=10种排列方式,符合输出结果。

我们可以发现,每一行的数是递增的,我们也可以通过枚举一个位置上选什么数的思路来画出树状图,自己试试吧!

深度优先遍历树怎么画,c语言,深度优先,开发语言,dfs,算法

当一条路没有结果的时候,我们把这种舍弃它的行为称作”剪枝“

对于代码的实现,我们运用:

int x;记录当前枚举到了哪个位置

int arr[x];记录都选了哪些数(记答案)

int start;(记录下个位置从几开始枚举)

#include <stdio.h>
int n, r;
int arr[21];

void dfs(int x,int start)
{
	if (x > r)
	{
		for (int i = 1; i <= r; i++)
		{
			printf("%3d", arr[i]);
		}
		printf("\n");
		return;
	}

	for (int i = start; i <= n; i++)
	{
		arr[x] = i;
		dfs(x + 1, i + 1);
		arr[x] = 0;//恢复
	}
}

int main()
{
	scanf("%d %d", &n, &r);
	dfs(1,1);
	return 0;
}

 恭喜,你完成了DFS算法的学习!

深度优先遍历树怎么画,c语言,深度优先,开发语言,dfs,算法

接下来就是刷题啦,在我的下一篇文章里,我们一起来刷题~ 

已更新:C语言dfs深度优先练习 N皇后 图文并茂超详解 !

              DFS练习-迷宫(最短路径)问题详解 一波三折 图片+文字文章来源地址https://www.toymoban.com/news/detail-765619.html

到了这里,关于C语言递归+DFS(深度优先搜索算法)详解 图文并茂,手把手教你画树状图的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • DFS (深度优先搜索) 算法详解 + 模板 + 例题,这一篇就够了

    深度优先搜索算法 (Depth First Search,简称DFS):一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所

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

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

    2024年02月02日
    浏览(48)
  • 深度优先搜索(DFS)算法

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

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

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

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

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

    2024年02月03日
    浏览(63)
  • 第一周算法训练(dfs)(深度优先搜索算法)

    dfs: 深度优先搜索算法 ,是一种用于遍历或 搜索树或图的算法 .沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被

    2024年02月20日
    浏览(51)
  • Python 算法基础篇:深度优先搜索( DFS )和广度优先搜索( BFS )

    深度优先搜索( DFS )和广度优先搜索( BFS )是两种常用的图遍历算法,用于在图中搜索目标节点或遍历图的所有节点。本篇博客将介绍 DFS 和 BFS 算法的基本概念,并通过实例代码演示它们的应用。 😃😄 ❤️ ❤️ ❤️ 深度优先搜索( DFS )是一种用于遍历或搜索图或树

    2024年02月07日
    浏览(67)
  • 深度优先搜索(DFS)和广度优先搜索(BFS)两种算法c++

    深度优先搜索(DFS)和广度优先搜索(BFS)是一种用于遍历或搜索树图的一种算法,在这个过程中保证图或数的每个结点被访问且仅被访问一次,再按照每个结点访问的顺序不同分为深搜和广搜。 本文只讨论这两种算法在搜索方面的应用! 深度优先搜索 ( Depth-First-Search,DFS )它 沿

    2024年02月13日
    浏览(50)
  • 图的遍历(搜索)算法(深度优先算法DFS和广度优先算法BFS)

    从图的某个顶点出发访问遍图中所有顶点,且每个顶点仅被访问一次。(连通图与非连通图) 1、访问指定的起始顶点; 2、若当前访问的顶点的邻接顶点有未被访问的,则任选一个访问之;反之,退回到最近访问过的顶点;直到与起始顶点相通的全部顶点都访问完毕; 3、若

    2024年01月17日
    浏览(48)
  • 【数据结构与算法】搜索算法(深度优先搜索 DFS和广度优先搜索 BFS)以及典型算法例题

    【数据结构与算法】系列文章链接: 【数据结构与算法】递推法和递归法解题(递归递推算法典型例题) 【数据结构与算法】系列文章链接: 【数据结构与算法】C++的STL模板(迭代器iterator、容器vector、队列queue、集合set、映射map)以及算法例题 【数据结构与算法】系列文章链

    2024年04月13日
    浏览(78)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包