以前は隣接行列と幅優先探索を使って、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;
}
