minimale Spannbäume und ihre Algorithmen

Der Dijkstra-Algorithmus (Greedy)

Bevor man starten: Startknoten markieren. Kennzahl O zuweisen, als aktuellen Knoten bezeichnen Schritt 1: Vom aktuellen Knoten zu allen Nachbarknoten gehen und Summe aus der Kennzahl des aktuellen Knotens und der Lange der Strecke berechnen. Entscheidungen: Nachbarknoten ist markiert? --> Mache nichts. Nachbarknoten hat keine Kennzahl? --> Summe als Kennzahl zuweisen und Strecke zum aktuellen Knoten markieren. Nachbarknoten hat eine Kennzahl kleiner der Summe? --> Mache nichts Nachbarknoten hat eine Kennzahl größer der Summe --> Streiche dortige Summe und Markierungen, weise die Summe als neue Kennzahl zu und markiere die Strecke zum aktuellen Knoten.

Schritt 2: Betrachte alle Knoten mit Kennzahl aber ohne rote Markierung. Suche nach dem Knoten mit kleinster Kennzahl.

Schritt 3: Bezeichne diesen als aktuelle Knoten. Mehrere Knoten haben kleinste Kennzahl? --> Suche die einen beliebige dieser Knoten als aktuellen Knoten aus.

Schritt 4: Markiere den aktuellen Knoten, zeichne die dort markierte Strecke in rot ein.

Schritt 5: Falls es noch Knoten gibt, die nicht markiert sind, weiter bei Schritt I.

Der Algorithmus von Kruskal (Greedy)

Kante mit dem geringsten Gewicht markieren Knoten dieser kante markieren Wenn beide Knoten der nächst kleineren kante markiert sind --> wird diese nur markiert wenn dadurch kein Zyklus entsteht, also nur dann, wenn sich die beiden Knoten nicht bereits im selben Baum befinden

Formulierung 2: alle kanten des Graphen werden nach ihrem Gewicht in einer Kantenliste sortiert jeder Knoten wird als Baum aufgefasst, dabei ist jeder Knoten Sohn und Vater zugleich die kante mit dem geringsten Gewicht wird genommen (Greedy-Prinzip) und überprüft, ob die Knoten am Kantenende in unterschiedlichen Bäumen sind (kein Zyklus), ist dies der Fall, werden die Knoten verbunden und die Kante aus der Kantenliste gelöscht, im anderen Fall wird die Kante nicht aufgenommen

Der Algorithmus von Prim (Greedy)

Der Algorithmus von Prim hat als Ergebnis, vergleichbar mit dem Kruskal-Algorithmus, einen minimalen aufspannenden Baum eines bewerteten ungerichteten Graphen. Das Verfahren ist gegen über Kruskal effektiver und schneller.

Wähle einen beliebigen Startknoten und markiere ihn solange bis alle Knoten markiert sind: suche nach dem kleinsten Kantengewicht ausgehend von allen markierten Knoten zu allen noch nicht markierten Knoten und markiere den daazu gehörigen Knoten

Formulierung 2: Ausgangspunkt für das Verfahren ist ein beliebiger Startknoten alle kanten zu Nachbarknoten werden in eine Nachbarliste eingefügt, man wählt eine Kante minimaler Länge aus der Nachbarliste und fügt diese Kante dem bereits initialisierten Spannbaum zu von dort wird wieder der minimale Weg, basierend auf der ausgewählten Kante, zum nächsten Knoten gewählt, ist dieser Knoten bereits besucht worden, wird er nicht berücksichtigt dieses Verfahren führt man durch, bis alle Knoten besucht wurden

Tiefensuche (Backtracking)

Pseudocode: tiefensuche (Knoten k)     Markiere k als besucht     für alle Nachbarknoten n von k wiederhole         falls n nicht bereits als besucht markiert ist dann             tiefensuche (n)         ende falls     ende wiederhole

Bei der Tiefensuche werden alle erreichbaren Knoten eines Graphen systematisch besucht. Dabei wird ausge hemd von einem Startknoten immer zunächst so weit wie möglich in die Tiefe vorgedrun gen, bis alle erreichbaren Knoten besucht wurden. Auch auf einem Baum kann man die Tiefensuche ausfüh ren. Das Vorgehen entspricht dann dem bereits bekannten preorder-Durchlauf

starte bei einem Knoten und markiere diesen solange nicht alle nachbarknoten markiert sind gehe zum nächsten nicht markierten Nachbarknoten und wende dort die Tiefensuche an

Backtracking

Backtracking ist eine Lösungsstrategie bei Problem men, bei denen auf mehreren Stufen Wahlmöglichkeiten bestehen. Dabei werden nach dem Versuch-und-Irrtum-Prin zip möglichst viele Schritte durchgeführt. Gerät man dabei in eine Sackgasse, werden einzelne oder mehrere Schritte wieder rückgängig gemacht. Dieses Vorgehen wird so lange wiederholt, bis man zu einer Lösung des Problems gelangt oder feststellen muss, dass es keine Lösung gibt.

Breitensuche (Backtracking)

Pseudocode:   breitensuche()     markiere alle Knoten als nicht besucht     markiere den Startknoten als besucht     füge den Startknoten in eine (zunächst leere) Schlange s ein     solange s nicht leer ist wiederhole         entnehme den vordersten Knoten k aus s         für alle Nachbarknoten n von k wiederhole             falls n als nicht besucht markiert ist dann                 markieren als besucht                 füge n in s ein             ende falls         ende wiederhole     ende wiederhole

Bei der Breitensuche werden alle erreichbaren Knoten eines Graphen systematisch besucht. Dabei wird der Graph ausgehend von einem Startknoten schichtweise, d. h. in die Breite durchsucht, bis alle erreichbaren Knoten besucht wurden, Ein ähnliches Vorgehen wie bei der Breitensuche kennen Sie bereits vom Dijkstra-Algo rhythmus zur Lösung des kürzesten-Weg-Problems. In der Tat lässt sich mit dem Prinzip der Breitensuche der kürzeste Weg zwischen zwei Knoten ermitteln, allerdings nur in einem ungewichteten Graphen. Diese Erweiterung der Breitensuche ist unter dem Namen Algorithmus von Moore bekannt.

Starte bei einem Knoten und füge ihm einer Schlange hinzu solange die Schlange nicht leer ist: aktueller Knoten = Schlangen Front markiere aktuellen Knoten entferne Schlangen front füge alle nachbarknoten von aktueller Knoten zur Schlange hinzu, falls diese nicht markiert sind und markiere sie ist der aktuelle Knoten der gesuchte Knoten gib true zurück gib false zurück