幅優先探索を使用してグラフの頂点から頂点への最短距離を求める方法をALDS_1_11_Cを使って学ぶ

キューを使った幅優先探索をAIZU ONLINE JUDGEの例題を利用して、学びたいと思います。
幅優先探索の概念についてはこちらにまとめています。

では、例題を見ていきます。

例題

与えられた有向グラフ G=(V,E) について、
頂点 1 から各頂点への最短距離 d（パス上の辺の数の最小値）を求めるプログラムを作成してください。
各頂点には 1 から n までの番号がふられているものとします。
頂点 1 からたどり着けない頂点については、距離として-1 を出力してください。

入力

最初の行に G の頂点数 n が与えられます。続く n 行で各頂点 u
の隣接リストが以下の形式で与えられます：

u k v1 v2 ... vk

uは頂点の番号、k は u の出次数、
v1v2...vk　は u に隣接する頂点の番号を示します。

制約

1≤n≤100

出力

各頂点について id、d を１行に出力してください。
id は頂点の番号、d は頂点 1 からその頂点までの距離を示します。頂点番号順に出力してください。

解法

幅優先探索は、始点sから距離k + 1にある頂点を探索する前に、距離kの頂点をすべて発見しているので、
始点から各頂点までの最短距離を順番に求めることができます。

幅優先探索のアルゴリズム

1.始点sをキューに入れる

キューが空でない限り以下の操作を繰り返す

• キューから頂点uを取り出して訪問する(訪問完了)
• 頂点uに隣接し、未訪問の頂点vについて、始点から頂点までの距離を表す変数d[v]をd[u] + 1と更新し、
  頂点vをキューに入れる

グラフを例に幅優先探索が行われる流れを見る

下図のグラフを例として、頂点0から幅優先探索が行われる流れを追います。

1.始点である頂点0をキューに挿入します。
始点0からの距離を0とします。

0

2.キューから0を取り出して、訪問します。
頂点0に隣接して未訪問の1,3,5の頂点をキューに挿入します。 頂点1,3,5までの距離は頂点0までの距離+1となります。

1,3,5

3.キューの先頭から1を取り出して、訪問します。
頂点1に隣接する未訪問の頂点はないので、次に進みます。

3,5

4.キューの先頭から3を取り出して、訪問します。
頂点3に隣接する未訪問の頂点は、2のみなので、2をキューに挿入します。 頂点2までの距離は、頂点3までの距離+1になります。

5,2

5.キューの先頭から5を取り出して、訪問します。
頂点5に隣接する未訪問の頂点4,6をキューに入れます。
頂点4,6までの距離は頂点5までの距離+1になります。

2,4,6

6.キューの先頭から2を取り出して、訪問します。
頂点2に隣接する未訪問の頂点はないので、次に進みます。

4,6

7.キューの先頭から4を取り出して、訪問します。
頂点4に隣接する未訪問の頂点はないので、次に進みます。

6

8.キューの先頭から6を取り出して、訪問します。
頂点6に隣接する未訪問の頂点はないので、次に進みます。

キューが空になったので、幅優先探索終了です。
探索終了時に頂点0から各々の頂点への最短距離が求められます。

幅優先探索に必要な変数

キューを利用した深さ優先探索に必要な変数は以下のようになります。

変数名例	役割
color[N]	未訪問・訪問中・訪問済みの状態を表すための変数
M[n][n]	グラフの隣接行列を表すための変数、頂点が隣接している場合は1(true)など
Queue q	使用するキュー
d[n]	始点からインデックスを頂点番号とする距離を保存しておく

隣接行列を利用した幅優先探索の疑似アルゴリズム

bfs()

 各頂点についてcolorを未訪問に設定する
 各頂点において、d[u]を到達できないことを示す値を入れる
 // 始点をsとします
 color[s] = 訪問中
 d[s] = 0
 q.enque(s)
 
 while Qが空でない
  u = Q.dequeue()
  for vが0から|V| - 1まで
   if M[u][v] && color[v] == 未訪問
    color[v] = 訪問中
    d[v] = d[u] + 1
    Q.enqueue(v)
  color[u] = 訪問済み
  
 

計算量考察

隣接行列を用いた幅優先探索は、各頂点について、すべての頂点に隣接しているかどうかを調べるので、
$O(|V|^2)$のアルゴリズムになります。

c++を用いた解答例

では最後に隣接行列で幅優先探索を行う解答例を載せます

#include<iostream>
#include<queue>

using namespace std;

#define N 100
#define INFTY 99999999

int n,
// 隣接行列
M[N][N];
// 距離 colorも同時に管理する
int d[N];

void bfs(int s){
    queue q;
    q.push(s);
    
    // 距離を初期化
    for(int i = 0;i < n;++i){
        d[i] = INFTY;
    }
    d[s] = 0;
    // 対象の頂点番号
    int u;
    
    while(!q.empty()){
        u = q.front();
        q.pop();
        
        for(int v = 0;v < n;++v){
            // 頂点が隣接しているかつ未訪問
            if(M[u][v] == 1 && d[v] == INFTY){
                // 対象の頂点の距離は前の頂点 + 1
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    
}

int main(){
    int u,k,v;
    
    cin >> n;
    
    // 隣接行列を初期化
    for(int i = 0;i < n;++i){
        for(int j = 0;j < n;++j){
            M[i][j] = 0;
        }
    }
    
    for(int i = 0;i < n;++i){
        cin >> u >> k;
        // 頂点を移動する
        u--;
        // 頂点の数だけ回す
        for(int j = 0;j < k;++j){
            cin >> v;
            --v;    // ずらす
            M[u][v] = 1;
        }
    }
    
    bfs(0);

    for(int i = 0;i < n;++i){
        cout << i + 1 << " " << ((d[i] == INFTY) ? (-1) : d[i]) << endl;
    }

    return 0;
}