Wir kennen bereits einen greedy (gierigen) Algorithmus von der ersten fuelle-Funktion. Die Idee ist, immer den besten aktuellen Wert weiter zu verfolgen Leider hat unsere erste fuelle-Funktion den Nachteil, dass sie nicht alle Lösungen findet. Es gibt aber Algorithmen, die ebenfalls während des Suchprozesses keine Entscheidungen rückgängig machen und trotzdem sicher eine beste Lösung finden. Ob das geht, hängt vom Problem ab und das hier betrachtete Problem des minimal spanning tree ist ein solches Problem. Die beiden hier betrachteten Algorithmen sind der Algorithmus von Prim und der Algorithmus von Kruskal.
Das Material zum Kurs ist abschnittsweise, auf mehrere Seiten verteilt abgelegt.
Ein minimales Versorgungsnetz
Die mit Python entwickelte Software zum Erstellen von Graphen finden Sie im Abschnitt zur Software.
Programmierumgebung: Racket