Video 11-7: Breitensuche, Zusammenhangskomponenten

0:02 Wir werden auf Tiefensuche noch mal zu sprechen kommen. Ähm, es gibt noch mehr, was man damit machen kann. Äh, für den Moment belassen wir es äh für bei der ähm Anwendung, die ich eben schon gesagt hatte. Ich kann rausbekommen, ob von einem bestimmten Knoten ein anderer erreichbar ist über einen Weg. Ähm, es gibt aber noch eine Sache, die ich mit Tiefensuche nicht gut machen kann, nämlich einen kurzen Weg finden. Wenn Sie sich noch mal in Erinnerung rufen, gerade auch hier in unserem Beispiel, äh ich mache noch mal das das erste hier und wir finden das ganz schnell. Sie sehen, die die fettgedruckten Kanten sind ja die, die wir in dies Edge to Array packen. Wenn ich jetzt von meinem Knoten 0 zu dem Knoten 1 laufen würde, welchen Weg würde die Tiefensuche finden? Erstmal hier schön außenrum und einmal komplett durch den Graf gelaufen. Und das ist auch eher typisch als der die Ausnahme. Wenn ich also nicht nur irgendeinen Weg finden möchte, sondern einen kurzen Weg.

1:09 erinnern sich an äh unser Eingangsbeispiel mit der Routenplanung. Dann ist die Tiefensuche noch nicht der letzte der Weisheit letzter Schluss. Es gibt eine Variante der Tiefensuche oder eine andere Art von Suche, die Breitensuche auf englisch Breath first Search [seufzt][schnauben] und die eignet sich dafür sehr viel besser.

1:36 Äh, der Ansatz ist sehr ähnlich, aber wir verfolgen jetzt nicht in die Tiefe. Wann immer ich einen Knoten das erste Mal neu entdeckt habe, bin ich vor Begeisterung und Neugierhe, nicht zu bremsen und renn von dem Knoten weiter, sondern äh ich gehe von meinem Startknoten erstmal alle einzelnen Kanten ab. Wie weit komme ich mit einem Schritt? Und danach versuche ich diese Knoten weiter auszu baldobern. Wie komme ich mit zwei Schritten? Wo komme ich mit zwei Schritten hin? Wenn ich alle mit zwei Schritten erreichbaren Knoten abgehandelt habe, dann gehe ich drei Schritte weiter. Konzeptionell wahrscheinlich ähm klar, wie das gehen soll. Wie man das in im Code umsetzt, ist mit einer kleinen Änderung von der Tiefensuche. Statt, dass wir einen Stack verwenden, verwenden wir eine Qe. Um das bisschen noch mal zu illustrieren, auch da ein bisschen Animation.

2:38 Ähm, ich komme gleich auf die äh Variante zurück, wie das dann realisiert wird. Aber die Metapher für Tiefensuche war ja einzelner Höhlenforscher läuft da die Korridore ab und macht seine Kreuzchen an die Korridore, wo er schon war. Die Metapher für Tiefensuche ist eigentlich eine andere. Die Metapher für Tiefensuche ist, wir lassen eine eine Menge Wasser von unserem Knoten aus loslaufen und parallel, wann immer sie den nächsten Knoten erreicht, fließt das Wasser von dort weiter. Also mehr so wie eine Welle, die sich gleich mit gleicher Geschwindigkeit durch den Graf ausbreitet.

3:16 Ähm und äh ist natürlich ein bisschen äh mit dem Malen von den die Kanten sind nicht alle gleich lang, aber von der Zeit her sind sie dann doch gleich lang. Sie müssen sich irgendwie das entsprechend vorstellen. Also die Zeit auf jeder Kante ist genau gleich lang. Das heißt, die Knoten werden immer gleichzeitig erreicht, wenn ich äh sie über eine weitere Kante erreichen kann. Und was ich dann bekomme, ist so eine Art ähm Aufteilung meines Grafen in Distanz Layers. Es gibt den Startknoten, den kann ich mit Null Schritten erreichen. Dann gibt's eine Menge von Knoten, die kann ich mit einem Schritt erreichen und so weiter und so fort. Und jeder Knoten ist mit irgendeiner Anzahl Schritten erreichbar. Es gibt immer einen, entweder gibt's gar keinen Weg oder es gibt einen wohl definiert kürzesten Weg.

