隣接リストを使用した幅優先探索でALDS1_11_Cを解く

以前は隣接行列と幅優先探索を使って、ALDS_1_11_Cの問題を解きましたが、 今回は、隣接リストと幅優先探索を使って、この問題を解いてみたいと思います。

隣接リストを使用した幅優先探索・深さ優先探索の計算量は、こちらに書いたとおり、
O(|V| + |E|)の計算量になるので、隣接行列を使用した時よりも計算量が少なくなります。
(V = 頂点数,E = Vに対して隣接する頂点)

隣接リストを表現する方法

隣接リストを表現するために、c++のvectorを使います。

隣接リストの入力は以下のような形式で渡されるので、

1 2 2 4

以下のように隣接リストを定義して、挿入すればよいです。

// 隣接リストの定義
vectorlist[N];

    // nは頂点数
    for(int i = 0;i < n;++i){
        // uは頂点番号
        // kはuに隣接する頂点の数
        cin >> u >> k;
        // 頂点を移動する(便宜上0から始まるようにずらす)
        u--;
        // 頂点の数だけ回す
        for(int j = 0;j < k;++j){
            cin >> v;
            // 隣接行列に挿入する
            list[u].push_back(v - 1);
        }
    }

隣接リストによる幅優先探索のやり方

では、隣接リストにより幅優先探索を行う箇所を見ます。

隣接行列では、行列の数列分探索していましたが、隣接リストでは、頂点が隣接している分だけ回すだけでokです。

    while(!q.empty()){
        u = q.front();
        q.pop();
        // 頂点分探索する
        for(int i = 0;i < list[u].size();++i){
            // 隣接する頂点
            int v = list[u][i];
            // 頂点が未訪問
            if(d[v] == INFTY){
                // 対象の頂点の距離は前の頂点 + 1
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }

全体のソースコード

最後に全体のソースコードを載せます。

#include<iostream>
#include<queue>
#include<vector>
#include<stack>

using namespace std;

#define N 100
#define INFTY 99999999
vectorlist[N];

int 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 i = 0;i < list[u].size();++i){
            // 隣接する頂点
            int v = list[u][i];
            // 頂点が未訪問
            if(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){
        cin >> u >> k;
        // 頂点を移動する
        u--;
        // 頂点の数だけ回す
        for(int j = 0;j < k;++j){
            cin >> v;
            // 隣接行列に挿入する
            list[u].push_back(v - 1);
        }
    }
    
    bfs(0);
    
    for(int i = 0;i < n;++i){
        cout << i + 1 << " " << ((d[i] == INFTY) ? (-1) : d[i]) << endl;
    }
    
    return 0;
}