optimale Netzwerke mit den Algorithmen von Prim und Kruskal

Algorithmus von Prim

Wähle einen Startort aus und nenne ihn erreichbar. Alle anderen Orte gelten zu Beginn als nicht erreichbar.

Führe die folgenden Schritte so oft aus, bis alle Orte erreichbar sind:

Baue die kürzeste Verbindung zwischen zwei Orten, von denen einer erreichbar und der andere nicht erreichbar ist.

Bezeichne den bislang nicht erreichbaren Ort neu als erreichbar.

Algorithmus von Kruskal

Führe den folgenden Schritt so oft aus, bis alle Orte untereinander verbunden sind:

Baue die kürzeste Verbindung zwischen zwei Orten, die bislang nicht voneinander aus erreichbar sind.

Bedienung

  • Ein Linksklick setzt einen Knoten.
  • Drag-and-drop von einem zu einem zweiten Knoten erstellt eine Verbindung (Kante).
  • Mit einem 2. Drag-and-drop wird eine bestehende Kante aktiviert.
  • Mit 3. Drag-and-drop wird eine aktive Kante gelöscht.
  • Mit Klick auf einen Knoten werden alle mit ihm verbundenen Knoten grün markiert.

Tipp: mit der Taste 's' können nummerierte Screenshot der Zeichenfläche gespeichert werden. Diese können z.B. für händische Bearbeitung ausgedruckt oder dank der Nummerierung einfach zu einer GIF-Animation verarbeitet werden.

sci - fs in