קוד מדומה

שיעור 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] שונים זה מזה.
סריקת כל הקשתות בכל סבב כדי למצוא את הקשת החוצה הזולה ביותר משאירה את הקוד פשוט (אין צורך בתור עדיפויות עבור גרפים קטנים).

נסו בעצמכם

השיעור הזה לא כולל אתגר קוד.