過去問クラブ 学ぶ、わかる、つづく。
ログイン
用語解説

幅優先探索

近いところから順に調べる

幅優先探索は、開始点の隣接頂点を調べ、次にその一段先を調べるように、距離の層を広げていく探索方法です。BFSと略します。先に見つけた頂点を先に処理するため、キューを使うのが基本です。辺の重みが全て同じグラフでは、開始点からの辺数が最小の経路を求めることに利用できます。

Pythonによる例

from collections import deque

def breadth_first(graph, start):
    distance = {start: 0}
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        for neighbor in graph.get(vertex, []):
            if neighbor not in distance:
                distance[neighbor] = distance[vertex] + 1
                queue.append(neighbor)
    return distance

初めて見つけた頂点の距離を記録し、キューへ追加しています。

距離が決まる理由

距離0の開始点、距離1の頂点、距離2の頂点という順で処理するため、初めて到達した時点で最小の辺数が決まります。ただし、辺によって費用が異なる場合は、辺数が少なくても費用が小さいとは限りません。重み付きの最短経路へ無条件に使える方法ではありません。

訪問済みの記録

同じ頂点へ複数の経路から到達する場合、キューへ入れる時点で発見済みにしておくと重複を抑えられます。取り出すまで未訪問のままにすると、同じ頂点を何度も追加する実装になることがあります。最短経路そのものを復元したい場合は、距離だけでなく、どの頂点から来たかも保存します。

試験での比較

深さ優先探索は一つの枝を深く進み、幅優先探索は同じ深さの候補を先に調べます。幅が大きいグラフでは、キューへ多くの頂点を保持するため記憶量にも注意が必要です。試験ではキューの先頭と末尾を明確にし、隣接頂点を追加する順序を問題の指定に合わせます。到達できない頂点は距離が記録されないことも、結果の解釈で重要です。

参考資料

内容確認日:2026-11-13

この言葉を含む問題を探す

この用語に関連する問題

1問

用語一覧

10件

パーミッション・マーケティング

パーミッション・マーケティング とは、パーミッション(permition)は、日本語で 許可。 この事から、お客様より許可をとった上で行うマーケティング手法にな...

バイラルマーケティング

バイラル・マーケティングとは、 英語表記では Viral marketing . バイラルとは、「ウィルス性の」という意味であり、口コミなどでウィルスのように繁殖して広...

バックアップ

復元のために別の状態を保存する バックアップは、障害や誤操作などで失われたデータを戻せるよう、別の保存先や世代にデータを保管することです。現在のデータ...

ハッシュ表

キーから格納場所を求める ハッシュ表は、キーにハッシュ関数を適用して格納場所の候補を求め、対応する値を保存・検索するデータ構造です。社員番号から社員情...

ハッシュ関数

意味と用途 ハッシュ関数は、入力データから一定の規則で値を計算する関数です。暗号の分野では、任意の長さのデータから固定長のハッシュ値を得る仕組みがよく...

バッファオーバーフロー

確保した領域を越えて書き込む バッファオーバーフローは、データを一時的に置くためのメモリー領域に、その容量を超えて書き込んでしまう問題です。隣接するデ...

バブルソート

隣同士を比べて交換する バブルソートは、隣り合う要素を比較し、順序が逆なら交換する操作を繰り返して整列する方法です。一回の走査で大きな値が末尾へ移るな...

バリュー・チェーン

バリューチェーン分析とは、企業の価値の連鎖と呼ばれるもので、企業が生み出す付加価値の繋がりを分類したものである。 5つの主活動と4つの支援活動からなる。...

パレート図

値が降順にプロットされた棒グラフとその累積構成比を表す折れ線グラフを組み合わせた複合グラフ。 どの問題がどの程度占めているか、また、いくつ改善すれば全...

幅優先探索

近いところから順に調べる 幅優先探索は、開始点の隣接頂点を調べ、次にその一段先を調べるように、距離の層を広げていく探索方法です。BFSと略します。先に見つ...