4:03 Also, das ist die eigentliche Anschauung dahinter. Wir können aber kein Wasser durch den Grafliesen lassen und wir wollen wirklich nicht jetzt auch noch mit parallelen Algorithmen anfangen, die diese Sie sehen ja hier äh im Wesentlichen, was da passiert ist, dass ich parallel an mehreren Stellen Forscher aussende, die alle gleich schnell laufen und wo immer ein neuer Knoten ist, äh teilen die sich noch mal auf in so viele, wie es Kanten gibt. Das können wir nicht so gut implementieren. Was wir stattdessen machen, ist äh der das gleiche Vorgehen wie der Tiefensuche mit einer anderen Datenstruktur für was ist der nächste Knoten, den ich mir als nächstes anschaue. Und auf dem Abstraktionsniveau sind die beiden Algorithmen super super ähnlich. Deswegen auch hier noch mal ähm die Computerrepräsentation sind wieder Adjazslisten. Der allgemeine Schritt ist wieder nimm den Knoten hier aus der Datenstruktur. jetzt keine kein Stack mehr, sondern eine Queue, eine Warteschlange. Das heißt, ich packe Knoten hier hinten rein und nehme sie aber hier vorne raus.

5:05 Am Anfang habe ich nur den Startknoten, also nehme ich den und schaue mir in der Adjazliste seine ausgehende Kante an. Jetzt könnte ich eine Kante abarbeiten und den Knoten hier drin lassen. Das ist schon eine Optimierung, die man in der Praxis auch immer machen möchte. Ich nehme den Knoten raus und hänge alle seine Kanten, alle seine ausgehenden Kanten als neue Elemente in die Q ein. Es sei denn, ich habe sie schon besucht. Also, wir besuchen Knoten null und wir gehen jetzt direkt alle Kanten durch. Die vier habe ich noch nicht gesehen, also kommt die in die Q. Ähm, die ein habe ich noch nicht gesehen, Okay, jetzt ist dieser Knoten null endgültig abgehandelt. Von dem aus gibt es auch keine weiteren interessanten Pfade zu entdecken. Das heißt, jetzt beginnt der nächste Schritt. Ich nehme das Element aus der aus der Datenstruktur, aus der Q, arbeite dessen Kanten durch. Eine davon ist die Null, die haben wir schon gesehen. Die Acht kennen wir aber noch nicht. Das heißt, die kommt hier ans Ende der Warteschlange.

6:13 Bei der Null passiert nichts, denn wir haben wir schon besucht. Nächster Schritt ist, ich nehme den nächsten Knoten aus der Datenstruktur. Also jetzt machen wir immer das gleiche. ersten Knoten aus der Queue entfernen. Alle seine Nachbarn hinten anhängen. Es sei denn, sie waren schon mal besucht. Okay.

6:34 Und dann sehen Sie, wir machen im Prinzip die gleiche Exploration wie in dieser Wasseranalogie, aber eben jetzt nicht mehr gleichzeitig, sondern einen Knoten nach den anderen. Da wir aber die Reihenfolge in der Queue immer beibehalten, was was zuerst reinkommt, kommt auch zuerst raus. First in, first out, ähm ist die Reihenfolge, in der die Knoten abgearbeitet werden, immer noch so wie in der Wasseranalogie, nur sozusagen mit ein bisschen bisschen Zeitversatz. Aber da wir uns ja merken, ähm hätte ich vielleicht äh habe ich noch gar nicht gesagt, ne? Wir können uns hier an der Stelle natürlich merken, mit welcher äh Anzahl Kanten wir einen Knoten erreicht haben. Für den ersten Knoten am Anfang brauche ich null Kanten und für jeden weiteren Knoten, den ich erreiche, weiß ich, ich erreiche den über eine neue Kante von einem Knoten, dessen Distanz ich schon kenne.

7:27 Also, ich kann mir induktiv die Distanz von dem Knoten zum Startknoten merken, indem ich die Kante, über die ich laufe, als Startpunkt nehme. ist äh irgendeine Anzahl Knoten, nehmen wir ein Beispiel weiter zurück.

