幅優先探索(BFS)というのは,有名なグラフアルゴリズムで,その名の通りグラフを同じ距離の順にたどっていくアルゴリズムだ.
以下の資料を参考にして,詳細を掴んでいく.
https://mnakao.net/data/2020/HPC175.pdf
グラフの直径が小さいというのは,グラフの互いのノードの最大距離が小さいということを意味する. 探索中の頂点の数が非常に大きくなると効率が悪くなるというのは,それぞれの頂点に対して隣接している頂点がすでに訪問済みの可能性が高く,それを何度も確認のために訪問するのは効率が悪いということだと思う.
そこで,訪問する数を削減するために,探索の中間の段階でTop Downの探索からBottom Upの探索に切り替える方式がこのハイブリッドBFSだ.
下記の表が示している通り,チェック回数を減らすためには最初にTop Downで探索し,途中からBottom Upに切り替え,最後にもう一度Top Downするのが望ましい.