0Pricing
Competitive Programming Academy · レッスン

重みなし最短経路のための BFS

始点からの距離を層ごとに求めます

「重みなし最短経路のための BFS」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

BFSの動作

BFSはグラフを同心円状に探索します。まず開始地点、次に1ステップ離れたすべてのノード、その次に2ステップ離れたノード、という順番です。🌊

同心円が最短を意味する理由

BFSは次の層に進む前に現在の層をすべて処理するため、あるノードに初めて到達したとき、それがそのノードへの最短の重みなし経路になります。

キューが原動力

BFSはキューを使います。先入れ先出しの構造です。新しい隣接ノードを後ろに追加し、先頭から次に処理します。

from collections import deque
q = deque([start])

訪問済みのノードを管理する

visitedマーカーを用意し、同じノードを2回キューに追加しないようにします。これにより、BFSを高速かつ有限に保てます。

visited = [False] * (n + 1)
visited[start] = True

距離を保存する

dist配列に各ノードの層を保存します。開始ノードは0で、各隣接ノードは親の値に1を加えた距離になります。

dist = [-1] * (n + 1)
dist[start] = 0

先頭から取り出す

各ステップでキューの先頭からノードを取り出します。それは未処理の中で最も近いノードなので、すぐに処理します。

u = q.popleft()

隣接ノードを展開する

uの各隣接ノードについて、未訪問なら訪問済みにし、距離を設定して、キューの後ろに追加します。

for v in adj[u]:
    if dist[v] == -1:
        dist[v] = dist[u] + 1
        q.append(v)

完全なループ

キューが空でない間、取り出しと展開を繰り返します。キューが空になったとき、到達可能なすべてのノードを訪問したことになります。

while q:
    u = q.popleft()
    for v in adj[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + 1
            q.append(v)

追加時にマークする

visitedは取り出したときではなく、キューに追加した瞬間に設定します。遅れてマークすると、重複したノードがキューに入ってしまいます。

到達不能なら-1のまま

BFS後も距離-1のままのノードは、開始地点から到達不能ということです。この結果にも意味があります。

BFSは線形時間

BFSは各ノードと各エッジを1回ずつ調べるため、計算量はO(n + m)です。ほとんどのコンテストの制限時間を十分にクリアできます。

確認問題

単純なBFSで最短経路が求まるのはなぜでしょうか。

復習

BFSはキューとdist配列を使って実行します。追加時にマークし、隣接ノードを展開し、終了後に最短距離を読み取ります。🎉

よくある質問

「重みなし最短経路のための BFS」レッスンは無料ですか？

はい。「重みなし最短経路のための BFS」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「重みなし最短経路のための BFS」で何を学びますか？

始点からの距離を層ごとに求めます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。

「重みなし最短経路のための BFS」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 入力から隣接リストを作る
  2. 重みなし最短経路のための BFS
  3. DFS、再帰、反復スタック
  4. 連結成分と Flood Fill
← Competitive Programming Academyに戻る