Pseudo Code

Урок 4 из 9 курса Алгоритм Прима — Алгоритмы на графах на Coddy.

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