breadth first search
幅優先探索
名詞
複数形: breadth first searches
breadth first search（幅優先探索）は、グラフや木構造の探索において、根に近いノードから順番に、同じ階層にあるすべてのノードを網羅してから次の階層へ進む手法です。このアプローチの最大の特徴は、開始地点から目的地点までの最短経路を確実に見つけ出せる点にあります。
深さ優先探索との対比depth first search（深さ優先探索）が、一つの道を突き当たりまで深く掘り下げてから戻るのに対し、breadth first searchは横方向に広がるように探索します。そのため、メモリ消費量は多くなりがちですが、最短距離を求める問題や、ネットワーク上の最短ホップ数を計算する場合に非常に有効です。
実用的な活用シーン
このアルゴリズムは、単なるデータ検索だけでなく、以下のような具体的な場面で頻繁に利用されます。
ソーシャルネットワークにおける知り合いの知り合いなどの最短のつながりを特定する場合
パズルや迷路において、最小の手数でゴールに到達するルートを導き出す場合
ネットワークルーティングにおいて、パケットを転送するための最適な経路を選択する場合
意味
名詞幅優先探索
ルートノードから開始し、次の深さレベルのノードに移動する前に、現在の深さにあるすべての隣接ノードを探索する、木またはグラフのデータ構造を走査または検索するためのアルゴリズムのこと
The developer implemented a breadth first search to find the shortest path between two nodes in the network.
開発者は、ネットワーク内の2つのノード間の最短経路を見つけるために幅優先探索を実装した。
関連語
depth first searchalgorithmgraphtreenodevertexedgequeuetraversalsearchpathdistancelayerlevelneighboradjacencyadjacency listadjacency matrixcomplexitytime complexityspace complexityfrontierrootleafbranchdirected graphundirected graphcycleconnectivitycomponentheuristicoptimizationrecursioniterationpointerstackdata structurecomputer scienceprogramminglogicstate spaceexplorationdiscoverybreadthdepthwidthlayeringexpansionnavigationroutingnetworktopologyflowbottlenecklatencyefficiencyoptimalcompleteexhaustivebacktrackingbinary tree