首页 > 其他 > 详细

深度优先搜索(DFS: Depth First Search)

时间:2019-12-17 13:18:22      阅读:98      评论:0      收藏:0      [点我收藏+]

深度优先搜索是一种树的遍历方式。与此对应的是广度优先搜索

?

二叉树的优先搜索:

技术分享图片

?

如何把一个数学问题转换为树的深度优先搜索问题:

例如:各位数之和为偶数的一个10位二进制数有几个。

我们来分析一下这个问题,首先一共有10位数,然后每一位数都只有两种状态0,1

这可以看做是一个深度为10的一个二叉树,然后用树的深度优先搜索即可解决问题。

?

用C语言实现的代码结构

void DFS(int depth)

{

????if(depth==10)????????//递归出口

????{

????????//do something????????//对全部层进行操作

????????return;

????}

????for(int i=0; i<2; i++)????????//这是一个二叉树

????{

????????//do something????????//对该层进行操作

????????DFS(depth+1);????????//进入下一层

????}

}

?

完整代码

#include <iostream>

?

using namespace std;

?

int a[10]={};

int count=0;

?

void DFS(int depth)

{

????if(depth==10)

????{

????????int sum=0;

????????for(int i=0;i<10;i++) sum+=a[i];

????????if(sum%2==0)

????????{

????????????count++;

????????}

????????return;

????}

????for(int i=0;i<2;i++)

????{

????????a[depth] = i;

????????DFS(depth+1);

????}

}

?

int main()

{

????DFS(0);

????cout << count << endl;

????return 0;

}

深度优先搜索(DFS: Depth First Search)

原文:https://www.cnblogs.com/jawide/p/12053764.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!