BFS与DFS的总结

今天来总结一下BFS与DFS

首先有一种说法，就是DFS找连同块，BFS找最小路；

因为DFS的搜索路径：就如下面这个图来说吧，从a到x，'—'表示障碍物

如果是dfs，那么就是 运行路径就是（1，0），（-1，0），（0，1），（0，-1）就是它的路径变化，就会是下面的图，先从a的右边行走，然后如果右边不行就左边，左边不行就上边，上边再不行就下边。要是没路走了，就往回走,这个称为回溯。

 

这个的代码一般会是：

 

       

int n,m,x,y,sum;
char a[25][25];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}，vis[25][25];
void dfs(int x,int y)
{
    int xx,yy;
    sum++;
    vis[x][y]=1;
    if(a[x][y]=='x')
       return;
    for(int i=0;i<4;i++)
    {
        xx=x+dir[i][0];
        yy=y+dir[i][1];
        if(a[xx][yy]!='-'&&xx>=0&&xx<m&&yy>=0&&yy<n&&!vis[xx][yy])
            dfs(xx,yy);
    }
}

 

当然也有其他的搜索方式，就dfs，一般要知道搜索路径——就是像上面的向上，向左，向右，向下的路径，能否继续前行的判断条件——上面的判断条件是它是否是阻碍，以及循环标志——上面的循环标志是x与y的坐标，有的也是它的数量。有的会有结束标志——到达x。它的作用可以寻找连同块，也可以找到全部搜索路径，但是缺点是时间。

 

然后是bfs，也是上面的那个如果是bfs，它的搜索路径就会是这样子：

由a开始每次往它的搜索路径搜索，所以它的每个地方都会搜到 ，这个代码一般是：

struct node
{
    int x,y,ki;
};
node start,nextt;
int n,m,T,k,a1,b1,a2,b2;
int vis[105][105],dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
char Map[105][105];
bool cmp(int xx,int yy)
{
    if(xx>0&&xx<=n&&yy>0&&yy<=m&&Map[xx][yy]!='-')
        return true;
    else
        return false;
}
void bfs()
{
    queue<node>q;
    vis[a1][b1]=1;
    start.x=a1;
    start.y=b1;
    start.ki=-1;
    q.push(start);
    while(!q.empty())
    {
        start=q.front();
        q.pop();
        if(start.x==a2&&start.y==b2&&start.ki<=k)
        {
            cout<<"yes"<<endl;
            return ;
        }
        start.ki+=1;
        for(int i=0;i<4;i++)
        {
            nextt=start;
            nextt.x=start.x+dir[i][0];
            nextt.y=start.y+dir[i][1];
            while(cmp(nextt.x,nextt.y))
            {
                if(!vis[nextt.x][nextt.y])
                {
                    vis[nextt.x][nextt.y]=1;
                    q.push(nextt);
                }
            }
        }
    }
    cout<<"no"<<endl;
}

 就bfs，一般就是这种模板，一般求最短路，缺点是空间。