Pseudokod

Lekcja 4 z 9 w kursie Algorytm Prima – algorytmy grafowe w 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

Krawędź (u, v, w) przecina przekrój, gdy inTree[u] i inTree[v] się różnią.
Przeglądanie wszystkich krawędzi w każdej rundzie w celu znalezienia najtańszej krawędzi przecinającej przekrój upraszcza kod (w przypadku małych grafów nie jest potrzebna kolejka priorytetowa).

Spróbuj swoich sił

Ta lekcja nie zawiera wyzwania z kodem.