So, guten Tag, meine Damen und Herren, herzlich Willkommen, Vorlesung
Algorithmen 1.
Wenn wir nochmal zurückschauen auf die letzte Vorlesung vorgestern, da
hatten wir uns nochmal abschließend mit den AB-Bäumen beschäftigt, die
es eben erlauben, eine sortierte Datenstruktur mit einer darauf
aufgebauten Such-Datenstruktur aufzubauen, wobei die Bäume eben
balanciert waren, indem wir den Knotengrad für jeden inneren Knoten
anpassen konnten, sodass der zwischen A und B Kindern enthält und
damit konnten wir eben einen Großteil der Operationen, die wir auf
sortierten Folgen durchführen, also Suche, Einfügen, Löschen von
Elementen in logarithmischer Zeit in der Anzahl der Elemente
durchführen.
Gut, dann hatten wir uns auch noch beginnend in der letzten Vorlesung
bereits mit Graphen beschäftigt und das werden wir auch heute
fortsetzen.
Also Thema heute Graphen nochmal, welche Datenstrukturen sind zur
Repräsentation geeignet?
Und dann werden wir uns mit wesentlichen Algorithmen auf Graphen
beschäftigen.
Das sind in dem ersten Schritt Graftraversierungsalgorithmen, also wie
kann ich einen Graph durchlaufen, um sämtliche Knoten zu besuchen?
Und da gibt es eben verschiedene Varianten, zum Beispiel die
Breitensuche oder auch die Tiefensuche, zu der wir eventuell heute
auch noch kommen.
Okay, also es geht um Graphen.
Graphen, die Datenstruktur, um Abhängigkeiten zwischen Elementen
darzustellen.
Also Sie haben eine Menge von verschiedenen Dingen, über die Sie reden
wollen, also zum Beispiel Personen und Sie haben Abhängigkeiten
zwischen diesen Personen.
Das kann Organisationsstruktur in einem Unternehmen sein oder
Bekanntschaftsbeziehungen oder Sonstiges, die lassen sich dann eben
als Verbindungen oder als eine Relation zwischen den Elementen,
zwischen den Personen zum Beispiel ausdrücken.
Und dazu sind eben solche Graphen, Datenstrukturen sehr gut geeignet.
Gut, wir hatten uns dann schon überlegt, also es gibt gerichtete und
ungerichtete Graphen, es gibt Kantengewichte und vielleicht auch noch
Knotengewichte oder Knotenattribute, die wir dazufügen wollen.
Und wir haben uns überlegt, wie können wir solche Graphen jetzt auf
unserer Maschine repräsentieren und hatten dazu eine erste Variante,
die ganz einfach war, nämlich diese Kantenfolgenrepräsentation, uns
angeschaut, wo wir einfach die Kanten, die in einem Graph vorkommen,
in einer beliebigen Reihenfolge hintereinander schreiben, in eine
Sequenz.
Die Knoten sind dadurch implizit gegeben, das heißt, alles, was eben
in einer Kante hier auftaucht, als Knoten bezeichnet, definiert uns
dann einen neuen Knoten.
Und das ist eine sehr einfache Datenstruktur, aber sie erlaubt eben
keinen besonders strukturierten Zugriff auf die Daten.
Also wenn ich jetzt zum Beispiel herausfinden möchte, was sind die
ausgehenden Kanten von allen gegebenen Knoten, zum Beispiel U, dann
ist es hier relativ schwierig, auf dieser Darstellung das
durchzuführen, weil wir eben alle Kanten eigentlich immer durchgehen
müssen, diese ganze Liste, um das herauszufinden.
Und es ist in vielen Fällen nicht sonderlich effizient.
Dann hatten wir uns eine andere Darstellung angeschaut, die
Darstellung von Graphen über Adjacenzfeldern.
Über Adjacenzfelder, da hatten wir dazu zwei Arrays.
Einmal hatten wir ein Array, wo die Indizes, die den Knoten wieder
entsprechen, also hier zum Beispiel 1, 2, 3, 4, das wären die Indizes
der Knoten.
Und hier unten haben wir ein Array, in dem die Kanten repräsentiert
sind und die Kanten sind jeweils eben über die Endpunkte der Kante
repräsentiert.
Genau.
Und diese Kanten sind immer so gruppiert, dass alles, was zu einem
Knoten gehört, also was die ausgehenden Kanten von einem Knoten sind,
die werden hintereinander in diesem Kantenarray abgelegt.
Und was wir dann eben noch in dieser Datenstruktur benötigen, ist,
dass wir so eine Grenze benötigen, wo fängt jetzt die Zielpunkte der
Kanten an, vom nächsten Knoten und was gehört noch zum
Vorgängerknoten.
Also wir haben hier Kanten, die gehören zum ersten Knoten, dann haben
wir von hier bis hier Kanten, die gehören zum nächsten Knoten.
Und was unsere Datenstruktur V jetzt eben abspeichert, ist genau diese
Grenzen, wo fangen die Kanten, die zum nächsten Knoten gehören an.
Also hier beginnen die Kanten für Knoten 1, hier in dem unteren
Kantenarray an Index 3 beginnen die Kanten für Knoten 2, an Index 5
beginnen die Kanten für Knoten 3 und so weiter.
Und mit dieser Darstellung haben wir schon eine etwas strukturiertere
Darstellung von Graphen, wo wir eben zum Beispiel sehr einfach jetzt
herausfinden können, was sind von einem Knoten die ausgehenden Kanten.
Also wenn wir zum Beispiel wissen wollen, von diesem Knoten 3, was
sind die ausgehenden Kanten, dann wissen wir, die Kantenziele sind
abgespeichert ab Index 5 in unserem Array E.
Bei 7 beginnt schon das nächste, also an 5 und 6 sind die Zielpunkte
der Kanten abgespeichert.
1, wenn wir dann abzählen, 1, 2, 3, 4, 5, 5 und 6, also hier 2 und 4
wären die Ziele von Kanten, die von Knoten 3 ausgehen.
Also das heißt, wir haben eine Kante von 3 nach 2 und eine Kante von 3
nach 4, wie wir hier auch sehen, 3 nach 2 und 3 nach 4 sind eben hier
die ausgehenden Kanten.
Also diese Darstellung ermöglicht uns schon mal etwas einfacher, auf
zum Beispiel ausgehende Kanten schnell zu finden.
Gut, dann hatten wir auch noch einen Algorithmus angeschaut, wie wir
diese sehr einfache erste Darstellung der Kantenliste, wo wir einfach
beliebig diese Paare von Knoten, die Kanten einfach rausgeschrieben
haben, wie wir das in ein Adjacenzfeld konvertieren können.
Das war dieser Algorithmus hier.
Hier noch ein Beispiel dazu.
Dann hatten wir uns überlegt noch, dass wir auch Kantengewichte sehr
einfach dazufügen können, zum Beispiel durch ein zusätzliches Array,
das eben parallel oder gleich groß wie unser Kantenarray E ist und da
legen wir eben einen entsprechenden Index dann die Zusatzinformationen
ab.
Also wie hier eben so ein Kantengewicht des ABCD zum Beispiel sein
können.
Genau, Knoteninfos könnten wir genauso ablegen, indem wir eben zu
diesem Array V jetzt parallel dazu ein zweites Array anlegen, in dem
Zusatzinformationen für Knoten gespeichert sind.
Also das geht auch hier relativ einfach, Zusatzinformationen
abzuspeichern.
Gut, dann hatten wir kurz festgestellt, dass wir Kantenanfragen zum
Beispiel über eine Hashtabelle realisieren können.
Was bedeutet Kantenanfrage?
Kantenanfrage ist, wir geben zwei Knoten vor, also U und V zum
Beispiel und wollen wissen, ist in dem Graph eine Kante von U nach V
vorhanden?
Und das können wir eben zum Beispiel über eine Hashtabelle
realisieren, indem eben die Schlüssel dann die Paare von Knoten sind.
Gut, dann hatten wir uns noch eine weitere Darstellung auch schon
angeschaut in der letzten Vorlesung, die sogenannten Adjacenzlisten.
Das ist auch eine relativ einfach zu verstehende Datenstruktur.
Also wir haben ein Array für hier oben, für die einzelnen Knoten, die
im Graph vorkommen und für jeden Knoten speichern wir uns auch wieder
die Kanten, die von diesem Knoten aus ausgehen.
Auch wieder hier in der Form von den Zielen der Kanten, also was ist
der Knoten, zu dem die Kante führt und die Zielknoten, die eben von
eins aus erreichbar sind, speichern wir einfach in einer Liste
nacheinander ab.
Also das bedeutet, was wir hier jetzt abgespeichert haben, wäre, dass
wir von Knoten 1 eine Kante nach 2 haben und von Knoten 1 eine Kante
nach 4.
Und hier eben entsprechend mit dieser Liste hätten wir von Knoten 2
eine Kante nach 1, von 2 nach 3 und von 2 nach 4.
Und was man natürlich hier auch sieht, das Einfügen und Löschen von
Kanten ist jetzt hier relativ einfach.
Also wenn wir jetzt zum Beispiel hier von 3 noch eine Kante hinzufügen
wollten, die nach 3 selber geht zum Beispiel, könnten wir hier einfach
noch einen zusätzlichen Eintrag hinzufügen, der die Kante 3 und den
Zielknoten 3 noch enthält.
Wenn wir das wieder löschen wollten, würden wir eben einfach diesen
Eintrag ausnehmen.
Und Einfügen und Löschen in Listen, das wissen wir, das geht sehr
einfach.
Da haben wir noch das Problem, dass wir eben den entsprechenden
Eintrag suchen müssen beim Löschen zum Beispiel.
Aber da könnten wir auch eine Datenstruktur verwenden, wie wir sie
letztes Mal in der Forschung hatten.
Also dass wir so eine Navigationsdatenstruktur zum Beispiel hier oben
drauf setzen noch und mit Hilfe eines Suchbaums dann auch in
logarithmischer Zeit zum Beispiel hier den passenden Eintrag in so
einer Liste suchen können.
Okay, also was ist der Vorteil dieser Datenstruktur Adjacenzliste?
Einfaches Einfügen, einfaches Löschen.
Braucht aber durch diese ganzen Verlinkungen, die in der Liste oder in
jeder dieser Listen vorhanden sind, braucht sie mehr Platz.
Also wir haben eben statt dem Eintrag hier zum Beispiel der 2, haben
wir eben gleichzeitig noch diesen Pointer, der auf den nächsten Knoten
und dieser Pointer, der auf den vorliegenden Knoten zeigt.
Also grobs dreifache können wir unter Umständen benötigen für die
Adjacenzfelder.
Und diese Elemente einer Liste auch im Speicher verteilt sein können,
ist auch die Cache-Effizienz von diesem Algorithmus, von dieser
Darstellung nicht ganz so gut.
Also Adjacenzlisten, eine sehr flexible Darstellung, nicht ganz so
effizient wie Adjacenzfelder.
Das haben wir uns auch noch angeschaut, dass man diese Adjacenzlisten
-Darstellung noch erweitern kann und kann, um alle möglichen
zusätzlichen Hilfsdatenstrukturen oder Verlinkungen, die man sich noch
unter Umständen vorstellen könnte, zwischen Elementen.
Also was haben wir hier?
Hier auf der rechten Seite haben wir unsere Knoten, unser Knotenfeld,
also hier Knoten 0 oben, Knoten 1, Knoten 2, Knoten 3 und eben noch
mit Zusatzinformationen hier versehen.
Also wir haben zum Beispiel hier zwischen eine Verlinkung auch über
eine Liste von diesen einzelnen Knoten.
Wir haben dann hier verschiedene Pointer, also zum Beispiel hier oben
einen Pointer, der uns auf die erste ausgehende Kante zeigt, die
benötigen wir sowieso.
Dann haben wir auch noch einen Pointer, der uns auf die erste
eingehende Kante zeigt.
Also damit können wir dann eben nicht nur ausgehende, sondern auch
eingehende Kanten dann einfach erreichen.
Hier die 0 wird bedeuten, es gibt keine.
Das ist ein Nullpointer, der hier drin steht.
Und dann könnte man auch noch den Grad zum Beispiel hier abspeichern
zusätzlich.
Was ist der ausgehende, eingehende Grad der Kanten?
Dieses Knoten-Eingangs- und Knoten-Ausgangsgrad dieses Knotens.
Und genauso kann man dann auf der Seite der Kanten in der
Datenstruktur auch noch zusätzliche Informationen ablegen.
Also wir haben wieder ganz links eben die Verlinkung der Kanten
untereinander über so eine doppelt vergetete Liste.
Dann hätten wir hier die von einem Knoten ausgehenden Kanten nochmal
verlinkt.
Also das wird da relativ einfach auch alle Kanten ausgehend von einem
Knoten ablaufen können.
Dann haben wir hier noch eine weitere Verlinkung, die uns für die
eingehenden Kanten ermöglicht, diese in einer Liste durchzulaufen.
Hier hat man noch... also ob es eine Kante in der anderen Richtung
gibt zu einer bestehenden Kante.
Also hier zum Beispiel, wenn wir uns diesen Beispielgraf hier rechts
oben anschauen, da haben wir zum Beispiel jetzt eine Kante von 1 nach
2 und auch eine Kante von 2 nach 1.
Und wenn wir jetzt von einer Kante, sagen wir zum Beispiel der von
oben nach unten zu der anderen entgegengesetzten Richtungskante zu
kommen, könnte man auch nochmal ein Feld hier ablegen.
Das wäre hier zum Beispiel diese Riff für Reverse, dieser Eintrag.
Da sehen Sie hier hat es zum Beispiel dann eben diese Pointer, die uns
zwischen 1 und 3 eben genau oder zwischen 1 und 2, Knoten 2 haben wir
ja rechts unten, zwischen 1 und 2 diese Kanten angeben.
Und dann kann man hier auch nochmal rückwärts Pointer einspeichern,
die jetzt eben von den Kanten zu den Knoten Einträgen wieder zeigen.
Also Sie sehen, man kann diese Adjacenzlisten-Darstellung noch
ziemlich weit aufbauen, je nachdem, was man eben an Anforderungen hat
für spezielle Algorithmen.
Okay, also alle möglichen Verzeigerungen kann man da auch noch dazu
fügen.
Und das werden Sie wahrscheinlich auch erleben, wenn Sie solche Graph
-Algorithmen implementieren, dass Sie häufig je nach Anwendungsfall,
wofür Sie so einen Graph benötigen, ganz unterschiedliche
Anforderungen haben, was denn jetzt da über so einen Graph effizient
abgefragt werden können soll oder welche Informationen Sie noch
zusätzlich ablegen wollen.
Und da bietet es sich dann eben an, so eine sogenannte Customization
der Datenstruktur vorzunehmen.
So ein bisschen, wie wir es auf der letzten Folie eben schon gesehen
hatten.
Sie nehmen die Elemente zu Ihrer Datenstruktur dazu, die es Ihnen
erlauben, Zusatzinformationen, die eben hilfreich sind, abzulegen.
Okay, jetzt wollen wir uns noch ein kleines Beispiel anschauen, wie
wir eine dieser Datenstrukturen, die wir jetzt gesehen haben für
Graphen, wie wir die eben konkret verwenden können.
Und der Algorithmus, wo wir uns den Einsatz einer solchen
Datenstruktur anschauen wollen, ist einer, den wir in der Vorlesung
früher schon hatten, nämlich die sogenannte DAG-Erkennung.
Also wir haben einen Graph und wir wollen erkennen, ob es sich bei
diesem Graph um einen Directed Cyclic Graph, also einen
schleifenfreien Graph handelt.
Also nicht zyklisch soll das sein.
Gerichtet sind unsere Graphen im Folgenden fast immer.
Also es geht darum festzustellen, ist ein Graph a-zyklisch oder eben
ein sogenannter DAG.
Und damals, als wir uns diesen Algorithmus angeschaut hatten, Sie
erinnern sich vielleicht noch, hatten wir uns nicht genau angeschaut,
wie denn so eine Graph-Datenstruktur aussieht, sondern wir haben uns
eigentlich auf der rein mathematischen Ebene bewegt.
Wir hatten eben gesagt, ja, so ein Graph besteht aus einer Knotenmenge
V und einer Kantenmenge E und wir haben irgendwie die Möglichkeit, zum
Beispiel hier zu prüfen, ob es einen Knoten in unserer Knotenmenge
gibt, der einen Eingangsgrad von 0 hat.
Ohne uns jetzt genau zu überlegen, wie die Datenstruktur dazu
aussieht.
Wir hatten gesagt, ja, wir können einfach Elemente aus unserer
Knotenmenge entnehmen und wir können Elemente aus unserer Kantenmenge
entnehmen.
Aber wie genau wir das jetzt implementieren, das hat man damals offen
gelassen.
Und das wollen wir uns jetzt noch ein bisschen genauer anschauen.
Aber bevor wir uns das auf dieser konkreten Datenstruktur anschauen,
erinnern wir uns vielleicht nochmal, was war hier die Idee dieses
Algorithmus zur Erkennung von a-zyklischen Graphen.
Also wir wollen erkennen, ob ein Graph zyklenfrei ist.
Und die Idee war, dass wenn der so ein Graph zyklenfrei ist, dann gibt
es bestimmte Kanten oder solche Kantenfolgen, die durch den Graph
durchlaufen und die Kantenfolgen, wenn die nicht zyklisch sind, dann
enden die alle an irgendeinem bestimmten Knoten.
Und wir in diesem Algorithmus suchen uns einfach diese Endpunkte raus,
die eben keinen Nachfolger haben und reduzieren von dort ausgehend den
Graph.
Das heißt also, wenn wir hier so einen Endpunkt haben, der keine
weitere ausgehende Kante hat, dann wissen wir, dass der auch zu einem
Zyklus nicht beitragen kann, weil da ja wir an einem Endpunkt ankommen
würden, wo es eben nicht mehr weitergeht, was wir für so einen Zyklus,
also wenn wir so ein Zyklus wäre, eben so eine Schleife in dem Graph,
dass wir irgendwann mal wieder am Ausgangspunkt ankommen.
Und wenn wir hier einen Endpunkt haben, dann kann der natürlich nicht
zu so einer Schleife beitragen.
Das heißt, was wir dann gemacht haben, haben diesen Knoten entfernt.
Wir haben auch die zugehörige Kante entfernt und dann eben
schrittweise das Ganze durchgeführt und geschaut, ob wir damit mit
dieser Operation des Entfernens von Knoten mit Ausgangsgrad mit 0 den
Graph abbauen können.
Also ich sehe sogar, wir haben es hier sogar anders gemacht.
Wir haben die andere Richtung vorgenommen.
Wir haben uns den Indegree angeschaut.
Für Zyklen ist das egal.
Also man kann den auch von der anderen Seite her abräumen, den Graph.
Also wenn wir hier von diesem Ende her arbeiten, dann würden wir
einfach den Indegree überprüfen und feststellen, wenn das hier ein
Startpunkt ist, wo es keinen Vorräger gibt, kann das auch in keinem
Zyklus enthalten sein.
Und dann würden wir von hier her den abräumen, den Graph.
Also wir löschen schrittweise Elemente aus unserem Graph raus, die
eben einen Eingangsgrad von 0 haben, solange bis wir fertig sind.
Wenn wir den ganzen Graph damit abräumen konnten, wissen wir, er
enthält keinen Zyklus.
Falls das nicht mehr geht, dann muss das sein, dass wir am Schluss
eben in einem Zyklus angekommen sind.
Und dann wissen wir auch, dass es damit kein Deck ist.
Okay, also diese Aufgabenstellung der Deckerkennung wollen wir jetzt
eben mit einer passenden Datenstruktur für Graphen lösen.
Und was wir hier verwenden wollen, sind diese Adjacenzfelder.
Also diese Adjacenzarrays.
Sie erinnern sich, das war diese Darstellung.
Knotenarray, Kantenarray.
Und in dem Knotenarray haben wir eben gespeichert, wo sind jeweils die
Startpunkte der entsprechenden Kanten in unserem Kantenarray.
Okay, und was wir in diesem Algorithmus jetzt machen, Sie sehen schon,
der ist ein bisschen komplizierter geworden als vorher.
Wir haben bestimmte Zusatzdaten, die wir in der Funktion benötigen.
Einerseits zählen wir, wie viele Elemente wir schon rausgestrichen
haben auf dem Graph.
Das ist dieser Eintrag dropped.
Und dann wollen wir eine Liste droppable führen.
Und in dieser Liste droppable sollen alle Knoten gespeichert sein, die
eben aus dem Graph entfernt werden können.
Also wir entfernen die nicht wirklich aus unserer Datenstruktur,
sondern merken uns nur, dass die entfernt wurden in einem zusätzlichen
Array.
Okay, also was machen wir?
Wir berechnen erstmal den Indegree von allen Knoten.
Das geht in linearer Zeit und speichern das in so einem Feld Indegree
ab für jeden Knoten und berechnen und bilden darauf dann diese
Droppable.
Das sind eben die Elemente, die erstmal jetzt hier die Kandidaten
sind, die weggelassen werden können, sind eben die mit Indegree 0 und
die speichern wir in so einer Liste ab oder einem Feld oder sogar
einen Stack können wir hier nehmen.
Und diese Elemente, die bearbeiten wir jetzt eben schrittweise.
Das heißt, wir schauen uns alle die Elemente an, die eben einen
Eingangsgrad 0 haben, die rausgestrichen werden können aus dem Graphen
und die bearbeiten wir jetzt, solange eben dieses Droppable unter 0
ist.
Gut, und dann haben wir hier noch eine Invariante nochmal angegeben
und die sagt uns, dass eben unser Graph auch während diesen
Modifikationen, die wir in jedem Schleifenschritt durchführen, diese
Deck -Eigenschaft beibehält.
Das heißt, wenn er vorher ein Deck war, ist auch danach noch ein Deck.
Wenn er vorher kein Deck war, ist auch danach kein Deck.
Also diese Zyklenfreiheit, die soll hier eine Invariante sein.
Gut, dann schauen wir uns den ersten Knoten V an, der eben gelöscht
werden kann.
Wir zählen dropped 1 hoch, unser Zähler für die Anzahl der schon
ausgestrichenen Knoten und wollen jetzt diesen Knoten V aus dem Graph
entfernen.
Genau, und wie machen wir das?
Wir gehen dazu die Kanten durch, die eben von diesem Knoten V aus
ausgehend sind.
Und da haben wir ja über unser Adjacenzfeld die einfache Möglichkeit
herauszufinden, wo die ausgehenden Kanten gespeichert sind.
Wir schauen erst in unserem Vertragsfeld nach, was ist der Index der
ersten ausgehenden Kante in unserem Edge-Feld und von da aus gehen wir
dann eben die Kanten durch.
Das heißt, das ist etwas, was wir in dieser Grafräse mit der
Repräsentation sehr schnell durchführen können.
Und was wir dann machen, wir passen eben dann den Eingangsgrad des
Zielknotens dieser Kante entsprechend an.
Wir wissen, wenn wir den Knoten V rauslöschen, dann verringert sich
der Eingangsgrad von Knoten W um 1.
Das speichern wir eben ab und merken uns auch wieder, wenn wir beim
Eingangsgrad 0 angekommen sind für den Knoten W, dass der dann auch
wieder gelöscht werden kann.
Das heißt, der wird dann in unsere Droppable-Datenstruktur
abgespeichert oder diese Droppable-Liste oder im Droppable-Stack
dazugefügt.
Damit haben wir auf dieser Datenstruktur eigentlich genau das gleiche
erreicht, wie das, was wir auf unserer letzten Folie abstrakt einfach
durch E gleich E ohne eine bestimmte Kantenmenge hingeschrieben
hatten.
Hier eben jetzt konkret für diese Datenstruktur.
Und Sie sehen auch, wir haben hier diese Adjacenz-Felddarstellung gar
nicht modifiziert, sondern wir haben hier wirklich nur mit
Hilfsstrukturen gearbeitet.
Eben diese Droppable-Stack und diese In-Degree-Datenstruktur, dieses
In -Degree-Array und konnten mit dieser Zusatzdatenstruktur auch diese
Löscheffekte im Graph dann nachvollziehen.
Gut, am Schluss müssen wir noch prüfen, ob unser Graph leer geworden
ist.
Das können wir jetzt hier machen, indem wir prüfen, ob die Anzahl, die
Knoten in unserem Graph, also die ursprüngliche Knotenmenge, ob die
gleich der Anzahl der gedroppten Knoten ist.
Dann sind alle Knoten verschwunden.
Okay, also so können wir das mit so einer Adjacenz-Felddarstellung
realisieren, diesen Algorithmus.
Und das Schöne ist, die Laufzeit ist hier linear in der Summe von
Kanten und Knoten.
Und was wir auch gesehen haben, wir brauchen eben keine dynamische
Datenstruktur, sondern diese Hilfsdatenstrukturen haben uns auch schon
ausgereicht, um diesen Algorithmus durchzuführen.
Okay, also das ist jetzt eine mögliche Anwendung, wie Sie eben mit
Hilfe von einer der gesehenen Graph-Repräsentationen arbeiten können.
Okay, aber wenn man sich so umschaut, dann sieht man, dass das noch
gar nicht alle Graph-Repräsentationen waren, die in der Praxis gar
nicht verwendet werden, sondern es gibt noch eine ganze Reihe von
weiteren und die wollen wir uns deshalb jetzt auch noch etwas
umfassender anschauen.
Also eine weitere Variante, wie Sie Graphen darstellen können, ist
über sogenannte Adjacenzmatrixen.
Also was ist eine Adjacenzmatrix?
Das ist eine Matrix, die an Elementen nur Einträge 0 und 1 enthält.
Und es ist eine n-Kreuz-n-Matrix, wobei n die Anzahl der Knoten ist,
die wir in unserem Graph haben.
Also, wenn wir rechts auf das Beispiel schauen, in dem Graph auf der
rechten Seite haben wir vier Knoten und deshalb drunter eben auch
diese 4-Kreuz-4-Matrix.
Und wie gesagt, die enthält immer diese Adjacenzmatrixen, enthalten
immer nur 0 und 1 als Einträge, wobei eine 0 dafür steht, dass keine
Kante vorhanden ist von Knoten i zu Knoten j.
Und eine 1 bedeutet eben, dass eine Kante vorhanden ist.
Also wenn wir jetzt zum Beispiel schauen wollen, gibt es eine Kante
von...
das hier wäre unser i, das hier wäre unser j.
Also gibt es eine Kante von... also in diese Richtung geht unser i, in
diese Richtung geht unser j.
Und wir haben dann eben Eintrag aij in unserer Matrix, genau dann,
wenn zwischen i und j eine Kante besteht.
Also wenn wir jetzt prüfen wollen, gibt es eine Kante zum Beispiel
zwischen Knoten 1 und 2, dann schauen wir i gleich 1, j gleich 2 in
unserer Matrix nach.
Hier steht eine 1 drin, also ja, da ist eine Kante vorhanden.
Oder wenn wir hier schauen, zum Beispiel gibt es eine Kante zwischen 2
und 4, dann haben wir hier auch eine 1 stehen, also ja, es gibt auch
hier eine Kante.
Wenn wir schauen, gibt es eine Kante von 4, wäre hier unten, nach 3,
dann haben wir eine 0, also nein, die gibt es nicht.
Von 4 nach 3 haben wir keine Kante hier gespeichert.
Also eine sehr direkte Darstellung des Graphen, aber für eine relativ
große Datenstruktur.
Wenn Sie sich überlegen, wenn Sie n Knoten haben, n vielleicht 10.000,
dann haben Sie hier eben eine Matrix mit 10.000 mal 10.000, also mit 1
mal 10 hoch 8 Einträgen, also das ist schon eine sehr große
Datenstruktur, die Sie da erhalten.
Und das ist eigentlich auch schon der größte Nachteil dieser
Datenstruktur, dass sie eben nicht sonderlich platzeffizient ist in
vielen Fällen.
Aber sie ist platzsparend, wenn Sie sogenannte Dichte-Graphen haben.
Was ist ein Dichter-Graph?
Ein Dichter-Graph ist ein Graph, in dem fast alle möglichen Kanten
enthalten sind.
Also wenn Sie so einen Graph darstellen wollen, dann enthält er eben
in diesen anderen Graph-Darstellungen sehr große Kantenlisten auch.
Und hier benötigt man nicht wirklich mehr Platz, um solche großen
Kantenmengen darzustellen.
Also für Dichte-Graphen ist das geeignet mit sehr vielen Kanten.
Ansonsten eher platzineffizient.
Man kann sich natürlich auch noch überlegen, diese Matrizen trotzdem
etwas kompakter abzuspeichern.
Aber ein Vorteil von dieser Datenstruktur ist, dass wir eben wirklich
sehr direkten Zugriff haben auf Informationen.
Also wir können die Frage, ob eine bestimmte Kante jetzt zum Beispiel
besteht, ja einfach direkt aus unserer Matrix ablesen, indem wir eben
an den entsprechenden Index ij in unserer Matrix nachschauen.
Also einfache Kantenabfrage, Navigation, ja das geht, aber vielleicht
nicht ganz so optimiert wie auf anderen Darstellungen.
Ein Vorteil, warum diese Graphen auch gerne verwendet werden, ist,
weil sie eine Verbindung erlauben zur linearen Algebra.
Also in der linearen Algebra geht es ja unter anderem auch um die
Darstellung von linearen Funktionen, von Vektorraum in Vektorraum.
Und diese linearen Funktionen lassen sich über Matrizen
repräsentieren.
Und von daher und dadurch hat man dann eben den Zusammenhang mit
linearem Algebra und bestimmte Algorithmen aus der linearen Algebra
lassen sich eben verwenden, um Graph-Fragen zu beantworten.
Okay, und als ein Beispiel, wie sich so ein Zusammenhang darstellen
kann zwischen lineare Algebra und dieser Adjacenzmatrix-Darstellung,
ist, wenn wir zum Beispiel einfach von gegebenen Adjacenzmatrix A die
K -Typotenz berechnen.
Also wir multiplizieren diese Matrix K mal mit sich selbst und nehmen
an, dass die Matrix, die dabei entsteht, C sein soll.
Und die interessante Eigenschaft jetzt hier ist, dass wir jetzt diesen
Einträgen in dieser entstehenden Matrix C eine Bedeutung geben können,
die auf den Graphen wieder eine sinnvolle Eigenschaft ergibt.
Und zwar ist es so, dass der Eintrag in der Matrix C an der Stelle IJ
genau die Anzahl der Pfade angibt, die von I nach J in diesem Graph
möglich sind.
Und das ist eigentlich schon eine ganz interessante Eigenschaft, weil
es ansonsten dieses Zählen von Pfaden, die es von einem Knoten I zu
einem Knoten J gibt, mit gewissem Rechenaufwand verbunden ist.
Und hier haben wir eben eine einfache Möglichkeit, gleichzeitig die
Anzahl von allen Pfaden von beliebigen Knoten I und J zu berechnen.
Und das eben mit dieser Matrix-Multiplikation.
Matrix-Multiplikation ist ja auch eben in vielen linearen Algebra
-Paketen schon vorhanden.
Das heißt, Sie können einfach so einen Standard-Algorithmus hernehmen
aus so einem linearen Algebra-Paket und dann eben über diese Matrix
-Potenzierung dann die Anzahl der Kanten berechnen.
Okay.
Dann gibt es so ein bisschen ähnlich, wie wir uns ganz am Anfang die
Langzahl -Multiplikation angeschaut hatten, gibt es auch
Vereinfachungs - Techniken bei der Matrix-Multiplikation.
Also man kann zum Beispiel diese Potenz-Berechnung, da muss man in
Wirklichkeit nicht K-Multiplikationen durchführen, sondern man kann,
indem man einfach erst hoch 2, hoch 4, hoch 8, also immer
Quadrierungen berechnet, kann man auch mit Log-K-Matrix
-Multiplikationen auskommen.
Und man kann auch eine Matrix-Multiplikation selber, also der Triviade
-Algorithmus benötigt kubische Zeit.
Den kennen Sie wahrscheinlich, dass man einfach so Zeitspaltenweise
eben durchgeht durch die Matrizen.
Auch der lässt sich noch optimieren.
Da gibt es einen Algorithmus von Strassen, der eben die Matrix
-Multiplikation noch beschleunigt.
Das ist auch wieder ähnlich wie der Kara-Tsuba-Algorithmus, die Idee,
den wir am Anfang der Vorlesung uns angeschaut hatten für schnelle
Langzahl -Multiplikationen.
Also, es gibt noch ein paar Tricks, um das zu beschleunigen.
Aber was hier der wichtige Punkt ist, ist, dass Sie mit Verfahren der
linearen Algebra Graph-Probleme lösen können.
Okay.
Und diesen Fall hier wollen wir uns jetzt noch ein klein bisschen
näher noch anschauen.
Also, wir wollen prüfen, stimmt diese Behauptung denn wirklich, dass
wenn wir die K-Potenz einer solchen Adjacenz-Matrix berechnen, dass
dann der Eintrag in dem entstehenden Produkt Cij die Anzahl der Pfade
von i nach j angibt.
Und das wollen wir mittels Induktion beweisen, also von dem Fall K
gleich 1.
Ja, also man muss jetzt noch anschauen, was gibt das hier an?
K-Kantenpfade bedeutet, das sind die Pfade, die genau über K-Kanten
laufen.
Also, das K-T-Produkt gibt uns jetzt nicht beliebige Pfade an, das
habe ich etwas ungenau ausgedrückt vorher, sondern es gibt uns die
Pfade an, die in genau K-Kantenschritten erreichbar sind.
Okay, also für K gleich 1 geht es um die Frage, was ist eben in einem
Schritt erreichbar.
Und das sind natürlich direkt die Einträge, die in unserer Adjacenz
-Matrix gespeichert sind.
Das heißt, da stimmt die Behauptung natürlich dann trivialerweise.
Wenn wir jetzt so einen Induktionsschritt durchführen wollen, dann
gehen wir davon aus, dass wir eben ja dieses K-Produkt bereits
durchgeführt haben und jetzt noch ein weiteres Mal die Matrix A drauf
multiplizieren.
Das gibt dann unsere Matrix C und das heißt, wenn wir jetzt
ausmultiplizieren hier und einfach sagen, ja, in unserer A hoch K ist
bereits berechnet und die Matrix, die dabei entsteht, wollen wir
einfach auch mit A hoch K bezeichnen.
Um da jetzt nochmal das A drauf zu multiplizieren, haben wir eben
diese Summenberechnung, die wir hier durchführen müssen.
Also die bereits zur Kartenpotenz erhobene Matrix wird mit der Matrix
A multipliziert.
Und dann haben wir eben, wenn wir uns jetzt anschauen, was bedeuten
die Dinge?
Also hier der Eintrag in A hoch K I L gibt uns an die K-Kanten oder
Pfade über K-Kanten von I nach J.
Das ist unsere Induktionsvoraussetzung, die wir für K bereits bewiesen
haben.
Und wenn wir jetzt uns das anschauen, das heißt, wir haben einen Pfad
nach L.
Und was kommt jetzt dann durch unsere Matrix, die wir nochmal drauf
multiplizieren, dazu?
An der Stelle LJ ist eben gespeichert wie eine Eins, wenn es eine
Kante von L nach J gibt.
Das heißt, wenn es diese Kante gibt, dann wird dieser Pfad
entsprechend hier auch in dem Produkt berücksichtigt.
Wenn eine Null drin steht, dann wissen wir auch, es gibt keinen Pfad,
der von I über L nach J führt.
Und das heißt, da haben wir dann auch eine Null eben in unserer Matrix
ALJ drin.
Das heißt, der wird dann nicht mitgezählt.
Also dieses eine Produkt in unserer Summation gibt uns an, eben die
Pfaden, die Kanten, die in K plus 1 Schritte von I über L nach J
führen.
Genau.
Und nachdem wir da eben jede letzte Kante genau einmal zählen,
entspricht das auch dann eben der Anzahl der Pfade, die über Länge K
plus 1 von I nach J führen.
Und damit haben wir dann die Behauptung bewiesen.
Gut, also damit können wir dann rausfinden, ob es Pfade in K Schritten
gibt.
Man könnte sich jetzt auch noch überlegen, wie kann man die Pfade der
Länge kleiner gleich K erhalten?
Gibt es da auch ein einfaches algebraisches Muster dafür?
Das ist etwas, wo ich auf die Übungen verweisen möchte.
Und wenn man jetzt eben an Pfaden beliebiger Länge interessiert ist,
dann kann man einfach eben dieses K zum Beispiel schrittweise erhöhen
und erreicht dann irgendwann mal die Anzahl der Pfade, die beliebiger
Länge möglich sind.
Also man kann es zum Beispiel so lange durchführen, bis sich keine
Änderungen mehr an der Anzahl der Pfade über die ganze Matrix ergibt.
Und dann kann man die Potenzierung stoppen dann.
Okay, also das wäre eine Möglichkeit, wie man mittels linearer Algebra
eben Grafeigenschaften berechnen kann.
Es gibt auch eine andere Richtung noch.
Also sobald man so eine Korrespondenz hat, versucht man, die in beide
Richtungen auszunutzen.
Und es gibt dann eben auch die andere Richtung, dass zum Beispiel die
Grafentheorie helfen kann in der linearen Algebra.
Und hier ein Beispiel dazu wäre eine Matrixmultiplikation oder das
Lösen eines linearen Gleichungssystems.
Wir haben eben hier dieses Gleichungssystem B mal X gleich C mit einer
Matrix B und einem Vektor C.
Und wir wollen gerne die Lösungen in X berechnen.
Dazu gibt es dann ja verschiedene Algorithmen, Gauss-Algorithmus oder
Varianten davon.
Und jetzt ist die Frage, inwiefern kann uns der Grafentheorie helfen?
Die kann uns helfen, indem wir zum Beispiel versuchen, diese bestimmte
Eigenschaften von unserer Matrix B auszunutzen.
Und zwar könnte es sein, dass diese Matrix B eine Gestalt hat, wie sie
jetzt hier abgebildet ist, also dass das so eine Blockmatrix ist, also
die besteht aus zwei Blöcken B1, B2 mit beliebigen Teilmatrizen.
Aber außerhalb von diesen Matrizen sind alle anderen Einträge null in
dieser Matrix.
Und das erlaubt uns eben zum Beispiel, dieses Lösen des linearen
Gleichungssystems zu vereinfachen.
Aber wir müssen eben erstmal diese Blockstruktur erkennen.
Und um diese Blockstruktur zu erkennen, kann man eben jetzt diese
Adjacenzmatrizen zum Beispiel verwenden, indem wir einfach hergehen
und uns einen Graph aufbauen, der auf dieser Matrix B aufbaut.
Und zwar soll dieser Eintrag 1 in unserer Hilfsmatrix oder in unserem
Graph eine Kante vorhanden sein, wenn in unserer Matrix ein Nicht-Null
-Eintrag anstelle IJ steht.
Also wenn es sich um einen Eintrag handelt, der eben in so einen Block
hier reingehört und kein Null-Eintrag ist, dann speichern wir das in
unserer Matrix ab.
Und was wir dann feststellen, ist, dass diese Block-Eigenschaft auf
der Matrix den Zusammenhangskomponenten in dem Graphen G entspricht.
Das heißt, wir versuchen in dem Graph einzelne Knotenmengen zu
identifizieren, die keine Verbindung haben über Kanten zu anderen
Knotenmengen.
Das nennt sich dann die Identifizierung von sogenannten
Zusammenhangskomponenten.
Da kommt nachher noch mehr dazu in der Vorlesung.
Aber über diese Zusammenhangskomponenten kann man dann zum Beispiel
eben so eine Partitionierung dann feststellen und so eine Block
-Eigenschaft auf der Matrix erkennen und ausnutzen.
Okay, also das heißt, es gibt auch die Möglichkeit, in einer anderen
Richtung Eigenschaften auf Graphen, wie eben zum Beispiel jetzt hier
die Erkennung von Zusammenhangskomponenten in lineare Algebra
-Verfahren hier Lösungen von Gleichungssystemen auszunutzen.
Okay.
Jetzt wollen wir uns noch eine letzte Repräsentation für Graphen
anschauen, um dieses Kapitel Graphrepräsentationen abzuschließen.
Und das ist eine etwas ungewöhnliche Darstellung, die auch nicht so
häufig benötigt wird, aber die doch eine gewisse Bedeutung hat, weil
sie eben zum Beispiel auch dazu dienen kann, solche
Zusammenhangskomponenten, wie wir sie auf der letzten Folie gesehen
hatten, zu erkennen.
Okay, also das ist eine Darstellung über sogenannte Intervallgraphen.
Und was ist ein Intervallgraph?
Wir haben eine Darstellung von Knoten über Intervalle.
Also wir nehmen für einen Knoten einen Intervall her, das durch zwei
reelle Zahlen repräsentiert ist, a, b.
Und Kanten sollen dann bestehen in diesem Graph, wenn es eben eine
Überlappung dieser Knotenintervalle gibt.
Also wenn ich einen Knoten v habe, der zum Beispiel hier von 1 bis 5
das Intervall repräsentieren würde, einen anderen Knoten u, der das
Intervall von 4 bis 6 repräsentiert, dann hätten wir hier einen
Schnitt in diesem Bereich zwischen diesen Intervallen.
Und das würde uns anzeigen, dass da eine Kante eben besteht zwischen
den Knoten u und v.
Wenn wir jetzt ein anderes Intervall hätten, hier zum Beispiel von 7
nach 9, dann würde sich dieses Intervall nicht überlappen mit u und v.
Und dieser Knoten, wenn wir ihn mal w nennen, zwischen w und u und v
würde es dann keine Kante geben.
Also wie gesagt, eine etwas ungewöhnliche Repräsentation.
Also das a, b, wie genau die festgelegt ist, das wollen wir auch gar
nicht weiter präzisieren, sondern wir bleiben einfach dabei, das soll
irgendwelche Werte a, b sein, die eben danach diese
Überlappungseigenschaft zur Darstellung von Kanten erlaubt.
Okay, also hier nochmal aufgeschrieben, wir haben Knotenmenge als
Intervalle a, i, b, e, i jeweils.
Wir haben eine Kante zwischen zwei Knoten, wenn die Intervalle einen
nicht leeren Schnitt haben.
Und anhand von dieser Darstellung kann man jetzt solche
Zusammenhangskomponenten relativ leicht erkennen.
Und zwar kann man einfach die Intervalle von links nach rechts
durchlaufen und prüfen, wie viele überlappende Intervalle es gerade
noch gibt an dieser Stelle.
Und wenn dieser Wert irgendwann auf 0 sinkt, dann sind wir praktisch
am Ende angekommen, wo jetzt von einem Knoten aus keine weiteren
Kanten mehr zu den Folgeknoten gibt.
Und wir haben damit eben eine abgedrehte Komponente, die von den
anderen Knoten unabhängig ist, erkannt.
Ja, das ist schon eine kleine Nebenbedingung.
Die Intervalle sollen immer so sein, dass eben der kleinere Wert vor
dem größeren Wert abgespeichert ist.
Also a kleiner b soll hier nicht gelten.
Und diese Möglichkeit, um so einen Zusammenhang zu berechnen, wäre
dann durch diesen Algorithmus hier zum Beispiel gegeben.
Ja, also wir haben den Algorithmus, der uns prüfen soll, ob so ein
Graph, der durch solche Intervalle, also ein Intervallgraph gegeben
ist, ob der verbunden ist, also aus einer Komponente nur besteht.
Wie machen wir das?
Wir haben als Eingabe die Liste der Intervalle, die eben gleichzeitig
die Knoten und die Kanten repräsentieren.
Und die soll sortiert sein nach den Endpunkten der Intervalle jeweils.
Also wir haben eine Sortierung der Intervalle, sodass eben der eine
Knoten, der einen größeren Endpunkt hat, eben weiter hinten in unserer
Liste steht.
Und dann gehen wir einfach die Elemente der Reihe nach durch,
bestimmen diesen Overlap, der am Anfang erstmal 1 ist für die erste
Kante und zählen dann, während wir durchlaufen, jeweils, wenn eine
neue Kante, ein neues Intervall sich schneidet mit dem bereits
bestehenden, dann zählen wir unseren Overlapzähler 1 hoch.
Ansonsten zählen wir den 1 runter, wenn ein Intervall endet.
Das ist diese Bedingung hier.
Und wenn wir damit dann am Ende angekommen sind, der Datenstruktur,
dann geben wir 2 zurück.
Das heißt, dann ist es ein zusammenhängender Graph.
Wenn wir zwischendrin schon bei 0 ankommen und noch nicht am Ende
angekommen sind, dann geben wir Force zurück, weil er dann nicht
zusammenhängend ist.
Okay.
Und die Laufzeit von dem Algorithmus ist hauptsächlich durch das
Sortieren, der dieser Intervalle bestimmt.
Sortieren können wir in NlogN und das geht sogar mit einer sehr großen
Kantenzahl.
Das kann auch ein sehr dichter Graph sein.
Also bis zu N Quadrat Kanten können da ja vorhanden sein.
Und trotzdem läuft ja ein O von NlogN.
Okay.
Also schauen wir uns das mal an, was hier passiert.
Also hier hätten wir jetzt eben unseren Zähler, der die Überlappungen
zählt, der hier bei 1 beginnt.
Wenn ein neues Intervall hier anfängt, zählt der 1 hoch.
Dann wäre hier 2.
Wenn 1 endet, zählt er wieder runter, wären wir wieder bei 1 und so
weiter.
Und hier an diesem Punkt wären wir jetzt wieder angekommen, dass der
Zähler zum Beispiel 0 ist.
Wir haben aber noch einen weiteren Knoten in unserem Graph, der eben
nicht verbunden ist mit dem restlichen Graph, wie man sieht dadurch,
dass er eben weiter hinten beginnt.
Als alle anderen hat er keine Kante zu den Vorhergehenden, sonst
bräuchte man so einen Schnitt dazu.
Das heißt hier an der Stelle würde man durch das Runtergehen des
Zählers auf 0 erkennen, dass dieser Graph nicht zusammenhängend ist.
Okay.
Also das ist so ein bisschen eine exotischere Darstellung nochmal, die
für diese eine Aufgabe eben jetzt des Erkennens von Intervallen, von
Zusammenhangskomponenten hilfreich sein kann.
Wir haben jetzt auch noch nichts gesagt, wie jetzt eben dieses AB hier
genau gewählt werden muss, oder wie man das wählen kann, dass eben
diese Graph-Struktur, dass die Kanten genau eingehalten werden.
Aber das soll dann auch Teil der Übung wieder sein.
Gut und damit wollen wir auch jetzt diese verschiedenen Graph
-Darstellungen, die wir uns angeschaut haben, erstmal beenden.
Also wir haben, wenn wir nochmal rekapitulieren, was hat man gesehen?
Wir hatten diese Kanten- Sequenz-Darstellung, wo wir einfach die
Kanten der Reihe nach in eine passende Datenstruktur geschrieben
hatten.
Wir hatten unsere Adjacenz-Felder, wir hatten die Adjacenz-Matrix, wir
hatten Adjacenz-Listen und wir hatten noch diese implizite
Repräsentation über Intervall-Graphen am Ende.
Und die Frage ist jetzt vielleicht, wenn Sie jetzt ein bestimmtes
Problem lösen wollen mit der Graph-Datenstruktur, welche
Repräsentation wählen Sie dann?
Und das hängt eben stark ab von den Operationen, die Sie da
durchführen möchten, eigentlich wie bei den anderen Datenstrukturen
auch.
Also die Operationen bestimmen häufig die sinnvollste Datenstruktur,
die Sie einsetzen.
Dann natürlich auch, wie häufig die Operationen durchgeführt werden
müssen.
Da gibt es dann eventuell auch wieder die Möglichkeit, vielleicht
amortisierte Laufzeitanalysen durchzuführen für die Algorithmen.
Gut, also vielleicht auch aus Erfahrung heraus, was sind die häufigst
verwendeten Algorithmen?
Eigentlich Adjacenz-Listen, würde ich sagen, ist eigentlich das, was
man am häufigsten antrifft oder Varianten davon.
Also die erlauben die häufig benötigte Flexibilität eben durch ein
Einfügen von Kanten oder Knoten auch, was man häufig benötigt und sind
deshalb, werden die gern verwendet.
Okay, gibt es gerade Fragen zu Graf-Repräsentationen?
Oder hat jemand von Ihnen selber vielleicht noch eine andere Graf
-Repräsentation schon mal gesehen oder selber implementiert?
Die meisten sind wahrscheinlich ähnlich wie das, was wir uns jetzt an
Varianten angeschaut hatten.
Okay, also was kommt jetzt als nächstes?
Jetzt haben wir Graf-Repräsentationen.
Die Frage ist jetzt, was sind Operationen, die man auf Grafen
durchführen möchten?
Also was sind Algorithmen, die auf Grafen arbeiten?
Können sich da was, ja, man kann sich da vieles jetzt darunter
vorstellen, was man auf so einer Graf gerne berechnen wollte, gerade
wenn der auch noch vielleicht mit Zusatzinformationen angereichert
ist.
Aber wenn Sie sich mal überlegen, was wären denn so Basis-Algorithmen,
die man vielleicht gerne hätte?
Ja, genau, hier wird schon ein Algorithmus sogar genannt.
Dijkstra, um kürzeste Wege in Grafen zu finden.
Genau, das wäre ein Algorithmus.
Also wir wollen, wenn wir jetzt eben zusätzlich noch ein Kantengewicht
haben, also zum Beispiel das Kantengewicht könnte es ausdrücken, was
ist der Abstand zwischen zwei Städten, die eben über eine Straße
verbunden sind?
Dann könnten wir versuchen, darauf einen Algorithmus aufzubauen, der
uns den kürzesten Weg zwischen zwei Städten bestimmt.
Das ist eigentlich so die klassische Routenplaner-Aufgabe.
Sie geben ein, Sie wollen hier von Karlsruhe nach Buxehute fahren und
Sie wollen den kürzesten Weg wissen, wie Sie dahin kommen.
Dann können Sie eben alle Straßen oder erstmal alle Wegpunkte über
einen Knoten darstellen und alle Straßen über eine Kante.
Die Länge der Straße oder die Zeit, die man benötigt, um die zu
fahren, speichern Sie als Gewicht ab und dann versuchen Sie, den
kürzesten Weg zu finden.
Das ist ein klassischer Algorithmus, genau.
Gibt es noch andere Dinge, die Sie sich denken können, die man auf
Grafen berechnen möchte?
Es gibt noch viele Dinge.
Es gibt eine große Gruppe, es sind auch solche
Flussoptimierungseigenschaften.
Also Sie wollen zum Beispiel in einem Stromnetz irgendwie
herausfinden, was ist die maximale Kapazität, die Sie übertragen
können von einem Punkt A an einen Punkt B in einem Stromnetz.
Vielleicht auch noch, wenn jetzt irgendeine bestimmte Verbindung
ausgefallen ist, was ist denn dann die maximale Kapazität, die noch
übertragen werden kann und auf welchem Weg kann die übertragen werden.
Also das wäre eine Fragestellung.
Aber es gibt auch noch viel einfachere Dinge.
Eine sehr einfache Fragestellung wäre, kann ich überhaupt in einem
Graf von A nach B kommen?
Also gibt es irgendwie so eine Kantenfolge, die uns erlaubt, von einem
Punkt A zu einem Punkt B zu kommen?
Also in der roten Planung ist es jetzt vielleicht in den feisten
Fällen der Fall, dass Sie irgendwie von A nach B kommen können.
Wenn es nicht gerade auf einem anderen Kontinent ist und Sie nur
Autoverbindungen berücksichtigen wollen, dann könnte es auch mal
schief gehen.
Aber solche Erreichbarkeitsfragen sind wirklich häufig etwas, was man
auf Grafen auch berechnen möchte.
Also die Frage, kann ich von einem Ausgangspunkt zu irgendeinem
anderen Punkt kommen?
Und es spielt in der Reihe von Fragestellungen eine Rolle, also zum
Beispiel auch in der Prüfung von Software oder Hardware, wenn Sie
beschreiben, die Zustände, die zum Beispiel ein Chip einnehmen kann
über Werte von Registern, Werte von irgendwelchen Flipflops, die in
unserer Schaltung vorhanden sind.
Das wären dann die Knoten, also die möglichen Zustände der Schaltung.
Eine Kante wäre dann vorhanden, wenn Sie eben einen Zustandsübergang
in Ihrer Hardware-Schaltung haben, die es erlaubt, von einem Zustand
zum anderen zu kommen.
Und dann könnten Sie so eine Frage haben, ist es möglich, in
irgendeinen Zustand, der eben fehlerhaft wäre, zu kommen von Ihrem
Startzustand aus?
Also Sie haben einen Chip, der Ihnen irgendwas berechnen soll und
bestimmte Zustände in Ihrem Hardware-Design sollen nicht erlaubt sein.
Die sollen nicht erreichbar sein, weil die eben irgendwie fehlerhaft
sind.
Und diese zu erkennen und ob die vom Start von Ihrem Chip aus
irgendwann mal erreicht werden können, das ist auch eine sehr typische
Frage.
Also die Frage Graf-Erreichbarkeit, kann ich in einem Graf von einem
bestimmten Startknoten zu einem bestimmten Endknoten kommen?
Auf kleinen Grafen ist das noch sehr überschaubar, da sieht man das
noch von Hand, wenn er nur fünf, sechs Knoten hat.
Aber wenn Sie dann denken, dass ein Graf vielleicht Millionen oder
Milliarden von Knoten hat, dann erkennt man natürlich nicht mehr so
einfach, ob ich jetzt von einem bestimmten Knoten überhaupt zu einem
anderen kommen kann.
Genau.
Und da spielen dann eben Erreichbarkeitsfragen eine Rolle.
Und was man zu der Erreichbarkeit häufig benötigt, ist die
Möglichkeit, einen Graf irgendwie auf systematischer Weise zu
durchlaufen.
Also ich möchte von einem Startknoten aus alle erreichbaren Knoten
irgendwie ablaufen.
Und diese Frage, wie komme ich von einem Knoten zu allen anderen
Knoten, nennt sich auch Graf-Traversierung.
Also könnte zum Beispiel hier sein, wenn man jetzt durch so eine Stadt
laufen möchte, was gibt es da für Möglichkeiten, durch diese Stadt zu
laufen?
Und Graf-Traversierung ist wirklich eben in sehr vielen Algorithmen
Basis von irgendwelchen komplexeren Dingen, die darauf aufbauen.
Also wollen wir uns jetzt im Folgenden ein bisschen anschauen, wie
können wir einen Graf traversieren?
Also wie können wir von einem gegebenen Startknoten aus alle
erreichbaren Knoten finden?
Okay.
Und was man dabei feststellt, wenn man sich jetzt anschaut, so eine
Graf - Traversierung, das heißt ich laufe jetzt die Knoten in meinem
Graf in irgendeiner Reihenfolge ab, die eben durch die Kantenrelation
vorgegeben ist.
Und dabei können verschiedene Arten von Kanten auftreten.
Oder man hat festgestellt, dass man die Kanten klassifizieren kann in
bestimmte Kanten, die auftreten.
Also einerseits gibt es eben solche Kanten, die einfach in dem Graf
direkt vorhanden sind.
Und die werden als Tree-Kanten bezeichnet.
Also ausgehend von einem Startpunkt S kann ich jetzt einfach über die
Kantenrelation zu einem anderen Knoten kommen.
Das wäre dann so eine Tree-Kante.
Während der Traversierung trifft man immer mal wieder auch auf den
Fall, dass man irgendwie prüfen möchte, ob eine bestimmte Kante
irgendwie vorhanden ist oder nicht.
Und diese Kanten, das sind dann diese, die jetzt hier gestrichelt
eingezeichnet sind.
Das heißt, das sind Kanten, die nicht im Graf vorhanden sind, sondern
die typischerweise geprüft werden oder die in dem Algorithmus eben
auftreten können, um festzustellen, ob eine bestimmte Kante eben eine
bestimmte Eigenschaft hat.
Und die wollen wir dann klassifizieren in sogenannte Forward-Kanten.
Also Forward-Kante ist eine Kante, die jetzt nicht wirklich im Graf
vorhanden sein muss, aber die eben von einem Startknoten aus zumindest
so einen Sprung macht, der eben eine Kanten-Sequenz zusammenfasst.
Also hier haben wir zwei solche Tree-Kanten und wenn wir diese zwei
Tree -Kanten eben hintereinander ausführen, dann ist das ein so ein
Forward -Schritt und den können wir uns als eine gedachte Forward
-Kante da denken.
Also auch zum Beispiel hier von S nach hier unten, das wäre auch so
eine Forward-Kante.
Genau, also eben alles, was in der Richtung von Kanten, dem Graf
vorhanden ist, entgeht und eventuelle Kanten überspringt.
Dann in der anderen Richtung, wenn wir haben, dass wir entgegen der
Kantenrichtung laufen und da eine Kante, imaginär uns denken, dann ist
es eine sogenannte Backward-Kante, die eben entgegen der Richtung des
Grafs läuft.
Und wenn es eine Kante ist, die eben nicht jetzt alle Schritte in
Grafrichtung oder in Kantenrichtung macht oder alle Schritte
entgegengesetzt, dann nennen wir die Cross-Kante.
Also da gibt es hier zum Beispiel von hier oben nach hier unten gibt
es eben Rückwärtsschritte, das wären diese hier und es gibt
Vorwärtsschritte und wenn wir so eine Kombination aus Rückwärts- und
Vorwärtsschritten haben, dann nennen wir das Cross-Kante.
Okay, und diese Klassifizierung, die würde ich Sie bitten, sich zu
merken, weil die wird bei unseren Traversierungsalgorithmen eine
gewisse Rolle spielen.
Okay, also schreiben wir es nochmal kurz auf, dass diese Tree-Kanten
oder Baumkanten, das sind eben Kanten, die im Graf auftauchen und man
kann die auch so bezeichnen, das sind die Elemente des Waldes, der bei
der Suche aufgebaut wird.
Also das sind die Kanten, in denen Sie eben die Reihenfolge
ausdrücken, in der Sie Ihre Suche durchgeführt haben.
Also Sie sind von einem Knoten S aus bei Ihrer Suche zu dem Knoten
hier unten zu dem gelaufen, dann von dem aus zu diesem unteren weiter.
Das heißt, das ist das, was Sie während Ihrer Graf-Traversierung eben
wirklich an Kanten abgelaufen haben.
Dann diese Vorwärtskanten sind eben parallel zu den Baumkanten,
Rückwärtskanten dann eben in der Rückrichtung, in der
Gegengesetztenrichtung oder antiparallel zu den Baumkanten und
Querkanten wären alles übrige.
Also die Kanten, die wir hier betrachten, sollen diejenigen sein, die
eben bei der Traversierung auftreten.
Also Sie durchlaufen den Graf in einer bestimmten Reihenfolge und
gehen dabei eben die Kanten durch und je nachdem, um welche Art von
Schritt es sich dabei handelt, bekommt er eben so eine
Klassifizierung.
Ja, genau, also wenn Sie jetzt daran denken, dass es so einen Zyklus
zum Beispiel gibt in einem Graf, das kann natürlich auch sein.
Also hier in dem folgenden wird es immer so sein, dass sich diese
Vorwärts - und Backwärtskanten nicht direkt auf den Graf beziehen,
sondern auf die Graf-Traversierung.
Also wir schauen uns immer eine bestimmte Reihenfolge an, in der wir
den Graf durchlaufen und auf diesen dadurch erzeugten Graf, darauf
finden wir dann diese Klassifizierung an der Vorwärts- und
Backwärtskanten.
Und da ist eigentlich so, dass da im Normalfall nicht gleichzeitig
eine Vorwärts- und Backwärtskante entstehen kann, sondern wir haben
immer eine bestimmte Traversierung, die eben eine Richtung dann nimmt
bei dem Durchlaufen des Grafs.
Aber sonst haben Sie recht mit Ihrer Anmerkung.
Ja, also man definiert es immer so, dass man sagt, Vorwärtskanten sind
immer als parallel bezeichnet und die Backwärtskanten immer als
antiparallel.
Ich weiß nicht, ob ich Ihre Frage da richtig verstanden habe oder ob
ich etwas anderes noch damit meine.
Eigentlich ist es einfach ein Synonym.
Also Vorwärts wird immer als parallel bezeichnet, Backwärts als
antiparallel und es geht eben immer darum, um diese Traversierung, die
wir durchführen.
Also es geht immer um diesen dynamischen Aspekt.
Wir haben einen bestimmten Graf, dadurch laufen wir die Knoten in
einer bestimmten Reihenfolge und die Reihenfolge, in der wir die
Knoten besuchen, das ergibt uns dann eben diese Bezeichnung als
Vorwärts - oder Backwärtskante.
Also wir wollen uns jetzt einen solchen Traversierungsalgorithmus
anschauen.
Also Ziel ist, gegeben von einem Startknoten aus, alle erreichbaren
Knoten zu besuchen.
Und das erste, was wir uns anschauen, ist die sogenannte Breitensuche.
Und genau, wir werden nachher noch eine Variante davon sehen, die
Tiefensuche.
Breitensuche heißt eben, dass wir mit möglichst wenig Schritten
versuchen, die Kanten zu erreichen.
Also was haben wir?
Wir haben einen Startknoten S und wir wollen von diesem Startknoten
aus alle erreichbaren Knoten besuchen.
Und während wir diesen besuchen, läuft unser Algorithmus eben diese
Knoten in einer bestimmten Reihenfolge ab.
Und diese Reihenfolge des Absuchens, die ergibt uns eben einen Baum
auf diesem Graph.
Und dieser Baum ist auch das, was jetzt auf der letzten Folie genannt
war, der uns dann eben diese Klassifizierung erlaubt zu Vorwärts- oder
Rückwärtskanten und so weiter.
Okay, und wir wollen jetzt eben alle erreichbaren Knoten finden und
diese Knoten auch auf kürzesten Faden.
Also wir suchen zu jedem Knoten die geringste Anzahl der Schritte, die
wir benötigen, um dahin zu kommen.
Okay, und wie man das machen kann, ist, wir fangen einfach zum
Beispiel an mit unserem Knoten S, unserem Startknoten und wir
berechnen jetzt einfach mal alle Knoten, die wir in einem Schritt
erreichen können.
Das wäre diese Menge hier.
Und das geht ganz direkt.
Das sind einfach die ausgehenden Kanten, die geben uns ja direkt an,
was in einem Schritt erreichbar ist.
Und damit haben wir dann diese Menge eben bestimmt, was ist von
unserem Startknoten aus in einem Schritt erreichbar.
Dann von da aus ausgehend berechnen wir, was ist in zwei Schritten
erreichbar und was ist in drei Schritten erreichbar.
Das heißt, wir arbeiten uns immer so blockweise nach vorne.
Also wir fangen an mit, was ist in null Schritten erreichbar.
In dem wir unsere Suche oder unsere Traversierung beginnen, ist
erreichbar.
Dann versuchen wir, alle Knoten zu bestimmen im nächsten Schritt, die
in einem Schritt erreichbar sind.
Dann als nächstes alle Knoten, die in zwei Schritten erreichbar sind.
So lange, bis wir eben, bis es eben nicht mehr weitergeht und wir
irgendwo keine weiteren Knoten mehr hier dazu bekommen, wenn wir einen
Schritt dazunehmen.
Also das ist eine Formulierung, die uns eben erlaubt, auch eine
bestimmte Variante des kürzesten Wege-Problems zu lösen.
Also alle Wege sind im Grunde immer gleich lang.
Also jede Kantentraversierung hat eine Länge eins an und damit haben
wir eben hier die Möglichkeit, auch schon kürzeste Wege mit dieser
Einheitsdistanz herauszufinden.
Okay, was man hier auch sieht.
Ich würde zum Beispiel jetzt anfangen hier.
Ich habe erst den Knoten, Startknoten gegeben und versuche jetzt Reihe
nach, die Knoten, die in einem Schritt erreichbar sind.
Also den Knoten B als erstes, dann den Knoten C, dann den Knoten D.
Und jetzt, damit bin ich fertig, habe meine Ebene 1 aufgebaut.
Das heißt, jetzt würde ich als nächstes dann versuchen, die Knoten zu
finden, die in zwei Schritten erreichbar sind.
Also die Knoten, also hier von D wäre E aus erreichbar, von D aus ist
auch F erreichbar.
Und wenn wir jetzt noch annehmen, wir haben eine Kante, die von D nach
E geht in unserem Graph, dann stellen wir fest, ja was ist mit dieser
Kante?
Wir haben eigentlich den Knoten E ja schon davor gesehen, also von S
nach B zu E zu gehen.
Auf dem oberen Weg haben wir den E schon gesehen.
Das heißt, wenn wir jetzt hier von unten über den Weg D nochmal zu dem
Knoten E kommen würden, dann müssen wir das nicht noch ein weiteres
Mal berücksichtigen, weil wir den ja bereits gesehen haben.
Und von daher ist dann diese Kante, die von D nach E geht, also die
auch in unserem Graph eben vorhanden ist, die ist jetzt hier was, was
bei der Traversierung nicht mehr berücksichtigt werden muss.
Und wir können sie deshalb eben ja hier an der Stelle dann weglassen
bei der Traversierung und auch als Vorwärtskante deklarieren dann.
Oder eine Crosskante wäre es genau, wie die von einem Pfad zu einem
anderen Pfad hier geht praktisch.
Und Vorwärts- und Rückwärtskanten enthalten.
Genauso, wenn wir jetzt dann weitergehen würden, zum Beispiel von dem
Knoten E aus zu prüfen, was können wir von hier aus in drei Schritten
erreichen?
Dann würden wir feststellen, ja, das ist G zum einen.
Also würden wir G dazunehmen.
Wir würden aber auch sehen, es ist zum Beispiel C zu erreichen.
Aber C haben wir davor schon besucht.
Also würden wir es auch als eine Crosskante hier erkennen.
Wenn wir von E weiterprüfen, stellen wir fest, es gibt die Kante nach
F.
F haben wir auch bereits gesehen über den unteren Pfad.
Also wäre von E nach F auch eine Crosskante hier.
Gut.
Und dann, wenn man jetzt hier bei der Ebene 3 noch weiter sucht,
stellen wir fest, von G aus gibt es jetzt zwei ausgehende Kanten.
Einmal nach F in unserem Graph, einmal nach B in unserem Graph.
Und wenn wir die klassifizieren, stellen wir auch fest, ja, F haben
wir bereits besucht.
Also ist es in dem Fall jetzt eine Crosskante, weil sie eben rückwärts
und vorwärts Kanten umfasst, um von G nach F zu kommen.
Wir stellen auch fest, es gibt diese Kante von G nach B, also die hier
oben zurückgeht.
Und hier behandelt es sich jetzt um eine Backwärtskante, weil die,
weggesprungen, weil es sich um einen Rücksprung handelt, der entgegen
unserer Traversierungsrichtung komplett verläuft.
Okay, gut.
Also das ist, hier sieht man nochmal diese Klassifizierung der Kanten,
die bei der Breitensuche entstehen.
Und Breitensuche, wie gesagt, immer blockweise alle Elemente, die in
einem weiteren Schritt erreichbar sind, werden dazugenommen.
Also die Idee bei der Breitensuche ist, den Baum Schritt für Schritt
aufzubauen, Schicht für Schicht aufzubauen.
Erstmal diese Schicht 0 in 0 Schritten erreichbar, Schicht 1 in einem
Schritt erreichbar und so weiter.
Wie können wir das machen?
Wie können wir diesen Schichtaufbau der erreichbaren Knoten
hinbekommen?
Also das ist dann auch unser Algorithmus schon für die Breitensuche,
für Bread's First Search steht das BFS hier.
Also wir haben einen Startknoten S und von diesem Knoten aus wollen
wir eben in dieser Breitensuche Reihenfolge alle Knoten besuchen.
Und das machen wir so, dass wir so eine Q mitführen.
Und die Q enthält immer genau die Knoten, die auf der aktuellen
Schicht gefunden wurden.
Also wir beginnen mit Schicht 0.
Das heißt, unsere Q enthält am Anfang die Knoten, die auf Schicht 0
gefunden wurden.
Und was machen wir jetzt?
Wir lassen jetzt hier eine Schleife ablaufen, solange wir eben noch
Knoten in unserer Q haben.
Das heißt, für die müssen wir noch explorieren oder schauen, was ist
denn von diesem Knoten aus erreichbar.
Solange es solche Knoten gibt, machen wir eben diese sogenannte
Exploration, dass wir uns die ausgehenden Kanten anschauen, schauen,
ob da was dazukommt.
Und das wäre jetzt hier diese Knoten B, C und D, die hier dazukommen
würden.
Und die würden wir uns dann in der nächsten, in so einer nächsten Q
ablegen, für die nächste Schicht Q Strich.
Und genau, es sind eben praktisch die, die neu dazukommen.
Diejenigen, die wir schon in früheren Schichten bearbeitet haben,
kommen hier nicht dazu.
Und dann setzen wir einfach unsere aktuelle Schicht Q auf dieses neu
berechnete Q Strich und wiederholen die Schleife so lange, bis wir
alle Knoten beendet haben.
Also das ist relativ einfach.
Wir schauen uns immer alles an, was von der aktuellen Schicht aus in
einem Schritt erreichbar ist, nehmen das zu unserer neuen Q Q Strich
dazu und wiederholen einfach den Prozess so lange, bis wir bis keine
neuen Knoten mehr dazukommen.
Okay, jetzt können wir uns mal überlegen, das sieht relativ
nachvollziehbar denke ich aus, dass man da schrittweise in so einer
tiefen Suche erreicht durch den Baumduch.
Was man im Normalfall auch möchte, man möchte irgendwie dieses
Ergebnis dann jetzt eben auch darstellen können oder sich speichern,
in welcher Weise man den Graf durchlaufen hat.
Und dazu kann man eben diesen Suchbaum, den man aufgebaut hat, den
kann man eben sich abspeichern.
Also wenn wir uns mal anschauen, was hier passiert ist ja, man schaut,
geht eben hier diese Knotenreihe nach durch hier, sucht dann hier
weiter und was man damit erhält in dieser Suchreihenfolge ist eben
dieser Suchbaum.
Und dabei handelt es sich eben wirklich auch um einen Baum und nicht
um einen Graf und der gibt uns eben an, in welcher Reihenfolge wir die
Knoten gefunden haben.
Und diesen Suchbaum, den wollen wir jetzt irgendwie abspeichern
können.
Und was man dazu machen kann, ist, dass man einfach jeweils für jeden
Knoten sich den Parent-Knoten, also den Elternknoten merkt.
Also von welchem Knoten aus ist dieser Baumknoten erreicht worden.
Also zum Beispiel, wenn wir uns B anschauen, B ist von S aus erreicht
worden, dann wäre Parent von B wäre S.
Und dann wollen wir es so machen, dass wir speichern, wenn der Knoten
noch nicht erreicht wurde, dann speichern wir dieses Bottom-Symbol als
Parent ab, zeigt uns dann eben noch nicht erreicht, der Knoten.
Und für den Startknoten wollen wir auch ein bisschen eine spezielle
Bedeutung von Parent-Knoten haben.
Den setzen wir einfach auf sich selber.
Also hier Parent-Knoten enthält dann eben diese Kante auf sich selber.
Dadurch ist eigentlich nicht mehr wirklich ein Baum, was wir da haben,
aber bei den Wurzelknoten wollen wir eben das erlauben.
Okay, also wenn man sich das hier nochmal anschaut, wir haben die Tree
-Knoten und die Parent-Knoten gehen eigentlich immer in der
entgegengesetzten Richtung dann.
Gut, und mit dieser Darstellung über die Parent-Knoten können wir uns
jetzt auch diesen Breitenzug-Algorithmus noch etwas detaillierter
anschauen, wie man denn das Ganze umsetzen kann.
Also, was haben wir?
Wir haben unsere Breitenzuche, die wieder von einem Knoten ausgeht,
von unserem Startknoten S und die soll uns zurückliefern.
Einerseits so ein Knoten, ja, ein Array von Knoten in unserem Graph,
das eben den besuchten Knoten entspricht und dann noch ein zweites
Array, das für jeden Knoten uns abspeichert, die Distanz vom
Startknoten.
Also wurde dieser Knoten gefunden oder nicht, weil wenn er nicht
gefunden wurde, bekommt er oben eben unendlich als Distanz, weil wir
suchen ansonsten die Distanz vom Startknoten.
Also das ist das, was unser Breitenzug-Algorithmus bestimmen soll.
Also letztendlich eigentlich hauptsächlich die Distanz neben Knoten
und dieses Parent-Array ist das Erste, was wir hier berechnen.
Okay, wir initialisieren jetzt erstmal hier die Distanz von den
Knoten.
Setzen wir alle erstmal auf unendlich, wenn wir die noch nicht gesehen
haben.
Dann die Parent-Knoten setzen wir auch mal auf dieses Bottom-Symbol,
also auf undefiniert für alle Knoten.
Und dann setzen wir, wie wir ja schon wissen, für den Startknoten noch
spezielle Einträge, wenn wir da mehr davon haben.
Also die Distanz des Startknotens vom Startknoten aus ist natürlich
null und der Parent-Knoten vom Startknoten, haben wir auch gesagt, den
wollen wir per Konvention so festlegen, dass der auch der Startknoten
selber ist.
Das heißt, dass wir einen Zyklus haben.
Gut, und jetzt wollen wir, wie gesagt, eben dieses Schichtweise
absuchen, unser Grafen erreichen und wir haben dazu eben unsere
aktuelle Queue, die enthält am Anfang nur den Startknoten.
Unsere Queue Q' soll das Ergebnis erhalten, was von dem Startknoten
aus oder von dieser Knotenmenge Q aus in einem Schritt erreichbar ist
und das eben dann die nächste Ebene nach der Ebene Q angeben.
Okay, also was machen wir?
Wir haben so eine Zählvariable L, die wir eben schrittweise hochzählen
und wir durchzählen diese Variable so lange hoch, solange unsere Queue
noch nicht leer ist.
Das heißt, die aktuelle Ebene, die wir gerade bearbeiten, bearbeiten
wir eben Schritt für Schritt und solange wir da noch Elemente drin
haben, die noch bearbeitet werden müssen, läuft der Algorithmus noch
weiter.
Okay, also das, was wir hier machen, ist, dass wir über die
verschiedenen Ebenen gehen.
Also 0 wäre die Ebene 0, 1 wäre die Ebene 1 und so weiter.
Und die Invariante, die jetzt hier gelten soll, ist eben, dass Q genau
die Elemente enthält, die in Distanz L von S aus im Graph erreichbar
sind, also in L-Schritten von S aus erreichbar sind.
Gut, was machen wir jetzt?
Wir gehen jetzt einfach unsere Knoten aus unserer aktuellen Ebene oder
unserer aktuellen Schicht durch.
Das sind die Knoten U, für die schauen wir uns die ausgehenden Kanten
an.
UV, das bedeutet, wenn wir so eine Kante UV gefunden haben, dann ist
Knoten V, ja, müssen wir uns das jetzt anschauen, ob wir den schon
gefunden haben davor oder ob wir den noch nicht gesehen haben.
Und wie stellen wir fest, ob wir den Knoten V schon mal gesehen haben
davor?
Indem wir prüfen, ob der bereits in unserem Suchbaum enthalten ist.
Und dieses Prüfen, ob er im Suchbaum enthalten ist, das geht eben über
das Parent Array.
Da ist ja ein Eintrag und gleich diesem Bottom Element drin, wenn der
bereits gesehen wurde.
Also wenn das noch das Bottom Element ist, dann wissen wir, diesen
Knoten haben wir davor noch nie gesehen.
Und das ist jetzt eben ein Knoten, der unserem Suchbaum dazugefügt
werden muss auf der nächsten Ebene.
Also wir wissen von Knoten U aus, ist der in einem Schritt erreichbar,
also wird der auf der nächsten Ebene hinzugefügt.
Also erweitern wir unsere Menge Q Strich um diesen Knoten V, der eben
von U aus in einem Schritt erreichbar ist.
Dann setzen wir auch noch die Suchtiefe, auf der wir diesen Knoten V
gefunden haben.
Und zwar ist das eben die der aktuellen Ebene plus 1.
Genau, was eben in der nächsten Schicht ist.
Und dann setzen wir auch noch diesen Parent Eintrag für Knoten V, wie
wir den gefunden haben, auf U.
Das ist der Fall, wenn der Knoten noch nicht gesehen wurde.
Was müssen wir tun, wenn der Knoten bereits gesehen wurde?
Wenn wir den früher in der Suche bereits gefunden haben, dann müssen
wir gar nichts mehr machen.
Dann ist er bereits in der früheren Schicht enthalten und wir sind
hier soweit fertig.
Okay, damit haben wir jetzt, wenn wir diese Schleife durchlaufen
haben, die äußere sogar, wenn wir die durchlaufen haben, dann wissen
wir, wir haben jetzt alle Knoten in der aktuellen Schicht
abgearbeitet.
Und haben alle Knoten, die von dort aus in einem Schritt erreichbar
sind, in unserem Q-Strich uns gemerkt.
Und was wir dann machen ist, dann vertauschen wir eben, oder setzen
wir unser Q, das heißt, wir wechseln eine Ebene weiter.
Wir gehen von dem Q zum Q-Strich, also unser Q-Strich wird, ja, also
das ist ja diese parallele Zuweisung, also Q-Strich wird zu Q und
unser bisheriges Q-Strich wird zur leeren Liste.
Das heißt, wir gehen einfach eine Ebene weiter damit.
Und hier oben in der Vorschleife, an dieser Stelle, war es ja auch so,
dass wir das L dann eben bei jedem Schleifendurchlauf um 1 erhöhen.
Also L geht hier gleichzeitig dann auch um 1 hoch.
Das heißt, die Tiefe entspricht dann auch dem, was wir auf der
nächsten Ebene finden.
Gut, das Ganze wiederholen wir, solange wir noch Knoten haben, die wir
noch bearbeiten müssen.
Also solange dieses Q ungleich leere Sequenz ist, wenn das irgendwann
mal leer wird, dann haben wir als Ergebnis unser Parent Array, das uns
eben den Suchbaum oder diesen Traversierungsbaum zurückgibt und die
entsprechenden Tiefen, die in dem Array D gespeichert sind.
Das ist der Breitenzug-Algorithmus.
Also was ist das Wichtige dabei?
Wir suchen die Knoten alle mit minimaler Distanz von einem Startknoten
ausgehend, indem wir uns eben schichtweise uns die Knoten betrachten.
Also wir haben immer eine aktuelle Schicht, die uns eben anzeigt, dass
in K-Schritten dieser Knoten erreichbar ist und wir versuchen von da
aus die Knoten, die in K plus 1 Schritten erreicht werden können.
Okay.
Also was man jetzt auch noch machen kann, man kann sich noch ein
bisschen überlegen Richtung Optimierungen.
Also man kann zum Beispiel diese Qs, Q und Q Strich kann man als FIFO
-Qs implementieren.
Ja, das geht relativ problemlos.
Dann was noch ein anderer kleiner Trick ist, ist, dass man sich
versucht, den Speicherplatz zu optimieren.
Also bei dem Algorithmus, wie er jetzt gerade angegeben war, da hatten
wir immer eine Q, Q und eine Q, Q Strich.
Und was man machen kann, ist, dass man das etwas anders repräsentiert,
indem man, es spart nicht unbedingt Speicherplatz, aber es ist eine
einfachere Repräsentation des Algorithmus, indem wir einfach zwei
solche Qs verwenden oder wie bisher auch Q und Q Strich, aber die
Schleife praktisch einmal ausrollen und einmal eben direkt von Q nach
Q Strich unsere Ergebnisse übertragen und dann in einem zweiten
Schleifendurchlauf diese Q und Q Strich einfach in einer vertauschten
Rolle ansehen dann.
Also bisher war es so, dass wir ja einfach Elemente von Q angeschaut
haben, Ergebnisse nach Q Strich geschrieben haben.
Danach haben wir dann Q Strich nach Q kopiert, Q Strich auf Leer
gesitzen.
Was man stattdessen machen können ist, dass wir einfach so wechselnd
zwischen Q und Q Strich arbeiten.
Das heißt, in einer der ersten Phasen lesen wir aus Q die aktuellen
Knoten raus, schreiben in Q Strich diejenigen Knoten rein, die in
einem Schritt oder einer eins zu höheren Tiefe erreichbar sind und
dann danach vertauschen wir einfach die Rollen.
Das sind Q Strich, die auf der aktuellen Tiefe sind und wir in Q die
Elemente reinschreiben, die in einem Schritt mehr erreichbar sein
können.
Genau und dann, wenn wir eben mit Q und Q Strich auf diese Art
arbeiten, dann kann man die auch platzsparend in ein Feld
reinschreiben.
Das heißt, wir haben ein Q, das hier von links nach rechts wächst und
ein Q Strich, das von rechts nach links wächst.
Und nachdem die eben nicht gleichzeitig beliebig wachsen können,
sondern Elemente hin und her gespielt werden, kann man die eben
geschickt in ein Feld reinpacken und sich dadurch nochmal einen
Speicherplatz sparen.
Okay, gut.
Aber das sind kleinere Optimierungstricks, die man sich da noch
überlegen kann.
Die Hauptsache ist eigentlich dieser Tiefenzug-Algorithmus, wie der
funktioniert.
Dieser Breitenzug-Algorithmus.
Was wir uns als nächstes anschauen wollen, ist diese sogenannte
Tiefenzuche.
Und was passiert bei der Tiefenzuche?
Da ist es jetzt so, dass wir eben nicht schichtweise die Knotenmengen
aufbauen wollen, sondern wir laufen einfach den Baum an der Stelle, wo
wir gerade sind, möglichst weit ab, bis es eben nicht mehr weitergeht.
Und erst dann, wenn wir am Ende angekommen sind, gehen wir wieder
einen Schritt zurück.
Also machen so ein Backtracking und suchen über andere Knoten, was es
da noch für weitere Wege gibt.
Also wir würden hier vom Startknoten aus erstmal den Knoten B uns
anschauen, dann aber nicht zu dem nächsten Knoten D, der ja auch auf
der nächsten Ebene liegen würde, weitergehen, sondern wir arbeiten
immer von dem aktuellen Knoten aus weiter.
Also E nach G nach F, bis es eben nicht mehr weitergeht.
Machen dann ein Backtracking und schauen uns hier, wo es noch weitere
Kanten gibt, die drei nach an.
Machen dann auch wieder irgendwann mal alle Kanten abgedickt haben.
Und auch da spielen dann wieder diese Tree-Kanten, Forward, Backward
und Cross-Kanten eine Rolle.
Okay, also wie kann so eine Tiefenzuche funktionieren?
Also die Idee ist eben wirklich, dass wir möglichst weit oder auf
einem Pfad voranschreiten.
Also wir verwenden eine Markierung nachher im Algorithmus für die
Knoten, die wir bereits gesehen haben.
Und deshalb werden wir am Anfang erstmal diese Markierungen
zurücksetzen, weil wir eben noch keine Knoten gesehen haben.
Dann initialisieren wir unsere Suche.
Also das bedeutet eigentlich den Startknoten in erster Linie.
Also dass wir den eben als bereits gesehen markiert haben und dann
gehen wir durch unsere Knotenmenge durch, schauen uns an, ob der
Knoten bereits markiert wurde.
Wenn das der Fall ist, dann haben wir den bereits früher gesehen.
Ansonsten markieren wir den.
Also ja, wir können sagen, das ist jetzt die neue Wurzel von unserer
Suche vorübergehend und von da aus werden wir die Suche dann irgendwie
fortsetzen.
Und genau, dann setzen wir diesen Knoten S, den wir jetzt gefunden
haben als neuen Knoten und führen von da aus diese Tiefenzuche wieder
durch.
Okay, also bei diesem Tiefenzuge-Algorithmus, da haben wir jetzt noch
einen kleinen Trick dabei, dass wir eben zwei Knoten dem übergeben.
Also dieser Depth-First-Search-Algorithmus-Tiefenzuge hat Argumente U
und V, jeweils zwei Knoten.
Und was geben die uns an?
Also wir wollen den Knoten V und von da aus unsere Suche fortsetzen,
wissen aber, dass wir den Knoten V von U aus erreicht haben.
Also das erste Argument gibt uns an, dass wir von U auf den Knoten V
getroffen sind.
Also Knoten V, wobei wir wissen, dass wir den U davor gesehen haben.
Wozu man das braucht, das sehen wir demnächst dann.
Gut, was macht jetzt diese Tiefenzuche?
Sie macht eben auch so eine Explorierung.
Wir schauen uns ausgehend von V die ausgehenden Kanten an.
Also wir schauen uns an, von wo aus können wir von V in einem Schritt
hinkommen, bezeichnen den Knoten mit W.
Also wenn wir diese Kante VW haben, was machen wir dann?
Wenn W bereits markiert wurde, dann wissen wir, den haben wir bereits
besucht und dann rufen wir diesen sogenannten Traverse Non-Tree-Edge
-Algorithmus auf, der uns so ein bisschen dieses Backtracking dann
auch durchführt oder diese Kante bearbeitet.
Ansonsten wissen wir, es handelt sich um eine Tree-Edge.
Also den Knoten V haben wir noch nicht gesehen.
Dann müssen wir den irgendwie bearbeiten.
Das sehen wir gleich nachher, wie wir das machen mit dieser Funktion
Traverse Tree-Edge.
Wir markieren den Knoten W als gesehen und führen dann von dort
rekursiv wieder eine Tiefenzuche durch.
Also jetzt von Knoten W aus gesehen, wobei wir wissen, wie haben wir
den Knoten W erreicht, über den Knoten V.
Also Knoten V war der Vorgänger.
Gut, wenn wir dann mit dieser Schleife fertig sind, dann haben wir den
Knoten V bearbeitet und dadurch, dass wir wissen, dass wir von U aus
den erreicht haben, machen wir jetzt diesen Backtrack-Schritt, der uns
eben eins wieder zurückgeht zu dem Vorgängerknoten U.
Auch dazu sehen wir gleich auf der nächsten Folge noch etwas mehr, wie
das genau funktioniert.
Okay, also schauen wir uns das auch wieder etwas mehr im Detail an.
Was macht die Init-Funktion, die wir auf der letzten Folie hatten?
Also im Detail schauen wir uns das mal kurz an.
Also wir haben hier diesen Vorbereitungsschritt für unsere Suche.
Wir wollen auch wieder genauso unser Ergebnis mit Hilfe des Parent
Arrays aufbauen.
Die Suchtiefe, wann wir den Knoten gefunden haben, die wollen wir ja
nicht verwenden und das heißt, wir initialisieren hier das Parent
Array auch erstmal wieder auf undefiniert.
Das heißt, alle Knoten sind erstmal noch nicht in dem, ja, noch nicht
gefunden worden durch unseren Suchalgorithmus.
Und was wir dann als erstes machen, also wenn wir S als Root
markieren, wird eben auch nach unserer vorherigen Konvention diese
Parent Kante von Knoten S auf S selber gesetzt.
Dann die Funktion Traverse Tree Edge ist auch sehr einfach zu
realisieren.
Was macht Traverse Tree Edge?
Die zeigt eben nur an, dass wir, oder soll uns im Ergebnis uns
speichern, dass wir eben hier diese Baumkante gefunden haben und das
bedeutet, dass wir das einfach in das Parent Array entsprechend
eintragen können.
Also wenn wir von V nach W diese Kante als Baumkante erkannt haben,
dann ist eben von V der Vorgänger W und das tragen wir hier
entsprechend, ja, von W der Vorgänger V und wir tragen das hier
entsprechend ein.
Okay, also wie sieht es dann aus?
Wir haben hier am Anfang unser Parent Array, das erstmal nur das S
initialisiert enthält und dann haben wir nachher während des
Algorithmus solche Tree Kanten, die wir haben, die wir eben
entsprechend markieren.
Gut.
Okay, aber ich denke an dieser Stelle machen wir auch für heute mal
Schluss und dann schauen wir uns nächste Woche den Tiefenzug
-Algorithmus noch abschließend an und beschäftigen uns dann auch noch
mit ein bisschen weiteren Algorithmen.
Dann, ja, genießen Sie den sommerlichen Tag noch und wir sehen uns
dann nächste Woche Montag wieder.