Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).

Breitensuche: Kürzeste Wege in Graphen finden

Name: Breitensuche: Kürzeste Wege in Graphen finden
Uploaded: 2021-05-22T21:58:56+00:00
Duration: 39 min 50 s
Channel: Algorithmen und Datenstrukturen
Description: Straßennetze lassen sich als Graphen modellieren: Orte und Kreuzungen sind Knoten, Straßen die verbindenden Kanten. Bei gewichteten Graphen ergibt sich …

Algorithmen und Datenstrukturen39:50 7.166 Aufrufe veröffentlicht 22. Mai 2021 Auf YouTube

Das Wichtigste aus dem Video

Tipp auf eine Zeit – das Video springt genau dorthin.

Transkriptautomatisch erstellt · 214 Zeilen

Herunterladen

Jeder von Ihnen hat mit Sicherheit schon einmal ein Navigationssystem benutzt. Wenn ich zum Beispiel an der TRM in Gießen bin und ich habe aber jetzt eine Veranstaltung in Friedberg,
dann kann ich mir so ein Navigationssystem nehmen von einem bekannten Internetriesen hier zum Beispiel und der sagt mir dann, welche Strecke ich mit dem Auto zurücklegen könnte,
um möglichst schnell von A nach B zu kommen. Solche Navigationssystem liegen natürlich Daten zugrunde über das Straßennetz, über die Auslastung der Straße zu jedem Zeitpunkt
und so weiter. Und welche Struktur werden diese Daten vermutlich haben? Denken Sie mal nach. Ja, das werden Graphen sein. Das heißt, es wird Orte geben,
wie zum Beispiel Stellen in der Stadt, wo dann Straßenkreuzungen sind oder Autobahnauffahrten und Abfahrten und so weiter. Und zwischen diesen Orten,
die man dann als Knoten des Graphen auffassen kann, gibt es dann Verbindungen. Das sind dann die Kanten und diese Verbindungen entsprechen den Straßen.
Und wir können die Knoten sogar sehen, die sind hier teilweise als kleine weiße Punkte auf diesem einen Pfad, der hier gerade als kürzester Pfad markiert ist,
in dem Graphen eingezeichnet. Graphen kommen also in realen Problemen als Daten vor. Und mit einem dieser realen Probleme wollen wir uns jetzt ein wenig beschäftigen.
Und das ist eben dieses Problem hier, nämlich kürzeste Wege im Graphen zu finden. Nun ist in einem solchen Fall das Problem noch ein bisschen komplizierter als das, was wir
uns jetzt tatsächlich anschauen wollen. Hier sind ja nicht alle Strecken gleich lang. Wahrscheinlich ist hier, wenn es hier eine Autobahn gibt, gibt es nur einen Knoten pro Abfahrt bzw.
Auffahrt. Und dann macht man keine Knoten dazwischen jeden Meter oder so. Das wäre Quatsch. Das heißt, man hat hier Längen bzw.
Fahrzeiten an den Kanten stehen. Die Gesamtlänge eines solchen Weges durch den Graphen wäre dann die Summe aller Kantenlängen, die auf diesem Weg liegen bzw. aller Fahrzeiten,
die ich bräuchte, um von einem Knoten zum nächsten zu kommen. Und diese Fahrzeiten können sich ja dann je nach Verkehrssituation auch mal verändern.
Wir schauen uns jetzt aber ein Problem an, was ein bisschen einfacher ist. Da sagen wir einfach, die Länge von Wegen ist nicht irgendwie mit Fahrzeiten oder so gekoppelt,
sondern wir zählen wie viele Kanten auf dem Pfad liegen. Und das soll dann unsere Länge sein. Das hier wäre jetzt ein Beispiel, was unserem Problem vielleicht ein bisschen näher liegt.
Das ist ein Schnellbahnnetz. Und jeder Knoten hier ist eine Haltestelle. Und die Kanten dazwischen sind dann also die Wege zwischen den Haltestellen,
die dann die u-Bahn fahren. Und wir suchen jetzt nach Wegen von einer Stelle irgendwo anders hin, wo wir möglichst wenig diese u-Bahn-Strecken fahren müssen.
Also möglichst wenig Kanten zwischen A und B sind. Bei einem Netz wie diesem hier ist das relativ einfach. Das ist nämlich hier
im Wesentlichen ein Baum. Da gibt es keine Zyklen und alternativen Routen. Normale Streckenführungen von u-Bahnsystemen sind aber nicht so aufgebaut. Ich habe ganz
schön lange gesucht, bis ich sowas gefunden habe. Und wo bin ich fündig geworden? Ja, in Bielefeld. Und Sie können sich jetzt selber überlegen, was das über die Wahrscheinlichkeit aussagt,
dass es Bielefeld wirklich gibt. Ein baumförmiges u-Bahn-Netz. Sehr realistisch. Wer denkt sich bloß so einen Quatsch aus?
Nürnberg. Okay, das wundert mich jetzt. Ich dachte, Nürnberg würde es wirklich geben. Normalerweise sieht ein Streckennetz eher so aus.
Da kann man dann diese Bahn nehmen oder diese Bahn nehmen, um von hier nach dort zu kommen. Man kann sogar immer im Kreis fahren, wenn man darauf Lust hat. Und dann wird das Ganze natürlich
ein bisschen spannender. Wir nehmen das Problem noch mal genau, also als Graphenproblem, gegeben. Ein Graf, hier ist wieder ein schöner Beispiel-Graf. Und wir nehmen jetzt einen Knoten
heraus und sagen, das sei unser Startknoten s und einen zweiten Knoten. Und da wollen wir hin. Das ist der Zielknoten z und sagen wir mal der Knoten hier, dieser Knoten F, der sei jetzt unser Ziel.
Und gesucht ist jetzt der kürzeste Pfad von diesem Startknoten A zu diesem Zielknoten F. Und man sieht, direkt komme ich nicht hin, es gibt also keine Kante
von A nach F. Aber immerhin gibt es Pfade. Denn wir wissen ja schon aus seinem letzten Video, dass das F tatsächlich in der Menge der erreichbaren Knoten von A aus liegt.
Und die Länge eines Pfades ist definiert als die Anzahl der Kanten auf dem Pfad. Wir müssen uns jetzt also nur die Pfade mal anschauen und dann zählen,
wie lang die sind. Also eine Möglichkeit von A nach F zu kommen wäre folgendes. Ich laufe hier lang über B, dann über C, dann über D und dann bin ich am Ende bei F.
Und dann ist die Länge von diesem Pfad eben eine Kante, zwei Kanten, drei Kanten, vier Kanten. Das heißt, die Länge ist vier. Es
gibt aber noch eine andere Möglichkeit. Ich kann natürlich auch über E laufen. Das heißt, ich kann hier laufen, A, dann E und dann F. Und dieser
Weg hat eine andere Länge. Da sind nur zwei Kanten drin. Das heißt, der hat Länge zwei. Ob es also überhaupt einen Pfad vom Startknoten zum Zielknoten im Graphen gibt,
das ist das Erreichbarkeitsproblem. Damit haben wir uns schon im anderen Video beschäftigt. Das ist gelöst. Aber was der kürzeste Pfad ist von s nach z, das ist was Neues.
Und damit wollen wir uns jetzt beschäftigen. Und wie lösen wir das Problem nun? Na ja, wieder mit Traversieren. Das heißt, wir laufen durch den Graphen von Knoten zu Knoten entlang der Kanten.
Und zwar fangen wir mit dem Startknoten an und entdecken von dort weitere Knoten, die man direkt über die Kanten erreichen kann. Von dort wieder Knoten und so weiter und so weiter. Und wir merken
uns dann zu jedem Knoten, den wir entdeckt haben. Zum einen, ob wir ihn entdeckt haben oder nicht. Das kennen wir schon. Das war auch schon in einem anderen Video wichtig,
damit wir nicht immer im Kreis laufen und wieder die selben Knoten nochmal neu entdecken. Und das haben wir da gemacht mit einer Menge, die wir visited genannt haben. Und
dann haben wir immer jeden Knoten, den wir uns schon mal angeschaut haben, dort reingeworfen. Und außerdem merken wir uns jetzt auch für jeden Knoten, wie weit denn der kürzeste Weg von s zu
diesem Knoten ist. Das sieht jetzt vielleicht auf dem ersten Blick erstmal nach ganz viel unnötiger Zusatzarbeit aus. Wir wollten ja eigentlich nur wissen, wie lang der kürzeste Pfad von s nach z
ist. Und jetzt rechnen wir aber kürzeste Pfade von s zu allen erreichbaren Knoten im Graphen. Es stellt sich aber nun leider heraus, dass es schwierig ist, nur die Länge des kürzesten Pfades
von s nach z zu berechnen. Denn wir brauchen dazu zumindest die Längen der kürzesten Pfade von allen Knoten, die auf diesem kürzesten Pfad von s nach z liegen. Und da wir am Anfang gar nicht wissen,
welche Knoten das sein könnten, brechen wir eben das hier. Und wenn wir das haben, haben wir natürlich dann auch, wenn das z erreichbar ist, auch die Länge des kürzesten Pfades von s nach z.
Und Sie haben vielleicht schon bemerkt, wir berechnen jetzt erstmal nur die Länge des kürzesten Pfades. Und wenn wir die dann haben, dann fragen wir uns wieder, wie ist
denn nun der kürzeste Pfad? Und die Antwort ist so ähnlich wie in den anderen Optimierungsaufgaben, die wir in dieser Veranstaltung gemacht haben. Da benutzt man dann ein Traceback.
Diese Länge des kürzesten Pfads von s nach v wollen wir uns für jeden Knoten v merken in einer Map. Und die nennen wir Dist. Eine Map ist ja eine Abbildung von Keys auf Values. Und die Keys sind
in diesem Fall also die Knoten und die Values sind die Pfadlängen von s zu den jeweiligen Knoten. Und das Schöne an dem Ansatz ist, ich brauche, wenn ich Dist habe, wenn ich diese Map Dist habe,
nicht noch zusätzlich eine Visited Menge, weil das Dist ist ja selber an sich schon eine Menge. Und wenn ich jetzt einen neuen Knoten gefunden habe und ich habe ihn vorher noch nie gesehen,
dann erkenne ich das einfach darin, dass er noch keinen Eintrag in Dist hat. Und damit wir ein bisschen netter mit diesen Maps umgehen, verwende ich jetzt hier noch so ein bisschen
schönere Notation für die Zugriffsfunktion von der Map. Statt hier zu schreiben m. z key, value, schreibe ich das so. m von key und dann ein Zuweisungsfile value. Das heißt
Value wird jetzt reingeschrieben an der Stelle m von key. Und wenn das m von key schon vorher drin war, wird der Wert geändert und wenn es noch nicht drin war,
wird eben ein neues Paar key, value in die Map eingefügt. Und statt x wird zugewiesen m. getKey, also das ist die Get-Funktion der Map,
schreibe ich das einfach so. Also einfach m und dann Eckegeklammer auf, Key Eckegeklammer zu. Ich verwende die Map also sozusagen als eine Art Array, wobei allerdings der random access
nicht über Indexposition i läuft, also Position in einem Array, sondern eben über diesen Key. Diese Notation ist im Übrigen der Grund, warum man die Map auch assoziatives Array nennt. Das
ist eben, wenn man es so hinschreibt, ein bisschen wie eine verallgemeinerte Form von einem Array. Dann lassen Sie uns jetzt erstmal die Grundidee des Algorithmus aufschreiben,
der jetzt den kürzesten Pfad sucht. Also wir definieren am Anfang eine Map, nämlich Dist sei eine Map von Knoten zu Pfadlängen und am Anfang soll sie leer sein.
Und dann können wir aber bereits die Distanz von einem Knot in dem Graphen angeben, nämlich von s und die Distanz von s zu sich selbst ist nämlich Null. Wir sind ja schon da und deswegen brauchen
wir gar keinen Pfad zu laufen. Und jetzt kommt der eigentliche Algorithmus und wie der genau aussehen muss, das sehen wir uns dann gleich an. Jetzt wird traversiert von s ausgehend,
traversiere ich den Graphen und werde während ich das mache auch Dist entsprechend verändern. Da müssen wir gleich nochmal drüber reden, das markiere ich jetzt erstmal mit To Do,
das heißt, da muss ich noch was tun. Wenn ich dann mal fertig bin, wenn ich den ganzen Graphen traversiert habe, habe ich auch dieses Dist fertig ausgerechnet.
Das heißt, dann weiß ich, wie lange der kürzeste Pfad von s zu jedem Knoten ist, der erreichbar ist. Und da muss ich aber jetzt prüfen, ist den Dist überhaupt erreichbar?
Und das finde ich heraus, indem ich mir anschaue, ob denn in Dist tatsächlich der Zielknoten z eingetragen ist. Das heißt, ob Dist Punkt
Hesky von z gilt. Und wenn das der Fall ist, dann haben wir Dist ja einmal erreicht und eine Distanz eingetragen. Und in dem Fall können wir Distanz einfach zurückgeben.
Dann schreibe ich hier Return Dist von z und ansonsten ist es eben nicht erreichbar. Ich komme von s also niemals zu z und dann kann ich eine kleine Fehlermeldung ausgeben.
So, jetzt bleibt natürlich nur das Wichtigste zu klären, nämlich wie traversieren wir denn den Graphen? Und die erste Idee ist jetzt natürlich Tiefensuche.
Haben wir letztes Mal ja auch gemacht, hat funktioniert, probieren wir doch gleich mal aus. Das heißt, wir streichen jetzt hier diese Zeile und rufen stattdessen Algorithmus
auf. Und den könnten wir zum Beispiel Dist DFS nennen. DFS Depth First Search, also Tiefensuche. Und dem übergeben wir jetzt zum einen den Knoten, den Startknoten s. Da geht jetzt unsere Suche los.
Und das wird, wenn es dann sich nachher rekursiv aufruft, immer wieder der nächste Knoten sein, den wir gefunden haben. Und dann übergeben wir auch noch die Map Dist, damit der
Algorithmus dann in Dist die entsprechenden kürzesten Weglängen mit protokollieren kann. Und den Algorithmus Dist DFS schreibe ich jetzt hier unten hin. Also, was machen wir denn bei der
Tiefensuche? Wir haben einen Knoten v gegeben und jetzt schauen wir uns an, was für weitere Knoten können wir denn von v aus erreichen. Also, for each u mit, es gibt eine Kante von v nach u.
Und um jetzt Zyklen zu vermeiden, dass wir uns in einem Zyklus gefangen nehmen lassen und dann nie enden, müssen wir jetzt erstmal prüfen, ist denn u schon bekannt. Und wenn also u schon bekannt ist,
dann heißt das, wenn Dist bereits einen Key u hat, also if Dist has Key von u, dann wissen wir, da müssen wir nicht mehr rein. Aber wenn das nicht der Fall ist,
wenn also not Dist has Key von u ist, dann ist das u noch nie entdeckt worden und dann können wir jetzt eintragen die Distanz. Und das machen wir so.
Dist von u setzen wir auf Dist von v plus 1. Warum das? Wir sind gerade in Dist von v drin, wissen also schon die Distanz von s nach v. Und jetzt kommen wir ja über eine Kante von v nach u.
Wenn wir jetzt den ganzen Weg nehmen, nämlich von s über v nach u, dann ist das hier die Weglänge, die wir dann eben benutzt haben. Und ansonsten müssen wir, nachdem wir das gesetzt haben,
natürlich den rekursiven Aufruf starten. Das heißt, jetzt rufen wir hier Dist DFS von u, Dist auf. Und wenn wir das dann fertig haben, dann ist am Schluss von allen Knoten,
die überhaupt erreichbar sind, eine Distanz eingetragen in Dist und wir sind fertig. Prima, das ist jetzt ein sehr schöner, knapper Algorithmus,
hat nur einen Nachteil. Er funktioniert so nicht. Machen wir uns das an folgendem Beispiel klar. Hier haben wir den Startknoten s und hier ist der Zielknoten z.
Und nehmen wir mal an, dass in der Vor-Eats-Schleife in dem Algorithmus, die hier diese ganzen Kinder durchgeht, der Knoten A zuerst rankommt und dann der
Knoten B. Und dann würden wir zuerst also Knoten A entwickeln und dann machen wir ja Tiefensuche. Wir steigen erst mal in die Tiefe ab. Das heißt, hier geht es hin,
hier geht es hin und dann kann ich ja mal an die Knoten die Distanzen anschreiben. Hier erst mal der Startknoten kriegt die Distanz 0 und dann A kriegt 1 und dann geht es hier weiter
mit 2, 3 und so weiter. Und dann bin ich hier bei dem Knoten C und dann finde ich heraus, die Distanz zu z ist eben 12. Und wenn jetzt das wieder zurückkommt,
dann sind die ganzen rekursiven Aufrufe fertig, dann kommt hier als nächstes noch das B und da steht dann 1 drin. Bei dem Graph ist noch alles okay,
aber jetzt stellen Sie sich vor, es gibt hier noch eine weitere Kante von B nach C. Und dann ist die Distanz ja eigentlich nach C 2 und nicht 11. Das Problem ist aber,
das merke ich nicht, denn nehmen Sie mal an, wir sind jetzt hier in dem Knoten. Das heißt, wir haben jetzt gerade Dist DFS von B, Dist aufgerufen und dann macht
ihr hier die Schleife und ihr findet also einen weiteren Knoten, das ist der Knoten C, den er erreichen kann. Aber dann prüft er nach, ist denn Dist Punkt HES-KEY von dem Knoten C.
Und tatsächlich, der Knoten C, er hat ja bereits einen Eintrag, er hat ja eine 11. Und weil da ein Eintrag drin ist, sagt er sich, okay, dann überspringe ich den und rufe nicht noch einmal
Dist von C auf. Das Problem ist also, dass sobald ich hier einmal von einem Knoten die Distanz gesetzt habe in der Map Dist, dass ich dann diesen werde nie wieder ändere. Ich trage
sozusagen bei jedem Knoten die Länge des ersten Weges ein, den ich finde von s zu diesem Knoten, aber nicht die Länge des kürzesten Weges und die wollte ich ja gerne haben.
Wie kann ich den Algorithmus jetzt korrigieren, damit er doch wieder funktioniert? Ich muss mir hier anschauen, was passiert, wenn ich hier einen Knoten u finde und der aber schon einmal entdeckt
worden ist. Bisher sage ich, okay, kenn ich schon, gehe ich nicht wieder hin. Das ist aber falsch. Ich muss jetzt schauen, habe ich denn jetzt vielleicht einen kürzeren Weg zu
ihm gefunden als vorher. Das heißt, ich muss als zweiten Fall hier reinsetzen, denn Dist von v plus eins ist ja jetzt die Länge des Weges von s über v nach u. Und
das ist jetzt sozusagen die Länge des neu gefundenen Weges. Ich habe jetzt u entdeckt über den Knoten v und wenn das jetzt hier kleiner ist als der kürzeste Weg,
den ich bisher gefunden habe, der steht in Dist von u drin, dann muss ich das hier neu setzen. Ich habe also jetzt zwei Gründe, warum ich hier den Distwert von einem Knoten u verändere.
Entweder habe ich ihn zum ersten Mal entdeckt, dann trage ich die Distanz ein von dem Weg, wie ich da zum ersten Mal hingekommen bin oder ich bin jetzt auf einem anderen Weg
hingekommen und dann bin ich hier in dem Fall zwei und da muss ich eben eventuell, wenn der neue Weg kürzer ist, das Dist hier verändern. Und das würden wir dann in dem
Fall tun. Wir kommen also von hier, hier ist v, dann entdecke ich hier den Knoten C, das ist das u und dann stelle ich fest, ja, die Distanz von v plus eins, das ist also hier eine 1,
Distanz von B ist eins, plus eins, also diese Kante hier, nach C, das ist zwei, das ist ja tatsächlich kleiner als das Dist von u, u ist dieser Knoten C hier und da steht im Moment
11 drin, das heißt jetzt muss ich den Wert 11 hier wegschmeißen und stattdessen eine 3 einfügen. Jetzt können Sie hier sehen, warum das noch nicht ausreicht. Ich habe zwar Dist von C korrigiert,
das ist jetzt der richtige Wert, aber das ändert natürlich noch nichts an der Distanz von s nach z, die ich bisher gefunden habe. Ich muss jetzt also in dem Moment, in dem ich einen kürzeren Weg
zu diesem Knoten C gefunden habe, schauen, ob ich von dort aus auch kürzere Wege zu weiteren Knoten finde und das ist tatsächlich auch der Grund, warum ich im Algorithmus an dieser Stelle
tatsächlich auch noch mal den rikursiven Aufruf starten muss. Es reicht eben nicht aus, hier nur die Distanz zu korrigieren, ich muss jetzt auch sämtliche von dem Knoten u aus erreichbaren
Knoten noch einmal abprüfen, um zu sehen, gibt es denn jetzt dahin auch noch mal kürzere Wege. Und wenn ich das dann mache, dann finde ich hier den Knoten z und kann sagen, ja da gibt es auch
einen kürzeren Weg hin, das ist dann vier und das ist dann tatsächlich die korrekte Lösung. Jetzt müssen wir unbedingt mal über Laufzeiten reden, das haben wir bisher noch gar nicht gemacht,
müssen wir jetzt nachholen, hier noch mal der Algorithmus aus dem anderen Video, der einfach eine tiefen Suche macht, um herauszufinden, welche Knoten denn überhaupt
erreichbar sind vom Startknoten. Und wir nennen mal die Anzahl der Knoten, die Gesamtzahl der Knoten im Graphen n und die Gesamtzahl der Kanten im Graphen, also alle Kanten
zusammengenommen soll M sein. Und dann können wir mithilfe von n und M diese Laufzeit abschätzen. Es ist ja so, dass DFS durch diesen Einsatz dieser Menge visited dafür gesorgt hat, dass
jeder Knoten im Graph höchstens einmal aufgerufen werden kann. Der Algorithmus DFS wird für jeden Knoten aufgerufen, der von s aus erreichbar ist. Das ist ja eine Untermenge aller Knoten,
die es im Graphen gibt. Und deswegen ist die Zahl der Aufrufe von DFS insgesamt durch n beschränkt. Die Zahl der DFS-Aufrufe kennen wir jetzt. Also jetzt ist die Frage,
wie viel Zeit braut der DFS-Aufruf für sich mal, abgesehen von den rekursiven Aufrufen, die da noch dran hängen. Und das hängt eben dann für jeden Knoten davon ab,
wie oft diese Vor-Itschleife durchlaufen wird. Die hängt also von dem Grad jedes Knotens ab. Die Zahl der Knoten u, die ich von v, also über Kanten erreiche, ist ganz einfach die Zahl der
Kanten, die von v abgehen. Und jetzt schaue ich mir an, wie viele solche Schleifendurchläufe dieser Vor-Itschleife gibt es denn insgesamt über alle Aufrufe von DFS hinweg. Ja, so viele,
wie es eben Kanten in dem Graphen gibt. Jede Kante wird bei dieser Vor-Itschleife einmal angeschaut. Und das sind insgesamt samt M. Also ist die Laufzeit von diesem Algorithmus O von n, das
ist die Einzahl der DFS-Aufrufe, plus M, das ist die Gesamtzahl dieser Vor-Itschleifendurchläufe und damit auch dieser Lookups hier in der visited Menge, die ich machen muss. Im worst case habe ich
es mit einem Graphen zu tun, wo jeder Knoten mit jedem anderen Knoten über eine Kante verbunden ist. Dann habe ich n² viele Kanten und dann wird das hier zu O von n plus n², also zu O von n².
Schauen wir uns jetzt also den Algorithmus des DFS an, den wir eben zur Traversierung, zur Bestimmung des kürzesten Weges benutzt haben. Und da sehen wir gleich das Argument, was wir eben noch
anwenden konnten, nämlich zu sagen, die Anzahl der Aufrufe, die durch die Anzahl der Knoten beschränkt ist, gilt jetzt nicht mehr. Es kann sein, dass wir das DFS für einen Knoten mehrfach
aufrufen müssen. Und überlegen wir uns mal, wie da ein worst case Beispiel aussehen könnte. Also mal angenommen, im Graphen sind die Knoten so verteilt da ganz am Anfang, das ist der erste
Knoten, das ist unser Startknoten und dann geht es jetzt zum zweiten, dritten, vierten und so weiter, eine lange Kette bis am Schluss. Hier der Ende Knoten ist, das ist unser Zielknoten. Und dann
ist, wenn wir hier den Algorithmus aufrufen, nachher die Distanz von z natürlich gleich n. Und nun fügen wir aber noch weitere Kanten hinzu, die das Ganze interessanter machen.
Und zwar sagen wir, am Anfang entdecken wir hier diese blauen Kanten und dann gibt es aber hier eine Abkürzung zum dritten Knoten und dann stellen wir fest, ja eben dachten wir noch,
hier wäre der Abstand zwei, aber jetzt entdecken wir die grüne Kante und sehen, der Abstand ist in Wirklichkeit eins. Und dann müssen wir sämtliche Abstände hier nochmal
anpassen und am Schluss sehen wir, aha, Abstand zu z ist eben nicht n, sondern n minus eins. Und das können wir noch weiterführen. Wir sagen, danach entdeckt er dann diese Kante hier.
Und die stellt fest, dass hier der Abstand auch eins ist und nicht zwei, wie er vorher dachte. Und dann muss er wieder alles anpassen und dann ist am Schluss die
Distanz zu z eben n minus zwei und so weiter. Das heißt, wir bauen jetzt hier immer weiter noch zusätzliche Kanten von s zu den Knoten ein, die dann immer nochmal dafür sorgen,
dass ich dann nochmal und nochmal und nochmal die Knoten mir anschauen muss. Am Schluss habe ich dann den Startknoten und diesen zweiten Knoten hier einmal in DsDfs aufgerufen.
Für den hier habe ich schon zweimal DsDfs ausgerufen, für den dreimal, für den viermal und so weiter. Das heißt, die Gesamtzahl der DsDfs-Aufrufe bei diesem
Graphen ist O von n². Natürlich nur, wenn ich die Kanten in einer ungünstigen Reihenfolge durchlaufe bei den For-Each-Schleifen. Was die reine Anzahl der DsDfs-Aufrufe anbelangt,
sind wir mit dem Beispiel schon gut in Richtung Worst-Case-Beispiel unterwegs. Nur die Laufzeit geht noch schlimmer und das liegt daran, weil abgesehen von diesem ersten Knoten,
von dem Startknoten, die gerade aller Knoten in diesem Graph ja nur eins ist. Das heißt, von jedem bekommen wir nur eine ausgehende Kante. Der z hat noch nicht mal
eine ausgehende Kante. Das bedeutet, dass diese For-Each-Schleife also nicht so viel zu tun hat. Die läuft höchstens einmal durch und das können wir ändern, wenn wir den Algorithmus noch ein
bisschen langsamer machen wollen, indem wir dafür sorgen, dass da ordentlich Kanten sind, die er sich anschauen muss. Zum Beispiel, indem wir von jedem Knoten auf alle Vorgängerknoten
eine Kante einfügen. Und eben nicht nur zu jedem direkten Vorgänger, sondern zu allen davor auch. Das wird jetzt ganz schön unübersichtlich.
So und am Ende sieht das dann also so aus. Wir haben hier von jedem Knoten zu allen Vorgängerknoten,
also allen Knoten, die hier in der Reihe davor sind, noch eine Kante. Und je weiter wir hier nach hinten kommen in der Liste der Knoten, desto häufiger werden bei diesen Knoten, wird bei diesen
Knoten des DFS aufgerufen zum einen und desto mehr habe ich auch zu tun bei dieser For-Each-Schleife hier. Wobei ich bei den meisten Fällen dann keinen kürzeren Weg finde, aber das macht nichts aus.
Ich habe jetzt hier einfach Arbeit. Und insgesamt heißt das also, ich habe O von n² viele Aufrufe und jeder hat nochmal n zu tun. Das heißt insgesamt
habe ich hier dann eine Laufzeit von O von n hoch 3. Nun bin ich mir nicht ganz sicher, ob das tatsächlich buchstäblich das Worst-Case-Beispiel für diesen Algorithmus ist.
Aber es ist schon ziemlich schlecht der Fall. Deswegen schreibe ich hier dann also Bad-Case-Beispiel. Tatsache ist, dass O von n hoch 3 tatsächlich
eine obere Laufzeit-Schranke für den Algorithmus darstellt. Denn die Anzahl der Aufrufe des DFS, die hier insgesamt getätigt werden, ist tatsächlich durch O von n² beschränkt.
Ich rufe ja nur dann den Algorithmus mit einem Knoten u auf, wenn ich ihn entweder noch nie gesehen habe. Davon gibt es maximal O von n viele Aufrufe,
denn es gibt ja nur n Knoten. Und außerdem rufe ich ihn auf, wenn ich einen kürzeren Weg gefunden habe. Nun ist die maximale Länge, wenn ich Zahlen von Kanten zähle, von einem Knoten
zu einem anderen Knoten beschränkt durch die Menge der Knoten, also durch O von n. Diese Weglänge wird jetzt bei jedem Aufruf um 1 kleiner. Das heißt,
das kann höchstens n mal passieren. Jeder einzelne Knoten wird also höchstens n mal dem DFS übergeben. Und insgesamt sind das n Knoten also insgesamt höchstens n² viele Aufrufe.
Da darüber hinaus, zum Beispiel in einem vollständig verbundenen Graphen, wo jeder mit jedem Knoten verbunden ist, die Zahl der Schleifendurchläufe pro Aufruf ebenfalls
durch n beschränkt ist, ergibt sich also eine Worst-Case-Laufzeit von n². Und wir sehen an dem Beispiel, diese Abschätzung ist tatsächlich auch eng. Das heißt, es gibt tatsächlich Graphen,
die so eine Laufzeit dann produzieren. Eine Laufzeit von n hoch 3 finde ich nicht gut. Das wollen wir jetzt noch verbessern. Und zwar wollen wir das dadurch erreichen, indem wir dafür
sorgen, dass die Knoten nicht mehrfach untersucht werden. Mit untersucht meine ich, dass wir uns die Knoten anschauen und sehen, welche anderen Knoten wir davon erreichen können. Die Strategie,
die wir also hier suchen, soll greedy sein, sie soll gierig sein, sie soll dafür sorgen, dass wenn wir einen Knoten einmal untersucht haben, wir danach ihn nie wieder untersuchen müssen.
Und um das zu erreichen, müssen wir unbedingt wegkommen von der Tiefensuchen-Strategie, die ja einfach wild losläuft und weiter, weiter, weiter immer in die Tiefe geht und erst wenn
sie zurückkommt, dann sieht, dass es da noch kurze Wege irgendwo hingegeben haben könnte. Wir müssen stattdessen langsam vorgehen, von dem Startknoten die Grenzen immer weiter ausweiten,
immer entferntere Knoten entdecken. Nehmen wir uns als Beispiel nochmal diesen schönen Graphen vor und zwar als Startknoten nehmen wir das A und dann wissen wir schon die Distanz von A zu A,
die ist ja Null. Und nun gucke ich mir an, welche Knoten kann ich denn direkt vom Startknoten aus erreichen und das ist B, E und H.
Und diese drei Knoten haben deswegen eine Distanz von jeweils eins. Und nun schaue ich mir an, welche Knoten ich denn von diesen Knoten hier B, E und H erreichen kann und das ist zum einen
das C und zum anderen das F und dann weiß ich auch schon, was die für eine Distanz haben, nämlich jeweils zwei. Jetzt schaue ich mir an, was kann ich denn von diesen Knoten C
und F erreichen? Na, zum einen der Knoten D und dann kann ich von F auch noch E erreichen und B. E und B habe ich jetzt schon, Distanzen, das werde ich nicht mehr verändern,
aber D ist Null, das heißt jetzt weiß ich die Distanz zu D. Und von D kann ich jetzt nichts Neues mehr erreichen, das heißt das sind tatsächlich jetzt
die Distanzen aller erreichbaren Knoten. G, i, J und K sind ja von A aus gar nicht erreichbar und kriegen deswegen auch keinen Distanzwert. Was ich also tue ist, ich fange
bei dem Startknoten an und dann lasse ich den Abstand größer wachsen, mehr und mehr werden. Am Anfang ist nur der Startknoten drin. Wenn ich jetzt die Grenze ausweite,
sodass sie auch die Knoten beinhaltet, die in Abstand eins haben, dann sind eben auch die Knoten B, E und H mit in dem Bereich. Und wenn ich dann den nächsten Ausweitungen mache, dann
ist auch noch C und F mit drin. Und die letzte Phase wurde dann auch noch das D mit beinhalten. Die Art der Traversierung, die wir uns jetzt also anschauen können,
hat den Namen Breitensuche auf Englisch Breath First Search, BFS und es bedeutet erst sind die Geschwister dran, bevor dann die Kinder dran kommen. Und die Methode, wie wir dafür sorgen,
dass die Knoten in dieser Reihenfolge aufgerufen werden, ist die, dass wir sie in eine Warteschlange eintragen. Da kommen sozusagen alle Knoten rein, die wir bereits entdeckt haben,
aber die wir noch untersuchen müssen. Und die Warteschlange sorgt dafür, dass es fair zugeht, dass nicht schon die Kinder und Kindeskinder und so weiter dran kommen, bevor ein Geschwisterkind
dran kommt, sondern dass die in der Reihenfolge ihrer Entdeckung aufgezählt werden, die Knoten und es stellt sich heraus, dass es genau dann die Reihenfolge auch des Abstandes zum Startknoten.
Wir starten also mit demselben Algorithmus wie vorher, diesem Shortest Pass Algorithmus, der Dist anlegt und dann hier die Traversierung startet. Nur als Traversierungsalgorithmus
nehmen wir eben jetzt nicht Dist DFS, also die Tiefensuche, sondern wir nehmen jetzt hier einen Algorithmus und den nennen wir dann eben logischerweise Dist BFS,
also Breitensuch-Algorithmus. Und ich schreibe ihn hier unten hin. Und für alle unter Ihnen, die immer noch recursive Algorithmen nicht mögen, habe ich jetzt eine gute Nachricht.
Dist BFS wird ein iterativer Algorithmus sein. Wir beginnen damit, dass wir uns eine Q nehmen und die nennen wir To Do. Das wird unsere To Do Liste. Da stellen wir alle Knoten rein,
die wir schon entdeckt, aber noch nicht untersucht haben. Und am Anfang schreiben wir dort einfach erstmal das s hinein. Denn das s kennen wir ja schon,
aber wir haben uns noch nicht angeschaut, welche anderen Knoten wir von dort erreichen. Und nun beginnt die WILE-Schleife, die so lange durchläuft, solange noch was zu tun ist.
Wir laufen jetzt also durch diese Schleife und jedes Mal bei jedem Schleifendurchlauf nehmen wir uns einen Knoten aus der To Do Liste heraus und schauen mal,
welche weiteren Knoten wir über Kanten von diesem Knoten aus entdecken können. Und dazu verwenden wir einfach die Funktion POP. Und die sorgt eben jetzt dafür,
dass die Knoten in der richtigen Reihenfolge ausgewertet werden, nämlich in der Reihenfolge, in der sie hineingesteckt worden sind. Und für jeden Knoten v schauen wir uns nun an, welche
Knoten u können wir denn von v aus erreichen. Also for each u mit es gibt eine Kante von u nach v. Mit dem Knoten u machen wir jetzt im Grunde das gleiche, was wir auch vorher schon in der
Tiefensuche gemacht haben. Wir prüfen nach, kenne ich den schon, war ich da schon mal. Wenn ja, dann ist er in die DIST-MAP eingetragen. Und wenn nicht, muss ich ihn mir eben anschauen.
Das ist Fall 1 und Fall 2 wäre jetzt eben, ich habe einen kürzeren Weg zu u gefunden, als bisher bekannt war. Also und wenn jetzt eine dieser Fälle aufgetreten ist, muss ich also die
Distanz von u neu setzen. Und da ich jetzt DIST von u gesetzt habe, heißt das, u ist ein Knoten, den ich mir jetzt noch mal anschauen muss. Das heißt, er kommt jetzt in die TODO-Liste hinein.
Und damit bin ich fertig. Den Algorithmus wollen wir jetzt kurz nochmal an diesem Graphen hier ausprobieren. Und wir protokollieren immer mit,
was in TODO drin ist. Am Anfang ist nur der Startknoten A. Das A war ja unser Startknoten in TODO drin. Und da nur A drin ist,
wird jetzt an dieser Stelle, wo wir TODO-POP aufrufen, das A rausgeholt. Das heißt, das streiche ich jetzt weg und ich entdecke dann aber alle Kinder hier.
Als nächstes werden also die drei Kinder B, E und H in die TODO-Liste eingetragen. Und gleichzeitig trage ich dann auch die Distanz zu diesen drei Knoten in DIST ein.
Bei A war die Distanz ja null und bei B, E und H war sie dann also entsprechend hier dieser Rechnung eben eins. Und ich habe hier alle drauf gepusht. Als nächstes käme jetzt das B dran.
Das B hole ich aus der TODO-Liste raus an dieser Stelle und schaue mir jetzt an, welchen Knoten kann ich von B aus alles erreichen. Und das ist das C. Das heißt,
jetzt weise ich die Distanz zu C, trage ich ein und ich hänge das C hinten in die Warteschlange rein. Als nächstes kommt dann das E dran.
Das E wurde herausgepoppt aus der Warteschlange und ich kann von dem E das F erreichen. Also F bekommt jetzt die Distanz 2 und muss sich hinten
in die Warteschlange anstellen. Jetzt ist H dran. H streiche ich einfach raus. Da gibt es keine Kante weg. Bin ich fertig? Dann kommt
als nächstes das C. Von dem C entdecke ich das D. Die Distanz vom D setze ich auf 3 und dann kann auch das D sich hinten reinstellen in
die Warteschlange. Nun ist F dran. Ich hole das F aus der Warteschlange raus und jetzt entdecke ich von F die beiden Knoten B und E. Und nun zieht aber gar nicht dieser Fall 2.
Das heißt, ich entdecke keine neuen Knoten und die, die ich schon entdeckt habe, haben eine kleinere Distanz. Das heißt,
es geht nicht weiter. Und am Schluss kommt dann D. Da würde ich dann das F entdecken. Das hat aber auch schon eine kleinere Distanz als 4. Das heißt, es geht auch nicht weiter.
Und vielleicht ist Ihnen das aufgefallen, zu keinem Zeitpunkt hat es geklappt, dass diese zweite Bedingung hier eingetreten ist. Es ist nämlich so, dass wir hier die Knoten genau
in der Reihenfolge ihres Abstandes zu s entdeckt und in die To-do-Liste hineingeschrieben haben. Und das sorgt dafür, dass wenn wir später noch mal zum Beispiel hier
vom F zu dem Knoten B zurückkommen würden, wir das nicht machen wollen, weil wir B ja schon vorher gesehen haben und er hatte deswegen eine kleinere Distanz,
als wir jetzt über den Umweg F hinkriegen können. Und das bedeutet, der Algorithmus ist greedy. Sobald wir einen Knoteneimer aus To-do herausgeholt haben, kommt er nie wieder
rein und wir können uns diesen zweiten Fall einfach komplett schenken. Der passiert nie. Und das hat noch eine weitere sehr hübsche Konsequenz. Die einzige Gelegenheit,
bei der wir Dist von u, also die Distanz von s zu einem Knoten u setzen, ist die, wenn wir u zum ersten Mal entdeckt haben. Dann setzen wir hier die Distanz und pushen
das u auf die To-do-Liste. Diese Distanz wird zu keinem Zeitpunkt später geändert. Das heißt, wir setzen sie einmal und dann bleibt sie so. Und das heißt,
sobald wir z entdeckt haben, wissen wir auch schon die Distanz nach z. Und so sieht er dann aus, Dist BFS, wenn man ihn richtig schön macht. Wir brauchen hier nur den Fall eins.
Das heißt, nur wenn u noch nicht entdeckt worden ist vorher, dann müssen wir hineingehen und das Dist von u berechnen. Und da wir dann schon die Distanz kennen, können wir hier dann eben schauen,
ob das u schon das z ist. Und dann, wenn es das ist, dann machen wir Return und dann steht in Dist von z eben die Distanz von s nach z. Kommen wir zur unvermeidlichen Laufzeitfrage.
Was ist denn die Laufzeit von dem Algorithmus? Nun, wir haben es ja jetzt geschafft, dass wir jeden erreichbaren Knoten nur einmal anschauen. Die Zahl der erreichbaren Knoten
ist maximal n. Das heißt, wir haben n mal hier Schleifendurchläufe durch diese While-Schleife. Und dann kann natürlich hier je nach Grad verschiedene, häufige Schleifendurchläufe von der
inneren Foid-Schleife sein. Das müssen wir aber nicht unbedingt multiplizieren, weil wir wissen, wie viel Foid-Schleifendurchläufe es insgesamt geben kann. Nämlich M-Fiele,
so viel wie es eben Kanten gibt. Denn hier wird ja jedes Mal eine Kante angeschaut. Wir schauen nach jeder Kante nur einmal an. Das heißt, wir haben insgesamt eine Laufzeit von O
von n plus M. Und das bedeutet, da ja M ja auch wieder durch n² abgeschätzt werden kann nach oben, dass das O von n² ist. Und das heißt, das ist schon besser als der DFS-Algorithmus.
Der hat ja n hoch 3, also kubische Laufzeit. Und hier haben wir jetzt im Worst Case quadratische Laufzeit. Und wenn das M sogar ein bisschen kleiner ist als n²,
das kann ja auch sein, dass der Graph ein bisschen weniger dicht ist, dann schaffen wir es sogar in n plus M. Zum Abschluss des Videos schauen wir uns noch ein Beispiel an,
wie die Breitensuche die Knoten in einem Baum aufzählen würde. Und es ist ganz einfach. Wir hatten ja vorhin schon diese gestricheten Gebiete gekennzeichnet.
Und hier ist es genauso. Nur müssen wir eben die Striche hier quer über den Baum laufen lassen. Und aufgezählt werden jetzt die Knoten ebenenweise. Also wir fangen an mit A
und dann kommt B, C und dann kommt E, D, H und am Schluss F und G. Und das Einzige, worauf ich hier ein bisschen aufpassen muss, ist, dass ich mit der Reihenfolge nicht durcheinander
komme. Wenn ich also von A aus zuerst B und dann C entdecke, dann muss ich in der nächsten Ebene auch zuerst die Kinder von B entdecken, also zuerst E und D aufzählen und dann erst diesen Knoten H.
Und dann kommt am Schluss eben noch F und G dazu. Sie haben nun die beiden Traversierungsmethoden Tiefensuche und Breitensuche kennengelernt. Und das sind zwei sehr nützliche Methoden,
mit denen man viele Probleme über Graphen oder auch auf Bäumen lösen kann. Und es ist gut, dass Sie beide Methoden kennen, denn manchmal ist die Tiefensuche besser geeignet als die Breitensuche.
Und manchmal, wie wir hier gesehen haben bei dem kürzesten Fahrtproblem, ist die Breitensuche etwas nützlicher als die Tiefensuche.

Zum Nachlesen

BreitensucheBreitensuche (englisch breadth-first search, BFS) ist ein Verfahren in der Informatik zum Durchsuchen bzw. Durchlaufen der Knoten eines Graphen. TiefensucheTiefensuche (englisch depth-first search, DFS) ist in der Informatik ein Verfahren zum Suchen von Knoten in einem Graphen. Sie zählt zu den uninformierten … Dijkstra-AlgorithmusDer Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy-Algorithmen und löst das Problem der … Bidirektionale SucheIn der Informatik zählt die Bidirektionale Suche zu den Suchverfahren, spezieller zu den uninformierten Suchverfahren. Wie der A*-Algorithmus und der …