Pseudo Code

Lektion 4 von 9 im Kurs Prims Algorithmus - Graphenalgorithmen von Coddy.

prim(n, edges):
   inTree[0] = true; alles andere false
   total = 0
   repeat (n - 1) times:
      best = die überquerende Kante (ein Endpunkt drin, einer draußen) mit dem kleinsten Gewicht
      if none exists: stop      # nicht verbunden
      total += best.weight
      inTree[best.outsideEndpoint] = true
   return total

Eine Kante (u, v, w) überquert den Schnitt, wenn inTree[u] und inTree[v] sich unterscheiden.
Das Scannen aller Kanten in jeder Runde, um die günstigste überquerende Kante zu finden, hält den Code einfach (keine Prioritätswarteschlange für kleine Graphen erforderlich).

Probier es selbst

Diese Lektion enthält keine Programmieraufgabe.

Teste dich selbst

Diese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.

Alle Lektionen in Prims Algorithmus - Graphenalgorithmen

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