深度优先dfs与广度bfs优先搜索总结+例题

DFS（Deep First Search）深度优先搜索

深度优先遍历（dfs）是对一个连通图进行遍历的算法。它的思想是从一个顶点开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。

简而言之：不撞南墙不回头

模板如下：

void dfs(int t)//t代表目前dfs的深度

{

    if(满足输出条件||走不下去了)

    {

        输出解;

        return;

    }

    else

    {

        for(int i=1;i<=尝试方法数;i++)

            if(满足进一步搜索条件)

            {

                为进一步搜索所需要的状态打上标记;

                dfs(t+1);

                恢复到打标记前的状态;//也就是说的{回溯一步}

            }

    }

}

例题一：洛谷P1219八皇后

#include<bits/stdc++.h>

using namespace std;

int a[14],b[14],c[29],d[29];//分别存横、列、左对角线、右对角线访问标记

int n;

int cnt=0;

void print()

{

	cnt++;

	if(cnt<=3)

	{

		for(int i=1;i<=n;i++)

			cout<<a[i]<<" ";

		cout<<endl;

	}

}

void dfs(int k)

{

	int i=k;

	for(int j=1;j<=n;j++)

	{

		if(b[j]==0&&c[i+j]==0&&d[i-j+n]==0)//满足未被访问

		{

			a[i]=j;

			b[j]=1;c[i+j]=1;d[i-j+n]=1;//分别在竖排，左对角线，右对角线打上标记

			if(k<n)

				dfs(k+1);	//放置下一横排的皇后

			else if(k==n)

				print();

			b[j]=0;c[i+j]=0;d[i-j+n]=0;//回溯，标记重新置为0

		}

	}

}

int main()

{

	cin>>n;

	dfs(1);

	cout<<cnt;

	return 0;

}

例题二：牛客网小雨的矩阵

#include<bits/stdc++.h>

using namespace std;

long long a[52][52];

int n;

set<int> s;	//set集合中数据唯一且有序

void dfs(int x,int y,int sum){

    if(x==n && y==n){

        s.insert(sum);	//走到（n,n）则把sum插入集合s

        return;

    }

    if(x+1<=n){

        dfs(x+1,y,sum+a[x+1][y]);//向下走

    }

    if(y+1<=n){

        dfs(x,y+1,sum+a[x][y+1]);//向右走

    }

}

int main() {

    cin>>n;

    for(int i=1;i<=n;i++){

        for(int j=1;j<=n;j++){

            cin>>a[i][j];	//录入矩阵

        }

    }

    dfs(1,1,a[1][1]);	//开始深搜

    cout<<s.size()<<endl;//输出集合s的大小

    return 0;

}

BFS（Breath First Search）广度优先搜索

广度优先搜索较之深度优先搜索之不同在于，深度优先搜索旨在不管有多少条岔路，先一条路走到底，不成功就返回上一个路口然后就选择下一条岔路，而广度优先搜索旨在面临一个路口时，把所有的岔路口都记下来，然后选择其中一个进入，然后将它的分路情况记录下来，然后再返回来进入另外一个岔路，并重复这样的操作。

简而言之：地毯式搜索或者说像水波纹一样四散开来

模板如下：

//通常用队列queue实现，或者有些时候用数组模拟队列

void bfs()

{

    初始化队列q

    q.push(起点)；

	标记上起点；

    while(!q.empty())

    {

		取队首元素u；

         q.pop();//队首元素出队

         for(int i=0;i<可以走的方向数;i++)

         {

             if(下一步满足边界内，未访问等条件)

             {

                 q.push();//该点入队

                 标记上该点；

                 ...

             }

         }

    }

}

例题一：洛谷P1443马的遍历

此题要求马从某点到达某点的最少要走几步，优先用bfs

#include<bits/stdc++.h>

using namespace std;

int h[8]={-2,-1,1,2,-2,-1,1,2},z[8]={1,2,2,1,-1,-2,-2,-1};//8个方向

int vis[410][410];

int cnt[410][410];//记录到达每个坐标点的步数

queue<pair<int,int> >q;

int n,m;

void bfs()

{

    while(!q.empty())

    {

        int x=q.front().first;

	    int y=q.front().second;

	    q.pop();

    	for(int i=0;i<8;i++)

    	{

		    int xx=x+h[i];

	    	int yy=y+z[i];

		    if(xx>n||xx<1||yy>m||yy<1||vis[xx][yy]==1)continue;//到达边界或已经访问则跳过此次循环

		    q.push(make_pair(xx,yy));

		    vis[xx][yy]=1;

		    cnt[xx][yy]=cnt[x][y]+1;

    	}

    }

}

int main()

{

	memset(cnt,-1,sizeof(cnt));

	int x,y;

	cin>>n>>m>>x>>y;

	vis[x][y]=1;

	cnt[x][y]=0;

	q.push(make_pair(x,y));

	bfs();

	for(int i=1;i<=n;i++)

	{

		for(int j=1;j<=m;j++)

		{

			printf("%-5d",cnt[i][j]);//控制格式

		}

		cout<<endl;

	}

	return 0;

}

例题二：洛谷P1162填涂颜色

此题的关键是通过广搜把 1 外围的 0 打上标记

#include<bits/stdc++.h>

using namespace std;

int h[4]={-1,0,1,0},z[4]={0,-1,0,1};

int n,a[35][35];

queue<pair<int,int> >q;

int main()

{

	cin>>n;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=n;j++)

			cin>>a[i][j];

	for(int i=0;i<=n+1;i++)//在四周加0,避免在角落的0搜不过去

	{

		a[0][i]=0;

		a[n+1][i]=0;

		a[i][0]=0;

		a[n+1][i]=0;

	}

	q.push(make_pair(0,0));

	while(!q.empty())

	{

		int x=q.front().first;

		int y=q.front().second;

		q.pop();

		for(int i=0;i<4;i++)

		{

			int x2=x+h[i];

			int y2=y+z[i];

			if(x2>=0&&y2>=0&&x2<=n+1&&y2<=n+1&&a[x2][y2]==0)

			{

				a[x2][y2]=-1;//1外围的0标志为-1

				q.push(make_pair(x2,y2));

			}

		}

	}

	for(int i=1;i<=n;i++)

	{

		for(int j=1;j<=n;j++)

		{

			if(a[i][j]==-1)cout<<"0 ";

			else if(a[i][j]==1)cout<<"1 ";

			else if(a[i][j]==0)cout<<"2 ";

		}

		cout<<endl;

	}

	return 0;

}

综上，其实很多题dfs和bfs都可以解，但是在最短（优）路径问题上最好用广度优先bfs

巴特西

深度优先dfs与广度bfs优先搜索总结+例题

DFS（Deep First Search）深度优先搜索

例题一：洛谷P1219八皇后

例题二：牛客网小雨的矩阵

BFS（Breath First Search）广度优先搜索

例题一：洛谷P1443马的遍历

例题二：洛谷P1162填涂颜色

最新文章

热门文章