About this episode
Nachdem wir den Begriff schon ein paar Male gestreift haben, heute ein genauerer Blick auf Graphen. Darin: informierte und uninformierte Suche sowie eine Erkundung der Dresdner Umgebung.Shownotes
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
