0Pricing
Coding Interview Prep · レッスン

ヒープを使う Prim の MST

1 つの頂点から木を成長させます

「ヒープを使う Prim の MST」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

MST への別の道筋

Prim法も最小全域木を求めますが、すべての辺を先にソートするのではなく、1つの連結した塊を外側へ広げていきます。🌱

1つの頂点から始める

任意の頂点を選び、訪問済みとしてマークします。木は1つの頂点から始まり、辺を1本ずつ追加しながら広がります。

visited = [False] * n

フロンティアの考え方

各ステップでは、木から外側へ出るすべての辺を調べます。Prim法は、そのフロンティアにある辺の中から常に最も安い辺を選びます。

ヒープで最小値を選ぶ

min-heapを使うと、フロンティアで最も安い辺をすばやく見つけられます。候補の辺を追加し、各ラウンドで重みが最小のものを取り出します。

import heapq
heap = [(0, start)]

最も安い辺を取り出す

ヒープから最小の要素を取り出します。そこから重みと、成長中の木に追加するのが最も安い次の頂点が得られます。

w, u = heapq.heappop(heap)

古い要素をスキップする

1つの頂点がヒープに複数回入ることがあります。取り出した頂点がすでに訪問済みなら、無視して次の要素を取り出します。

if visited[u]:
    continue

追加して広げる

取り出した頂点を訪問済みとしてマークし、その重みを合計に加えます。次に、その頂点から出る各辺を、後のステップのためにヒープへ追加します。

visited[u] = True
total += w
for wt, v in adj[u]:
    heapq.heappush(heap, (wt, v))

完成するまで繰り返す

すべての頂点が訪問済みになるまで、要素の取り出しと木の拡張を繰り返します。その時点で、累積した合計が最小全域木の重みになります。

計算時間

各辺は1回追加され、1回取り出されるため、ヒープを使う Prim法の計算量はO(E log V)です。これは Kruskal法と同程度です。

Prim法とKruskal法

隣接リストで表された密グラフにはPrim法を使い、単純な辺リストがすでにある場合は Kruskal法を使います。どちらも同じ MST の重みを求めます。

Dijkstra法に似ている

ヒープを使うループはDijkstra法とよく似ていますが、比較するのは経路距離ではなく、辺そのものの重みです。このパターンに気づけば、コーディング時間を短縮できます。⚡

確認問題

Prim法が各ラウンドで次の辺をどのように選ぶか思い出してみましょう。

振り返り

Prim法で MST を構築しました。どこからでも始め、min-heap で最も安いフロンティアの辺を追加し、古い訪問要素をスキップします。よくできました！🎉

よくある質問

「ヒープを使う Prim の MST」レッスンは無料ですか？

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

「ヒープを使う Prim の MST」で何を学びますか？

1 つの頂点から木を成長させます ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

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

「ヒープを使う Prim の MST」レッスンにはどのくらい時間がかかりますか？

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

このCoding Interview Prepレッスンでコードを書いて実行できますか？

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

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

  1. 経路圧縮付き DSU
  2. ランクによる Union と連結成分
  3. Kruskal の最小全域木
  4. ヒープを使う Prim の MST
← Coding Interview Prepに戻る