Pseudo Code

Coddy의 프림 알고리즘 - 그래프 알고리즘 코스 레슨 — 9개 중 4번째.

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

inTree[u]와 inTree[v]의 값이 다를 때 간선 (u, v, w)는 컷(cut)을 가로지릅니다.
가장 저렴한 가로지르는 간선을 찾기 위해 매 라운드마다 모든 간선을 스캔하면 코드가 단순하게 유지됩니다 (작은 그래프의 경우 우선순위 큐가 필요하지 않음).

직접 해보기

이 레슨에는 코드 챌린지가 없습니다.

실력 점검

이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.

프림 알고리즘 - 그래프 알고리즘의 모든 레슨

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