Pseudo Code

Coddyの「プリム法 - グラフアルゴリズム」コースのレッスン 4/9。

prim(n, edges):
   inTree[0] = true; everything else false
   total = 0
   repeat (n - 1) times:
      best = the crossing edge (one endpoint in, one out) with smallest weight
      if none exists: stop      # disconnected
      total += best.weight
      inTree[best.outsideEndpoint] = true
   return total

エッジ (u, v, w) は、inTree[u] と inTree[v] の値が異なるときにカットをまたぎます。
各ラウンドですべてのエッジをスキャンして最も安価なカットをまたぐエッジを見つけることで、コードをシンプルに保つことができます（小規模なグラフでは優先度付きキューは不要です）。

自分で試してみよう

このレッスンにはコードチャレンジは含まれていません。

腕試し

このレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。

プリム法 - グラフアルゴリズムのすべてのレッスン

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2