[Breadth-first search - Wikipedia](https://en.wikipedia.org/wiki/Breadth-first_search) [[Introduction to Algorithms]]より引用。 > 幅優先探索 (breadth-first search) は最も単純なグラフ探索アルゴリズムの 1 つであり，多くの重要なグラフアルゴリズムの原型である. > Prim(プリム)の最小全域木アルゴリズムとDijkstra の単一始点最短路アルゴリズムはBFSに類似する。 > グラフ G = (V, E) と始点 (source vertex) s が与えられたとき，幅優先探索は G の辺を組織 的に探索して，s から到達可能なすべての頂点を “発見” し，すべての到達可能な頂点について s からの距離(辺数の最小値)を計算する. s から到達可能な任意の頂点 v について，幅優先木における s か ら v への単純道は G における s から v への「最短路」，すなわち最小数の辺を含む道に対応す る.有向グラフと無向グラフのどちらに対してもこのアルゴリズムは正しく働く.