BFS与DFS总结

• BFS判断连通性

 if(vest[new_x][new_y]==false)
            {
                que.push(Node);
                vest[new_x][new_y]=true;
            }

• DFS判断连通性

            if(judge(nx,ny))
            {
                vest[nx][ny]=true;
                DFS(nx,ny);
            }

• BFS最优解(不走重复路径)

int BFS(int i,int j)
{
    queue<node> que;
    Node.x=i;
    Node.y=j;
    Node.step=0;
    que.push(Node);
    inque[i][j]=true;
    while(!que.empty())
    {
        node top=que.front();
        if(top.x==end_x&&top.y==end_y)
        {
            return top.step;
        }
        que.pop();
        for(int i=0; i<4; i++)
        {
            int new_x=top.x+x[i];
            int new_y=top.y+y[i];
            if(judge(new_x,new_y))
            {
                Node.x=new_x;
                Node.y=new_y;
                Node.step=top.step+1;
                que.push(Node);
                inque[Node.x][Node.y]=true;
            }

        }
    }
}

• BFS最优解(走重复路径)

int BFS(int x,int y)
{
    //(0,0)处用时判断
    n.x=x;
    n.y=y;
    n.time=6;
    n.use=0;
    que.push(n);
    //vest[x][y]=true;起点不可能是重置室,应该允许重复访问,所以这句话不要

    while(!que.empty())
    {
        now top=que.front();
        if(top.x==ed_x&&top.y==ed_y)
        {
            if(top.time>0)//逃生成功
            {
                flag=true;
                que.pop();
                return top.use;
            }
        }
        que.pop();

        for(int i=0; i<4; i++)
        {
            int nx=top.x+go[i][0];
            int ny=top.y+go[i][1];
            n.x=nx;
            n.y=ny;
            n.use=top.use+1;
            n.time=top.time-1;//如果走该方向会导致剩余时间用尽,则不能走该方向

            if(vest[nx][ny]==false)
            {
                if(G[nx][ny]==4)//是重置室,出了门就不许再重复访问这里
                {
                    n.time=6;
                    vest[nx][ny]=true;
                }
              
                 //vest[x][y]=true;不是重置室,应该允许重复访问,所以这句话不要
                que.push(n);
            }
        }
    }
}

• DFS回溯(不走重复路径)

void DFS(int x)
{
    if(x==N)
    {
        return;
    }
    for(int i=1; i<N; i++)
    {
        if(vest[i]==false)
        {
            a[x]=i+1;
            vest[i]=true;
            DFS(x+1);
            vest[i]=false;
        }
    }
}
/*输入:6
8
输出:
1 4 3 2 5 6
1 6 5 2 3 4

1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2*/

• DFS回溯(走重复路径)

void DFS(int x)
{
    if(x==N)
    {
        return;
    }
    for(int i=1; i<N; i++)
    {
            a[x]=i+1;
            DFS(x+1);
    }
}
/*输入:6
8
输出:
1 2 3 2 3 2
1 2 3 2 3 4
1 2 3 2 5 2
1 2 3 2 5 6
1 2 3 4 3 2

1 2 3 2 3 2 3 2
1 2 3 2 3 2 3 4
1 2 3 2 3 2 5 2
1 2 3 2 3 2 5 6
1 2 3 2 3 4 3 2
1 2 3 2 3 4 3 4
1 2 3 2 3 4 7 4*/