BFSの感想
「幅優先探索の利点は隣接頂点を網羅できるところにあり、2回目の訪問済頂点は枝刈りできるので途中で辺が追加されない有向グラフならば、如何に複雑でもO(N)で全ての頂点を調べることが出来る」の暗記が本質だと思う。したがって、頂点への到達可能性を調べる目的なら高速。途中で訪問済頂点に辺が追加されてしまうと訪問済頂点を調べ直さないといけなくなるので、O(N)ではなくなる。
BFSのテンプレート
bfs の引数
- graph& g 有向グラフ
- vl& svi スタートの頂点インデックス集合
- bit& vis 訪問チェック用の bitset
graph g; vl svi; bit vis(lsz(g)); lam(bfs, graph& g, vl& svi, bit& vis) vo { dl q; forx(x,svi) pub(q,x); // 探索開始 while(!q.empty()) { au cvi=pof(q); vis[cvi]=true; // 現在の頂点cvに接続している隣接頂点nvに対する処理 forx(nvi,nvx,g[cvi]) { if(vis[nvi]) continue; /*********************************** 初訪問の頂点に対する処理をここに追加 ************************************/ vis[nvi]=true; pub(q,nvi); } } };