7:49 Also z.B. ich sitze hier an dem Knoten 7. Ich schaue mir seine ausgehenden Kanten an. Ich weiß induktiv schon, die 7 hat Distanz 4 von dem Startknoten. 1 2 3 4. Das heißt, alle ausgehenden Kanten, die noch nicht zu die zu noch nicht besuchten Knoten gehen, gehen zu Knoten in Distanz 5. In dem Fall die 11. Das heißt, ich entdecke die jetzt, pack die da rein in die Q und kann mir merken, die wurde mit Distanz 5 erreicht.

8:25 Äh Beweis am Beispiel ist natürlich immer so ein bisschen mit Vorsicht zu genießen, aber eigentlich haben sie darüber alles gesehen, was Sie für Tiefensuche äh wissen müssen. Ähm hier noch mal ein Pseudocode, was wir getan haben. Wir verwenden eine Que statt einem Stack. Ähm ansonsten wie im Beispiel, äh schauen wir uns aber noch den Code dazu an. Der Tiefensuchecode war sehr kompakt, weil ich ihn einfach rekursiv beschreiben konnte. Das geht mit breiten Suche nicht. Que ist halt nicht Rekursion. Ähm, da gibt's keine keine einfache Möglichkeit. Ich muss mich also mit einer expliziten Queue rumschlagen. Ähm, haben wir ja aber gebaut aus verketteten Listen. Sie erinnern sich, da packe ich initial meinen Startknoten rein. Äh, der Startknoten ist initial auch direkt als markiert ähm gezeichnet. Alle anderen sind false. Das ist der Initialwert für Booliens. Und die Distanz zum Startknoten ist null. Da brauche ich keine Kante. Und dann kommt der allgemeine Schritt. Nimm den nächsten Knoten aus der Q.

9:29 lauf alle seine Nachbarn durch. Falls die noch nicht markiert sind, packen wir die jetzt ans Ende in die Queue und äh merken uns, dass wir die jetzt besucht haben oder dass wir die äh dass die in Bearbeitung sind. Ähm das Markt ist so ein bisschen, wir machen das schon prophylaktisch, wir wissen, die sind jetzt in der Queue, die werden dann schon abgearbeitet werden. Äh, das muss ich hier vorziehen, sonst würde ich eventuell den gleichen Knoten ganz oft in die Queue packen. Da kommt der eventuell erst viel später raus. Subtiler Unterschied zur Tiefensuche.

10:02 Wenn wir hier diesen neuen Knoten erreichen, der noch nicht markiert ist, dann wissen wir, wie wir die Distanz berechnen, nämlich die Distanz zu V1 größer. Und wir können uns auch merken, über welchen Knoten wir den erreicht haben. Dann können wir genauso wieder die Fade ausgeben, wie ähm bei der Tiefensuche.

10:22 Hier ist noch mal ein bisschen begründet, dass tatsächlich Tiefen äh Breitensuche die kürzesten Wege findet. haben sie glaube ich den Beispiel direkt gesehen. Ist wieder letztlich eine Induktion und hier ist das ähm Kernargument. Wir finden von dem Graf in diesen Distanzschichten, die Knoten in der passenden Reihenfolge. Ähm und wenn man sich genau anschaut, was in der Warteschlange passiert, ich habe da immer höchstens zwei solche Schichten gemischt. Ich könnte noch ein paar Knoten aus der Distanz äh D haben und ein paar Knoten sind schon von der nächsten Distanz d + 1. Mehr kann nicht passieren und ich arbeite die in der richtigen Reihenfolge ab. Dementsprechend finde ich immer den kürzesten Weg zu den Knoten.

11:08 Das ist natürlich sehr viel näher an dem, wie man äh kürzeste Wege vielleicht auch in den in Straßenkarten finden könnte. Eine ganz alte Anwendung Vorläufer des Internet. Arpanet kennen Sie vielleicht. Ähm da wurde das für ähm die Berechnung der kürzesten Kommunikationsdistanzen explizit gemacht. Wenn das ganze Internet halt nur aus so einer Handvoll amerikanischer Unis besteht, dann kann man das auch so machen. Äh mittlerweile natürlich ein paar Schichten dazu gezogen. Ähm ein anderes spaßiges äh eine andere spaßige Anwendung von kürzesten Wegen sind diese Verbindungen in sozialen Netzwerken. Z.B. gibt's die Bacon Number. Was sagt ihen das? Was kennt jemand das? Also es aus irgendeinem Grund ist Kevin Bacon Schauspieler äh relativ umtriebig gewesen, hat mit sehr vielen Leuten zusammengearbeitet und um so ein bisschen zu untersuchen, wie wie eng vernetzt die das soziale Netz von Hollywood ist, äh gibt's diese Bacon Number ähm in der quasi von zwei von dem beliebigen Schauspieler die Distanz zu Kevin Bacon berechnet wird.

