テクノロジ
幅優先探索とは
読み方：はばゆうせんたんさく
ひとことで言うと：始点に近い頂点から層ごとに広げて調べるグラフ探索法。
意味をわかりやすく解説
幅優先探索（BFS）は、始点から距離が近い頂点を先に調べ、層ごとに探索範囲を広げる方法です。
未探索の頂点をキューで管理します。すべての辺の重みが等しい、または重みのないグラフでは、始点から各頂点への最小辺数を求められます。
具体例
迷路で入口から1歩で行けるマスを全部調べ、次に2歩で行けるマスを調べる動きがBFSです。
似た用語との違い
覚え方
BFS＝Breadth＝幅。キューで「先に見つけたものから」処理します。
基本情報技術者試験の試験ポイント
キューとの対応と、無重みグラフで最短辺数が求められる理由を理解します。
CHECK QUESTION
無重みグラフで始点から各頂点までの最短辺数を求めたい場合、DFSとBFSのどちらが適していますか。
答えを見る
BFSです。始点から近い頂点を距離順に探索するため、最初に到達したときの辺数が最小になります。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。