数据结构之DFS与BFS

WHICH工作室 2020-10-05

236

广度优先搜索算法（Breadth-First-Search，缩写为 BFS），是一种利用队列实现的搜索算法。简单来说，其搜索过程和 “湖面丢进一块石头激起层层涟漪” 类似。

深度优先搜索算法（Depth-First-Search，缩写为 DFS），是一种利用递归实现的搜索算法。简单来说，其搜索过程和 “不撞南墙不回头” 类似。

BFS 的重点在于队列，而 DFS 的重点在于递归。这是它们的本质区别。

举个典型例子，如下图，灰色代表墙壁，绿色代表起点，红色代表终点，规定每次只能走一步，且只能往下或右走。求一条绿色到红色的最短路径。

对于上面的问题，BFS 和 DFS 都可以求出结果，它们的区别就是在复杂度上存在差异。我可以先告诉你，该题 BFS 是较佳算法。

BFS示意图：

DFS示意图

插一道例题，杭电OJ-1312 Red and Black

Sample Output

BFS解法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define check(x,y) (x<wx&&x>=0&&y>=0&&y<hy)
const int mod =1e7;
char room[23][23];
int dir[4][2]=
{
  {-1,0},
  {0,-1},
  {1,0},
  {0,1}
};
int wx,hy,num;
struct node
{
  int x;
  int y;
};


void BFS(int dx,int dy)
{
  num=1;
  queue<node>q;
  node start,next;
  start.x=dx;
  start.y=dy;
  q.push(start);
  while(!q.empty())
  {
    start=q.front();
    q.pop();
    for(int i=0;i<4;i++)
    {
      next.x=start.x+dir[i][0];
      next.y=start.y+dir[i][1];
      if(check(next.x,next.y)&&room[next.x][next.y]=='.')
      {
        room[next.x][next.y]=='#';
        num++;
        q.push(next);
      }
    }
  }
}


int main()
{
  int x,y,dx,dy;
  while(cin>>wx>>hy)
  {
    if(wx==0&&hy==0)
    break;
    for(y=0;y<hy;y++)
    {
      for(x=0;x<wx;x++)
      {
        cin>>room[x][y];
        if(room[x][y]=='@')
        {
          dx=x;
          dy=y;
        }
      }
    }
    num=0;
    BFS(dx,dy);
    cout<<num<<endl;
  }
    return 0;
}

DFS解法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define check(x,y) (x<wx&&x>=0&&y>=0&&y<hy)
const int mod =1e7;
char room[23][23];
int dir[4][2]=
{
  {-1,0},
  {0,-1},
  {1,0},
  {0,1}
};
int wx,hy,num;
struct node
{
  int x;
  int y;
};


void DFS(int dx,int dy)
{
  room[dx][dy]=='#';
  num++;
  for(int i=0;i<4;i++)
  {
    int newx = dir[i][0]+dx;
    int newy = dir[i][1]+dy;
    if(check(newx,newy)&&room[newx][newy]=='.')
    {
      DFS(newx,newy);
    }
  }
}


int main()
{
  int x,y,dx,dy;
  while(cin>>wx>>hy)
  {
    if(wx==0&&hy==0)
    break;
    for(y=0;y<hy;y++)
    {
      for(x=0;x<wx;x++)
      {
        cin>>room[x][y];
        if(room[x][y]=='@')
        {
          dx=x;
          dy=y;
        }
      }
    }
    num=0;
    DFS(dx,dy);
    cout<<num<<endl;
  }
    return 0;
}

可以很明确的看出，此题DFS要比BFS简单得多，所以遇到题用DFS还是BFS要根据题意判断后再作决定。

数据库

文章转载自WHICH工作室，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

数据结构之DFS与BFS

评论