BFS与DFS

2018-01-30 14:11:07


_~~1;应用方面

_ __ _ ——————bfs宽度搜索用于寻找最优解;

———

— —— dfs深度![]()搜索用于遍历寻找解;

2;实现原理;

——bfs;利用队列;层次来搜索的;



这里写图片描述

解释一下图片;

第一层;–A;

第二层;–BCD;

第三层;–EF;

第四层;–GH;

第4层;–I;

因为他是按层搜索,就是说只要bfs搜索到结果那么一定是最优解;;

来个题目化的;将上图CI连接,求从A到I最短路径;依旧划分层次;第三层就会搜到I;也就是说bfs最先搜到的一定是最优 解;

模板;//结合上图理解代码;

Q={起点s}; 标记s为己访问;

    while (Q非空) {

取Q队首元素u; u出队;

所有与u相邻且未被访问的点进入队列;

标记u为已访问;

```cpp
    }
////////////////////////////////////////////////////////////
whlie (队列不空) {
    u = 对队首元素;
```
首元素出队;
for (所有与 u 邻接点 v)      //  u 的上 下 左 右

          // if(v 的坐标在 row, col之内 

          //     并且 v 不是墙

          //     并且 v 未被遍历) 

v 入队

} 
1
2
3
4
5
6~~~~~~~~ \_ \_ \_ \_ \_ \_ \_ \_ \_ \_\_ \_ \_ \_ \_ \_ \_ \_ \_ \_ ~~~~~~\_

7
8
9
10
11
12
13
14
15
16
——dfs;利用运用堆栈,递归层次搜索,回溯来遍历全部;

![大](http://img.blog.csdn.net/20160808095944107)

------------

这里写图片描述

解释一下图片;

利用回溯,一条道路走到底,然后返回上一级,继续进行搜索,直到搜索完毕;

模板;//结合上图理解代码;

void DFS( Point P ){

        for(所有P的邻接点K){

                if(K未被访问){

标记K;

```cpp
                         DFS(K);
                         //有时候要清空之前的标记;
                }
        }
}
```
1
2
3
4
5
6
7
8
9
版权声明:该版权来自某大佬