解释:
广度优先算法(Breadth-First-Search),简称BFS。从知识点看属于图结构的搜索算法,是一种相对容易理解的简单算法。
BFS算法从问题的初始状态(起点)出发,根据状态转换规则(图结构中的边),遍历所有可能的状态(其他节点),直到找到终结状态(终点)。因此BFS算法的复杂度和状态集合的总数密切相关。
BFS算法虽然出自图结构,但其常用的领域却不是解决图论相关问题。一些常见的问题形式如(1)走迷宫最短路径(2)数字按规则转换的最少次数(3)棋盘上某个棋子N步后能到达的位置总数(4)病毒扩散计算(5)图像中连通块的计算。小结:BFS算法常用于求最短的步数或者求扩散性质的区域问题。参考
深度优先搜索算法(Depth First Search,简称DFS):一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。
个人理解:
bfs和dfs都是用来查找的算法
bfs类似于在一个点倒一桶水,水就会向着四面八方流,在向着四面八方流的时候,总有水会碰到要找到东西。这个就相当于bfs,所以也就称为广度优先搜索。
而dfs类似与在一个岔路口,面前有很多条路一条路一条路的走,每次都一条路走到黑走到不能走为止,才会回头;可以理解为不撞南墙绝不回头。
看题理解算法
bfs板子题
# 入门
## 题目描述
不是任何人都可以进入桃花岛的,黄药师最讨厌像郭靖一样呆头呆脑的人。所以,他在桃花岛的唯一入口处修了一条小路,这条小路全部用正方形瓷砖铺设而成。有的瓷砖可以踩,我们认为是安全的,而有的瓷砖一踩上去就会有喷出要命的毒气,那你就死翘翘了,我们认为是不安全的。你只能从一块安全的瓷砖上走到与他相邻的四块瓷砖中的任何一个上,但它也必须是安全的才行。
由于你是黄蓉的朋友,她事先告诉你哪些砖是安全的、哪些砖是不安全的,并且她会指引你飞到第一块砖上(第一块砖可能在任意安全位置),现在她告诉你进入桃花岛的秘密就是:如果你能走过最多的瓷砖并且没有死,那么桃花岛的大门就会自动打开了,你就可以从当前位置直接飞进大门了。
注意:瓷砖可以重复走过,但不能重复计数。
## 输入格式
第一行两个正整数 $W$ 和 $H$,分别表示小路的宽度和长度。
以下 $H$ 行为一个 $H\times W$ 的字符矩阵。每一个字符代表一块瓷砖。其中,`.` 代表安全的砖,`#` 代表不安全的砖,`@` 代表第一块砖。
## 输出格式
输出一行,只包括一个数,即你从第一块砖开始所能安全走过的最多的砖块个数(包括第一块砖)。
## 样例 #1
### 样例输入 #1
```
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
```
### 样例输出 #1
```
59
```
## 提示
#### 数据规模与约定
对于全部的测试点,保证 $1 \leq W,H\le 20$。
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<stack>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<cstring>
#include<queue>
#include<set>
#include<stdlib.h>
#define dbug cout<<"hear!"<<endl;
#define rep(a,b) for(int i=a;i<=b;i++)
#define rrep(a,b) for(int j=a;j<=b;j++)
#define per(a,b) for(int i=a;i>=b;i--)
#define pper(a,b) for(int j=a;j>=b;j--)
#define no cout<<"NO"<<endl;
#define yes cout<<"YES"<<endl;
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 2e5 + 100;
const int INF = 0x3f3f3f3f;
ll gcdd(ll a, ll b)
{
if (b) while ((a %= b) && (b %= a));
return a + b;
}
ll t,n, m, a, b, c, cnt, ans, ant,sum, q, p,idx;
ll arr[N];
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,-1,0, 1};
char mp[150][150];//存图
int sx, sy;//存开始的位置
struct node
{
int x, y;
};
void bfs()
{
queue<node>q;
node A;
A.x = sx, A.y = sy;
q.push(A);
while (!q.empty())
{
node B;
B = q.front();
q.pop();
for (int i = 0;i < 4;i++)
{
int tx = B.x + dx[i], ty = B.y + dy[i];
if (mp[tx][ty] == '.' && tx >= 1 && tx <= n && ty >= 1 && ty <= m)//上下左右四个点开始走
{
mp[tx][ty] = '#';
node C;
C.x = tx;
C.y = ty;
sum++;
q.push(C);
}
}
}
}
int main()
{
cin >> m >> n;//注意题目输入的顺序
rep(1, n)//存入图像
{
rrep(1, m)
{
cin >> mp[i][j];
if (mp[i][j] == '@')//将开始的点记录下来
{
sx = i, sy = j;
}
}
}
sum = 1;//因为最开始的点也算一个砖头,所以sum从1开始记
bfs();
cout << sum;
}
dfs板子题
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<map>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<stdlib.h>
using namespace std;
typedef long long ll;
//const int N = 1e6 + 5;
//bool flag[N], arr[N];
int nx[] = { -1,0,1,0,-1,-1,1,1 };
int ny[] = { 0,-1,0,1,-1,1,1,-1 };
//int a[N], b[N], c[N];
int n, m, k;
int sum = 999999, sum2 = 0;
struct food
{
ll a, b;
}food[20];
void dfs(int k, int x, int y)
{
if (k > n)
{
if (x == 1 && y == 0) return;
sum = min(sum, abs(x - y));
return;
}
dfs(k + 1, x * food[k].a, y + food[k].b);
dfs(k + 1, x, y);
}
int main()
{
cin >> n;
for (int i = 1;i <= n;i++)
{
cin >> food[i].a >> food[i].b;
}
dfs(1, 1, 0);
cout << sum;
}