2 
std::list <int> q;
std::vector<bool> visited(cols + 1);
for(int i = 1; i <= cols; i++) visited[i] = false;
visited[x] = true;
if(!l[x].empty())
{
    for(std::list<int>::iterator i = l[x].begin(); i != l[x].end(); i++)
    {
        q.push_back(x); q.push_back(* i);
    }
    while(!q.empty())
    {
        y = q.back(); q.pop_back();
        x = q.back(); q.pop_back();
        if(!visited[y])
        {
            visited[y] = true;
            if(!l[y].empty())
            for(std::list<int>::iterator i = l[y].begin(); i != l[y].end(); i++)
            {
                if(!visited[*i])
                {q.push_back(y); q.push_back(* i);}
            }
            dfst[x].push_back(y);
            if(flag != 0) dfst[y].push_back(x);
        }
    }
}

これは、グラフ内のスパニング ツリーを見つけるための私の DFS アルゴリズムです。2 つの頂点間の最短経路を見つける BFS アルゴリズムに変換する必要があります。うーん...どうすればいいですか？BFS アルゴリズムは、上記のものと多少似ていますか? それとも最初から書く必要がありますか？

l - 隣接リスト dfst - 最後にスパニング ツリーを保持する配列 x - 開始頂点 y - ヘルパー変数

4

4 に答える 4

4

DFS と BFS は本質的に同じアルゴリズムです。秘訣は、どのデータ構造を使用するか、またはどのノードを最初に探索するかです。

深さ優先検索はスタックを利用するため、アルゴリズムに戻る前に可能な限り下に移動します。

幅優先検索を利用するには、ノードのキューを使用し、各ノードを探索し、(まだアクセスしていない場合は) 隣接ノードをキューに追加し、親ノードの残りの隣接ノードを処理してから先に進む必要があります。

コードの大幅な変更ではなく、リストからノードを取得する方法を変更するだけです。

後ろから飛び出すのではなく、単にq.pop_front()ノードを取得するために使用します。

于 2013-06-18T21:13:02.273 に答える
3

BFS は DFS に似ています。バックトラックして繰り返すのではなく、深さ 1 のすべてのノードを調べ、次に深さ 2 のすべてのノードを調べ、すべてのノードにアクセスするまで続けます。

基本アルゴリズム:

 -Choose a starting node and add to LookQueue
 -look at all nodes directly touching and add them to LookQueue
 -when you've looked at them all
    -look at all nodes in LookQueue (removing them as you do)
    and look at all nodes touching them (adding them as you do)
       -repeat until all nodes are visited
于 2013-06-18T21:13:34.987 に答える
0

いいえ、コードを大きく変更する必要はありません。DFSの場合はreplace stackをQueueに置き換えるだけでBFSになります。

BFS と DFS の実装の違いは、「BFS は Queue を使用して実装され、DFS は Stack を使用して実装される」ことです (理由は、DFS が迷路のような深さを行うためです)。

自分で変更を確認してください:

DFS:

void dfs(int start)
{
    int j,temp; 
    stack<int> s; //STACK
    s.push(start);
    vector<int>:: iterator it;
    while(s.empty()==0)
    {
        temp=s.top(); // Top element from Stack
        s.pop();
        status[temp]=1; // marked as visited , 0 means unvisited
        cout<<temp<<endl; // visited element
        for(it=list[temp].begin();it!=list[temp].end();it++)
        {
            j=*it;
            if(status[j]==0)
            {
                s.push(j);
                status[j]=2;    // means that it is in stack        
            }
        }

    }
}

BFS:

void bfs(int start)
{
    int j,temp; 
    queue<int> q; // QUEUE
    q.push(start);
    vector<int>:: iterator it;
    while(q.empty()==0)
    {
        temp=q.front(); // Front element from Queue
        q.pop();
        status[temp]=1; // marked as visited , 0 means unvisited
        cout<<temp<<endl; // visited element
        for(it=list[temp].begin();it!=list[temp].end();it++)
        {
            j=*it;
            if(status[j]==0)
            {
                q.push(j);
                status[j]=2;    // means that it is in queue        
            }
        }

    }
}

ご覧のとおり、両方の実装は「STACK と QUEUE の使用」が異なるだけです。

お役に立てれば ！

于 2013-06-18T21:59:06.483 に答える