算法思考 – 深度优先搜索DFS

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止,然后返回到某一个HTML文件,再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时,说明搜索已经结束。

事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.

例题一 等式ABC+DEF=GHI

描述

假设等式  ABC+DEF=GHI  成立,且 A~I 的取值范围皆为(0 ≤ N ≤ 9)。请计算等式共有有多少种不同的可能,并输出等式。

 

C++ Code

#include<iostream>
#include<Windows.h>
#include"function.h"
using namespace std;

int a[10], book[10], n = 0;//此处特别说明一下:C语言的全局变量在没有赋值以前默认为0,
						//因此这里的book数组无需全部再次赋初值0

void dfs(int step) {
	if (step == 10) {//如果是 dfs(10) 被调用的时候,就意味着前面9个数字已经被确定
		if (a[1] * 100 + a[2] * 10 + a[3] + a[4] * 100 + a[5] * 10 + a[6] == a[7] * 100 + a[8] * 10 + a[9])
		{
			n++;
			//cout <<a[1] << a[2] << a[3] << "+" << a[4] << a[5] << a[6] << "=" << a[7] << a[8] << a[9] << endl;
		}
		return;//返回之前的一步(最近调用的地方)
	}

	//按照1、2、3...n的顺序一一尝试
	for (int i = 1; i <= 9; i++) {
		//判断i是否已经用掉
		if (book[i] == 0) {
			a[step] = i;//将i填入等式
			book[i] = 1;//将book[i]设为1,表示i已经填入等式

			//等式中第step个变量已经确定,接下来进行下一轮
			dfs(step + 1);
			book[i] = 0;//将i从等式中撤回,才能进行下一次尝试
		}
	}
	return;
}

int main() {
	dfs(1);
	cout <<n / 2;//因为ABC+DEF=GHI和DEF+ABC=GHI是同一种情况

	system("pause");
	return 0;
}

 

 

例题二 迷宫最短路径

描述

假设迷宫的平面图如下所示,其中标记为 1 的为障碍物,标记为 0 的为可以通行的地方。

0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1

 

输入

n和m,代表迷宫地图的行数和列数,然后逐行输入迷宫地图,最后输入起点和终点坐标

 

输入样例

5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3

 

输出

输出1个正整数,为最短路径的值。

 

C++ Code

#include<iostream>
#include<Windows.h>
#include"function.h"
using namespace std;

int n, m, p, q, min = 99999999;
int a[51][51], book[51][51];
void dfs(int x,int y,int step) {
	int next[4][2] = {
		{0,1},//向右走
		{1,0},//向下走
		{0,-1},//向左走
		{-1,0} //向上走
	};

	int tx, ty, k;
	//判断是否到达小哈的位置
	if (x==p && y==q) {
		//更新最小值
		if(step<min){
			min = step;
		}
		return;//这里的返回很重要
	}

	//枚举四种走法
	for (k = 0; k <= 3;k++) {
		//计算下一个点的坐标
		tx = x + next[k][0];
		ty = y + next[k][1];
		//判断是否越界
		if (tx<1 || tx>n || ty<1 || ty>m) {
			continue;
		}
		//判断该点是否为障碍物或者已经在路径中
		if (a[tx][ty]==0 && book[tx][ty]==0) {
			book[tx][ty] = 1;//标记整点已经走过
			dfs(tx, ty, step + 1);
			book[tx][ty] = 0;//尝试结束,取消这个点的标记
		}
	}
	return;
	
}

int main() {
	int i, j, startx, starty;
	//读入n和m,n为行,m为列
	cin >> n >> m;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	//读入起点和终点坐标
	cin >> startx >> starty >> p >> q;

	//从起点开始搜索
	book[startx][starty] = 1;//标记起点已在路径中,防止后面重复走
	//第一个参数是起点的x坐标,第二个参数是起点的y坐标,第三个参数是初始步数为0
	dfs(startx, starty, 0);

	//输出最短步数
	cout << min;
	system("pause");
	return 0;
}

 

dfs的基本模型大概是这样子

dfs(int step) {
	判断边界
	尝试每一种可能for(i = 1; i <= n; i++)
	{
		继续下一步dfs(step + 1);
	}
	返回
}

 

评论

  1. 我什么都不会
    Macintosh Chrome
    1年前
    2019-10-10 14:22:10

    博主博主,我要开SVM算法解析。那个我不会…

    • keyboardman 博主
      Windows Chrome
      1年前
      2019-10-13 23:06:27

      俺也一样…

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