MENU

两种搜索算法

April 4, 2020 • Read: 523 • 算法

今天来讲一下常见的两种算法:广度优先搜索深度优先搜索

这两种算法呢各自都有自己的特点,下面我来详细的解析一下

1.广度优先算法

广度优先算法,顾名思义,广度优先,他是在借助队列的情况下,通过不停的切换起点来对树进行搜索为了给大家解释这个问题,我找来了一棵树

8uxEq0.png

假如我们以A作为起点,以H作为终点,于是,我们把目光投降A,我们先把A加入队列中,然后我们检查与A相连的节点,发现A与B,C相连,于是我们将A从队列中移除,将B,C加入队列中

按照广度优先找起点的原则,我们现在要找一个新的起点,那我们找哪个起点合适呢?很显然,因为队列只能找到队首的那个元素,所以B理所当然的成为了新的起点,接着,我们将B弹出

再来看看有哪些是时与B相连的,于是我们找到了A,D,E,F四个点,因为A已经被搜索过一次了,所以不能将A加入队列

我们将D,E,F三个点加入队列中。然后我们再把队列的首元素拿出来,这次我们该从C开始搜索了,我们先弹出C,C下面只有一个G,于是我们把G放入队列中。

然后我们再来看,从队首取出D并且将D弹出,因为D下面已经没有节点了,所以A-->B-->D这一条线就搜索完了,我们再拿出队首的元素E并将其弹出,将其下H,I两个节点加入队列中,以此类推,当队列中的元素都为空是,就表示我们遍历了整个树,这就是广度优先算法的大致思路,

总结一下大致思路:

找到起点-->弹出起点-->找到相邻节点(未被搜索过)-->将节点加入队列中-->从队列中取出新的节点-->弹出节点……

来看看例题:NOJ P1663

这个题便是典型的广搜题,其实理论深搜也能写,但是超时的可能性应该比较大,毕竟n都取到200了

下面来看看AC代码:

#include <bits/stdc++.h>
using namespace std;
struct node{
    int x,cnt;//x用来存储起点,cnt用来存储步数
};
queue<node>q;
int location[205][205],vis[205];//vis用于标记已经搜索过的节点
int main(){
    int n,be,en;
    cin>>n>>be>>en;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            cin>>location[i][j];
        }
    }
    q.push({be,0});//将起点放入队列中
    vis[be]=1;//标记节点
    while (!q.empty()){
        int x=q.front().x;//当前的起点
        int cnt=q.front().cnt;//搜索的第cnt步,cnt-1就是经过的多少人
        q.pop();//千万不要忘了将当前起点弹出
        if (en==x) {
            cout<<cnt-1<<endl;
            break;
        }
        for (int i=1;i<=n;i++){
            if (location[x][i]&&vis[i]==0){
                vis[i]=1;
                q.push({i,cnt+1});//找打下一个节点并将其放入队列中
            }
        }
    }
    return 0;
}

2.深度优先算法

与广度优先算法不同,深度优先算法讲究的是<u>一条道走到黑</u>,并且搜索完一整条路径之后会通过回溯的方式寻找未访问过的节点,并以此进入下一条道

深搜的题一般都和递归有关系所以初学的时候看起来会比较难懂

下面我用刚刚的那棵树再解释一下:

8uxEq0.png

假如我们以A作为起点,于是,我们现在有两种选择:1.搜索B,2.搜索C。

我们定如下规则,优先搜索左边的内容。那么我们就应该搜索B,再看看B,与其连接的有三个点:A,D,E,F,因为A已经被搜索过了,我们便忽略A

按照规则,我们现在搜索D,我们发现,D已经没有路可走了,路线A-->B-->D已经走到了尽头,于是我们开始回溯,我们从B节点开始搜素E……以此类推,当我们搜到H时,又开始回溯,通过不停的执行这种过程,我们便可以将整棵树完全访问,这便是深度优先搜索的大致原理

总结一下大致思路:

从起点开始搜索-->依次寻找下一个优先节点-->到达路径末尾-->开始回溯到最近一个没有被访问的节点-->继续搜索……

我们来看一下深搜的模板吧:

void DFS(int cur)
{
    if(满足所需要的条件){
        相应的操作;
           return;
    }
    //这里对应一个递归的基,就是开始返回的地方
    else{
        for(int i= ; ;) //如果是方向的话,会枚举方向
        {
            枚举加方向的新坐标;
            if(界限 :例如:不能出到地图外,有障碍,已经访问过)
                continue;
               设置已经访问新坐标;
            DFS(新坐标); 
            恢复到未被访问;
        }
    }
}  

int main()
{
    dfs(0)//从某个起点开始搜索
} 

其实大部分的深搜都是这个样子,但是还是得学会灵活变通

例题:
洛谷P2089 烤鸡
洛谷P1219 八皇后

Archives Tip
QR Code for this page
Tipping QR Code