-
oft erwähnt, aber nie systematisch eingeführt: der Begriff Graph
- Graph: eine Menge von Knoten mit Kanten dazwischen
- z.B. Nahverkehrsnetz: Knoten = Haltestellen, Kanten = Direktverbindung zwischen zwei Haltestellen
- z.B. soziale Medien: Knoten = Personen, Kanten = "ist befreundet/folgt"
- anders als bei Listen (STP077) oder Maps (STP079) große Variabilität darin, was ein Graph fundamental ist
- z.B. gerichtete vs. ungerichtete Graphen: Haben die Kanten eine Richtung oder nicht? (siehe Beispiele oben)
- häufig verwendete Unterarten von Graphen:
- Baum: ayzklischer ungerichteter zusammenhängender Graph (z.B. siehe STP077/STP079: zum effizienten Abspeichern von sortierten Listen bzw. Maps)
- azyklischer gerichteter Graph (z.B. Versionsverwaltung, Familienstammbaum, Firmen-Organigramm)
- planarer Graph: siehe "Untangle"
-
Wie durchschreitet man einen Graphen? -> Suchalgorithmen, im allgemeinsten Fall die zwei wichtigsten "uninformierten" Suchalgorithmen
- Breitensuche: von einem Startpunkt pro Runde alle Nachbarn von bereits besuchten Knoten besuchen
- Tiefensuche: vom Startpunkt aus immer erst einen Nachbarn besuchen und dann dort wieder einen Nachbarn; sobald keine weiteren unbesuchten Nachbarn möglich sind, Backtracking zum vorherigen Knoten, bis ein neuer unbesuchter Nachbar gefunden wird
- sowohl Breiten- als auch Tiefensuche erzeugen beim Durchschreiten des Graphen einen Suchbaum, der ein Spannbaum ist (vgl. Spanning Tree bei Ethernet in STP028)
- Abwägung: Tiefensuche ist einfacher zu implementieren und hat weniger Speicheraufwand (braucht nur eine "besucht-Markierung" und keine Kandidatenliste), kann aber in der Praxis problematisch sein :)
-
Beobachtung: Breitensuche findet garantiert den kürzesten Pfad vom Startpunkt zu einem gewünschten Endpunkt
- Abwandlung für Wegfindung: Dijkstra-Algorithmus
- Voraussetzung: Kanten haben auch noch ein Gewicht (analog zu einer Streckenlänge)
- Breitensuche merkt sich bei jedem Knoten den kürzesten Gesamtweg zu diesem Knoten
- beim Auswählen des nächsten Besuchskandidaten Wahl des Knotens mit dem kürzesten Gesamtweg
- Erweiterung zum A*-Algorithmus mittels Ergänzung um eine Heuristik, die beschreibt, wie nahe gefundene Knoten am Ziel sind (damit je nach Situation enorme Effizienzsteigerung möglich, siehe z.B. dieser Blogpost der Factorio-Entwickler)
-
im Gespräch erwähnt: #WissPodWeihnacht 3: Das Haus vom Niko…hä?!? mit Geschichten aus der Mathematik
