一般検索のBFS

前編ではDFSアルゴリズムについて述べたが,南の壁にぶつからず振り向かないのが特徴であり,これとは逆の広さ優先探索(BFS)について述べた.イメージ的に言えば、広捜はルートノードV 0から、その未アクセスのサブノードW 1,W 2を巡る…次に、そのサブノードからW 1未アクセスのサブノードを遍歴し、W 2未アクセスのサブノードを遍歴し、このようにして広検索遍歴を完了する.したがって,広探索アルゴリズムは深探索アルゴリズムに基づいて次のルートノードを記録するためのキューque[]を複数必要とし,アクセスされていないノードにアクセスするたびにノードをキューの末尾に加え,現在のノードのサブノード遍歴が終了した後にque[]キューヘッダが指すノードをルートノードとして遍歴し,上記の手順を繰り返す.コード実装:

#include 
#include 
#include 
#include 
#include 
using namespace std;
int que[105],a[105][105],vis[105];
int n,m,rear,head;//head     ，rear     

void BFS(int x)
{
    cout<>n>>m;
    //   
    for(int i=1;i<=n;i++)
    {
        vis[i]=0;
        for(int j=1;j<=n;j++)
        {
            a[i][j]=0;
        }
    }
    int u,v;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        a[u][v]=1;a[v][u]=1;
    }
    head=0;rear=0;
    BFSTravel();
    cout<

操作から言えば,広捜比深捜は複雑であるが,最短経路を求める問題のあるBFSアルゴリズムがDFSアルゴリズムよりはるかに便利であることが利点である.この点は必ず覚えておいてください.例:http://poj.org/problem?id=3278題意:n,m,nからmまでの2つの数を入力し、今点Xにいる場合は、一歩歩いて3つの方法で:1.X+1まで歩いていきます.2.X-1まで歩いていきます.[原句]2*Xのところまでぴょんぴょん跳ねる.最低数ステップ到達m分析を求める:キューを確立し、キューの各量に対応する点の番号(num)とそれまで歩いたステップ数(sum)があり、またvis[]デジタル記録点がアクセスされたかどうかも必要である.(詳細はコードを参照)

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
struct node
{
    int num,sum;  //   h，      num   sum
}h;          
int vis[100005];
queue  que; //  ，        
int n,m,sum;
int BFS()
{
    //         
    while(!que.empty())
        que.pop();
    // n   h，        0，     
    h.num=n;h.sum=0;
    que.push(h);
    node cur,next; //                  
    while(!que.empty())
    {
        cur=que.front();
        que.pop();
        //                  
        if(cur.num==m) return cur.sum;
        //           
        int dir[]={1,-1,cur.num,};
        for(int i=0;i<3;i++)
        {
            next.num=cur.num+dir[i]; //         
            next.sum=cur.sum+1;      //    +1
            //                 
            if(next.num>=0&&next.num<100005&&!vis[next.num])
            {
                que.push(next);
                vis[next.num]=1; //      
            }
        }
    }
    return 0;
}
int main()
{
    while(cin>>n>>m)
    {
        memset(vis,0,sizeof(vis));
        sum=BFS();
        cout<

BFSは最小ステップ数または最短距離を求めるのに適しており、古典的な例題は典例プレートを見る.