12:14 Und Distanz heißt halt, es gibt eine Folge von Filmen und dann Schauspielern, die mit Kevin Bacon in dem Fall in diesem Film zusammengespielt haben und dann gibt's von dem Schauspieler einen anderen Film zu einem anderen Schauspieler. Und die kürzeste solche Kombination von äh zwischen Schauspielern und Filmen, die zu irgendeinem anderen Schauspieler führt, das ist für diesen Schauspieler dann die Kevin Bacon Zahl. Und wenn man dieses Experiment macht mit vielen vielen anderen Schauspielern, stellt man fest, dass diese Zahlen immer sehr sehr klein sind, wenn sie denn endlich sind. Vielleicht ist es unendlich, weil die nie irgendwie verbunden sind. Vielleicht gibt's so ein paar äh ganz isolierte. Ähm, aber wenn die Zahl endlich ist, dann ist sie in der Regel klein, was einfach dafür spricht, dass diese sozialen Netzwerke relativ kleinen Durchmesser haben. Äh, da gibt's ganz viele interessante sozialwissenschaftliche Forschung, die letztlich darauf rausläuft. Ähm, da haben sie sich den Spaß gemacht, noch ein bisschen ein Ausschnitt von diesem Graf zu malen.

13:19 Ähm, die Akademiker, man haben sich die gleiche äh Idee zum Vorbild genommen und das Kollaborationsnetzwerk von Paul Erd gemalt. Erdisch sehr bekannter einflussreicher Mathematiker gewesen, der ähm den späteren Teil seines Lebens im Wesentlichen mit äh aneinander gereiten und Forschungsaufenthalten und bestritten hatte und keinen festen Wohnsitz hatte. Und er war sehr er war dafür bekannt, mit sehr vielen Leuten zusammengearbeitet zu haben. Und dann gibt's die Erd Zahl, das ist also die Anzahl Zwischenschritte, die man braucht, bis man ein äh Kollaborator von Paul Erdisch ist. Äh, ähnliches Spiel und auch da gilt, wenn man eine endliche RDurchzahl hat, ist sie meistens klein. Ich glaube, bin bei drei oder so. Äh, das ist viel größere Zahlen gibt's nicht. Das ist auch da ähm sehr eng vernetzt. Und was man natürlich da berechnet, ist Breitensuche, um den kürzesten Weg in so einem Pfar zu fühlen. Na gut.

14:21 Äh zurück zu ein bisschen ähm abstrakteren Anwendung. Was wir hier ähm in verschiedenster Form gemacht haben, sind einerseits äh Zusammenhangskomponenten finden, also prüfen, ob zwei Knoten irgendeine Verbindung haben. Das können Sie mit tiefen Suche oder mit breitensuche machen.

14:40 Ist hier mit CC Connected Components benannt. ähm funktioniert im Prinzip mit mit Tiefen oder breitens genauso. Äh springe ich mal direkt zum Code. Ja, noch ein Beispiel dazu. Ähm, wir können z.B. eine Tiefensuche machen und wann immer wir den Knoten das erste Mal erreichen, merken wir uns von wo aus wir ihn erreicht haben. Äh, der Unterschied, was wir hier noch machen müssen für für die ähm Zusammenhangskomponenten ist, dass wir alle Knoten mal als Startknoten probieren müssen. Bisher hatte ich Ihnen sowohl Tiefensuche als Breitensuche so präsentiert, dass wir von einem Knoten loslaufen und dann explorieren wir den Graf, soweit wir kommen und dann hören wir auf. Äh in diesem in dieser Anwendung möchte ich aber für jeden Knoten wissen, mit welchen anderen ist er denn verbunden. Das klingt teuer, ist aber tatsächlich immer noch linear in der Größe von diesem Graf. Also großof von N + M gleich sehen. Äh was ich dafür mache, ist ein markiert Array für die für mehrere Durchgänge von Tiefensuche mir äh vorhalten.

