幅優先探索

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。

グラフ \(G=(V,E)\) 上の2頂点 \(u,v\) が同じ連結成分に属しているか判定するアルゴリズムについてです。 ...

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。

連結成分は3つアルゴリズム

グラフ \(G=(V,E)\) の連結成分の個数を数えるアルゴリズム：

「未探索」 ...

幅優先探索とは、全探索アルゴリズムの一種です。最短経路を求める際に使用される基本的なアルゴリズムです。

木などのグラフやグラフと同一視できるものを探索する際に良く使われます。深さ優先探索と似ていますが、幅優先探索は始めの状 ...

深さ優先探索とは、全探索アルゴリズムの一種です。グラフや、グラフと同一視できるものを探索する際に良く使われます。

幅優先探索(BFS)と似ていますが、深さ優先探索は末端に到達するまで「深く」探索してから、他のノードの探索を ...