【算法笔记】搜索基础

前言

写这篇文章的时候我甚至不会最短路，所以别骂了

1 深度优先搜索

深度优先搜索一种搜索算法，英文缩写为$DFS$，即Depth First Search其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。「1」

简单来说，深搜就是“一条路走到黑”。

1.1 深度优先搜索的顺序

(手绘图片，有点简陋请不要介意）

步骤：

1. 首先找到初始节点1。

2. 依此从1未被访问的邻接点出发，对图进行深度优先遍历。

3. 若有节点未被访问，则回溯到该节点，继续进行深度优先遍历。

4. 直到所有与顶点1路径相通的节点都被访问过一次。

1.2 DFS模板

void dfs(int v){
    if(/*到达目标位置*/) return;
    for(/*枚举所有可能性*/){
        if(/*符合条件*/){
            //标记
            dfs(/*下一个位置*/);
        }
    }
}

1.3 例题

洛谷P1706

全排列问题

解法：

1. next_permutation函数（stl字典序全排列函数）

2. 暴力枚举

3. DFS搜索

解法1

//代码来自@shajjl大佬
#include <bits/stdc++.h>
using namespace std;
int a[10];
int main()
{
	int n,i,j=1,k;
	cin>>n;
	for(i=1;i<=n;i++)
	 {a[i]=n-i+1;j*=i;}//题目好像没说要从小到大输出
     //但保险起见还是初始赋值为最大序列
     //即a[1~n]=n~1;顺便计算n!
	for(i=1;i<=j;i++)
	 {next_permutation(a+1,a+n+1);
	  for(k=1;k<=n;k++)
	   cout<<"    "<<a[k];//排一次输出一次
       //空格建议复制
	  cout<<endl;
	 }
	 return 0;
}

解法2

暴力枚举就需要循环n次，而题目中n限定在9以内，这就需要写9个循环，但是那太多啦，所以作者就写了3个循环，代码如下：

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
    cin>>n;
    for(int a=1;a<=n;a++){
    	for(int b=1;b<=n;b++){
    		for(int c=1;c<=n;c++){
    			if(a!=b&&b!=c&&a!=c) printf("%5d%5d%5d\n",a,b,c);
    		}
    	}
    }    			
    return 0;
}

解法3

#include<bits/stdc++.h>
using namespace std;
int n,vis[100],a[100];
void print(){//输出函数
    int i;
    for(i=1;i<=n;i++)
    printf("%5d",a[i]);
    cout<<endl;
}
void dfs(int k){
	//k代表搜索到了第k格
    if(k==n){
		//填满了的时候
        print();//输出
        return;
    }
    for(int i=1;i<=n;i++){//1-n循环填数
        if(!vis[i]){
			//如果当前数没有用过
            vis[i]=1;//那么就标记
            a[k+1]=i;//加入数组
            dfs(k+1);//搜索下一个
            vis[i]=0;//回溯
        }
    }
}
int main(){
    cin>>n;
    dfs(0);//开始搜索
    return 0;
}

时间复杂度

解法1

通过bdfs，我们知道，next_permutation函数的时间复杂度是$O(n)$ ，再观察程序，程序内有两重循环，所以，这个程序的时间复杂度是$O(n^3)$

解法2

暴力枚举n重循环，很明显，时间复杂度为$O(n^n)$

解法3

n个不相同的数字的全排列有$n!$个，在递归的过程中，这个时间复杂度大概在$O(n \times n!)$和$O(n!)$之间。

分析

所以，dfs的解法明显比暴力枚举更优。

2 广度优先搜索

广度优先搜索（Breadth First Search）简称广搜、宽搜或者 BFS。

如果说深搜是“一条路走到黑”，那么广搜就是一层一层地搜索。

那么如何实现这个过程呢？我们就需要用一个数据结构——队列。

广搜的搜索顺序

1. 首先找到初始节点1，把它加入队列。

2. 取出队首，依此访问该节点未访问过的的邻接点，把他们加入队列。

3. 重复执行步骤2，直到队列为空。

广搜模板代码

bool bfs(int v/*开始节点*/){
    queue<int>q;//队列
    q.push(v);//把开始节点加入队列
    while(!q.empty()){
        //BFS是用循环实现的
        int t=q.front();//取队首
        if(/*达到目标条件*/) return true;
        q.pop();//队首出队
        for(/*枚举可能性*/){
            if(/*符合条件*/) q.push(/*该元素*/);
        }
    }
    return false;//没有搜索到
}

例题

U263917 抓住拿头牛

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PLL;//first代表位置，second代表步数
const int N=100005;
int n,k;
int vis[N]={0};//是否访问过
int bfs(){
	queue<PLL>q;//队列
	q.push({n,0});//加入队首
	vis[n]=1;
	while(!q.empty()){
		PLL head=q.front();//取出队首
		q.pop();//队首出队
		int f=head.first,s=head.second;
		if(f==k) return s; //达到目标就结束
        if(f+1<N&&vis[f+1]==0){//从x移动到x+1
		    vis[f+1]=1;
            q.push({f+1,s+1});
        }
        if(f*2<N&&vis[f*2]==0){//从x移动到x*2
            vis[f*2]=1;
            q.push({f*2,s+1});
        }
        if(f-1>=0&&vis[f-1]==0){//从x移动到x-1
            vis[f-1]=1;
            q.push({f-1,s+1});
        }
	}
	return 0;
}
int main(){
	cin>>n>>k;
	cout<<bfs();//开始搜索
}

3 搜索之连通性

$Floodfill$又名泛洪填充算法，类似于画图的油漆桶工具一样，我们把所有起点能走到的格子全部拿一个颜色标记一下，然后如果终点没有被标记就说明不能联通。

因为所有能走到的点都需要遍历一遍，并且不重复走同一个点，时间复杂度为
$O(\text{格子个数})$ 的。

可以$BFS$也可以$DFS$搜实现，$BFS$可以顺便求出来最短距离，$DFS$又省空间又好写，如果不求距离一般拿$DFS$实现。

例题#1

POJ 1818 红与黑

代码

#include<bits/stdc++.h>
using namespace std;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};//四个方向的数值，为了方便用两个数组存
char a[110][110];
int n,m,cnt=0;
void dfs(int x,int y){//dfs搜索
   for(int i=0;i<4;i++){
   	int xx=dx[i]+x,yy=dy[i]+y;
   	if(a[x][y]!='#'&&x>=1&&y>=1&&x<=n&&y<=m){
    	    cnt++;
            a[xx][yy]='#';//
            dfs(xx,yy);
    	}
   }
}
int main(){
	cin>>m>>n;
	int xx,yy;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='@') xx=i,yy=j;
		}
	}
	dfs(xx,yy);
	cout<<cnt;
	return 0;
}