15:58 Dann ähm habe ich auch ein Id Array, das also für jeden Knoten speichert, in welcher Zusammenhangskomponente ist, ist dieser Knoten zu finden. Und am Ende werden zwei Knoten genau dann verbunden sein. Die haben genau dann Pfad, wenn die ID dieser Komponente die gleiche ist. Also, was wir tun ist ähm letztlich Tiefensuche und innerhalb der Tiefensuche wird jeder Knoten, der ähm markiert wird, als ähm bekommt die gleiche ID zugewiesen, die aktuelle ID, die wir gerade so haben. Äh das ist hier Encount. Und nachdem diese Tiefensuche zurückkehrt von dem Startknoten V, habe ich alle von V erreichbaren Knoten mit Count markiert als die gehören alle zur Komponente 5. Danach zähle ich das eins hoch und besuche den nächsten Knoten. Wenn der nicht schon durch diese aktuelle Suche erreicht wurde, dann wird der Knoten jetzt zum Startknoten einer nächsten Suche.

17:12 Und dann ist das ähm Ergebnis z.B. dieses Bild hier. Also, ich habe einen Graf mit diesen drei Komponenten, die man optisch natürlich direkt erkennt. Äh, wenn ich diesen Code ausführe, dann habe ich hinterher für die ersten paar, also die schwarzen hier, eine ID von null. Für die grünen die ein und für die blauen eben zwei. Wenn Sie jetzt fragen, ist ein Knoten, ist der Knoten 6 und der Knoten 7 verbunden durch irgendeinen Weg, dann kann ich mir die IDs angucken und direkt sagen, nö. Falls Sie dann ähm für zwei verbundene Knoten den Weg haben wollen, dann machen wir das gleiche wie vorher mit unserem Edge2 Array. Kennen Sie auch schon. Auch das kann man auf den Teil verallgemeinern. Da gibt's dann eben einige Knoten, die keine Kante zu einem Vorgänger haben. Äh im Prinzip gibt's immer hier diese Startknoten, von denen wir diesen Aufruf gestartet haben und äh von denen gibt es keine Edge 2 äh Einträge. Die sind dann eben einfach äh Startknoten selbst. äh kann man auf irgendeinen Default Wert setzen.

18:30 Ja, hier ist die die Tiefensuche noch mal. Ähm die ist genauso wie wir sie vorher hatten. Nur ähm der Eintrag von diesem ähm ID äh auf Count setzen, es ist hier noch ergänzt. Sobald ich also den Knoten als Markiert erreiche und ich erste Mal finde, merke ich mir, in welcher Komponente habe ich das gefunden.

18:56 Auch damit kann man wieder ähm Sozialwissenschaften machen. Ähm, ich will es nicht alles im Detail diskutieren, aber es gab eine Studie von der amerikanischen Highschool, wo so die äh sexuellen Beziehung zwischen den Schülern in der Highchool aufgemalt wurden und äh untersucht wurden, was da so für Muster rauskommen. Da gibt's dann hier dieses ähm bedenkenswert groß vernetzte Bild und viele viele Vorkommen von kleineren ähm also hier steht 63 mal gab es isolierte Pärchen, die mit niemand anderem sonst eine Beziehung hatten. Und dann gab's noch so eine paar Dreiecksbeziehung, aber es gab auch diese anderen äh größeren Konstrukte.

19:37 Ähm ist ohne Zeitauflösung, das heißt, es kann durchaus sequentiell Monogramm gewesen sein. Na gut. äh andere Art äh wieder Bildverarbeitung, Zusammenhangskomponenten in der ähnlichen mit dem gleichen Graf wie vorhin. Wenn Sie die Pixel als Knoten wählen und eine Kante einfügen zwischen Pixeln, die einen ähnlichen Farbwert haben, müssen Sie dann sagen, was der Schwellwert ist, bis wohin gilt ähnlich. Dann können Sie mit Zusammenhangskomponenten eben solche Objekte finden, z.B. Sterne in dem Teleskopaufnahme und so weiter und so fort. ähm ist viel vielfältig eingesetzt und dadurch, dass die Algorithmen eben so schnell sind, kann man das auch äh ohne großen Aufwand machen.