Video 11-4: Repräsentationen von Graphen

0:03 Als nächstes wollen wir uns anschauen, wie wir jetzt Grafen tatsächlich darstellen, sodass diese Operationen auch schnell gelingen. Das bis eben war sozusagen die Sicht nach außen, die wir den Benutzer von dieser Grafklasse geben wollen. Und es gibt aber durchaus unterschiedliche Möglichkeiten, wie die intern realisiert sein kann. Die einfachste Variante ist eine Menge von Kanten. Ein Graf, wenn ich die Anzahl Knoten kenne, besteht im Wesentlichen daraus, welche Kanten gibt es und welche gibt's nicht. Das heißt, ich könnte z.B. eine sortierte Liste der Kanten haben. Hier sortiert nach der ersten Komponente und bei denen, wo die gleich ist, dann nach der zweiten sortiert, stabiles Sortieren und so. Äh, wenn ich dann eine gewisse Verbindung äh Fragen wissen möchte, ob 7 und 8 z.B. eine Kante haben, dann muss ich eben in dieser Kantenliste suchen, ob es einen Eintrag 78 gibt. Oder wenn ich wissen will, welchen Grad hat Knoten null, dann muss ich in der Liste diese Kanten durchlaufen.

1:03 Äh, wenn ich nur das habe, ähm, also wenn ich nur eine so eine lange Liste von Kanten habe, dann fällt's mir vielleicht ein bisschen schwer, direkt die Nachbarn vom Knoten 9 zu finden. Ich würde irgendwie gerne hier anfangen können. In dieser reinen Darstellung als Liste von Kanten ist es nicht vorgesehen. Also eigentlich ist das äh selten schnell genug. werden wir quasi nie verwenden.

1:33 Etwas cleverer an manchen Stellen ist eine Adiaz Matrixdarstellung Quasi der gleiche Begriff, aber die Schreibweise ist ein bisschen anders. Wie funktioniert das? Da haben wir sie erinnern sich die Knoten sind Indizes. Das heißt, wir haben Indices einmal hier und einmal hier für Bau und W.

2:09 Und dann haben wir einfach einen Eintrag, wann immer ähm zwei Knoten eine Kante haben, dann steht da eine ein und wenn sie keine Kante haben, steht dann eine Null. Also z.B. hier die 7 und 8 ist hier die 7 hier die 8. Dementsprechend wäre dieser Eintrag eine ein, da der Graf hier äh ungerichtet ist. Wir sind ja im ganzen Kapitel ungerichtete Grafen, Kanten haben keine Richtung, muss also auch von 8 nach 7 hier diese ein stehen. Das heißt, diese ganze Matrix, die ist symmetrisch entlang hier dieser Diagonal, ne? Das kriegen wir besser hin.

2:57 Auf der Diagonalen selbst stehen lauter Nullen, denn wir haben ja Schleifen verboten. Auf der Diagonalen wäre eine Kante von einem Knoten zu sich selbst. Sie sehen, die Darstellung würde das auch verkraften. Sie können dann eins auf der Diagonalen haben, dann gibt's eben diese Schleife. Das ist eher eine Entscheidung von uns. Semantisch wollen wir das nicht. Meistens wollen wir das nicht haben.

3:23 Na gut, besser kriege ich es nicht hin. Äh, sie sehen, aber die Matrix ist dann symmetrisch entlang dieser Achse. Äh, wäre schöner, wenn das tatsächlich quadratisch wäre.

3:32 Ähm, also sehen hier die Einseln sind gespiegelt und so weiter. Gibt's nicht so viele mehr. Okay, das ist eine Möglichkeit. Graf darzustellen. Das ist vielleicht nicht die erste, die ihn eingefallen wäre. Die hat einen großen Vorteil. Wenn ich von zwei Knoten wissen will, ob sie eine Kante zwischen sich haben, dann ist das die schnellste Operation, die man sich denken kann. Mach einen Zugriff an diese Zelle in der Matrix und dann ist eine ein oder eine Null und ich habe die Antwort. Wenn ich alle Nachbarn von einem Knoten finden will, also z.B. alle Kanten von Knoten Null weg. Dann weiß ich zwar, wo ich die finde. Ich schaue mir die Zeile von Knoten null an, aber ich muss dann hier durchlaufen und die vier Einsen finden.

4:18 Das heißt, es geht nicht ganz so schnell, insbesondere wenn das viele Knoten und wenig Kanten gibt. Ähm ist natürlich auch ein bisschen platzverschwenderisch, wenn ich äh da diese ganzen vielen Nullen mir anschaue. Das klingt so, als könnte man das effizienter machen. Äh, diez Adiazenzmatrix hat noch so ein paar andere clevere Eigenschaften über die lineare Algebra. Ich kann alles, was ich mit einer Matrix machen, hier auch mal drauf werfen und gucken, was passiert. Und manche von diesen Operationen machen sogar Sinn. Aber das ist so ein bisschen fortgeschrittenere ähm Dinge. Die Haupt Darstellung, die wir fast immer verwenden wollen, sind die Adjaenszlisten.

5:03 Also, das ist so der Standardfall, den wir eigentlich immer annehmen, wenn nichts anderes da steht, denn das hat so die besten ähm den besten Kompromiss zwischen diesen Oper zwischen diesen Optionen, die wir davor gesehen haben. Ich habe ein Array, das für jeden Knoten eine Liste seiner Nachbarn speichert. Sie sagen hier formal sind das Bergobjekte, denn die Reihenfolge der Nachbarn ist ja eh egal. Das heißt, es soll mich gar nicht interessieren dürfen, in welche Reihenfolge die da kommen. Könnte also z.B. will einen Stack sein oder eine Queue hatten wir damals drüber gesprochen, irgendeine verkettete Liste Tools und ich habe in diesem Fall auch jede Kante zweimal repräsentiert, so wie in der Matrix einmal von der 7 zur 8, einmal von der 8 zur 7. Abgesehen davon passiert hier nichts fieses. Das ist eine relativ einfache Darstellung. Die hat aber die ähm angenehme Eigenschaft, dass ich sehr effizient über die über diese Kanten sogar laufen kann. Wenn ich z.B. den Grad von Knoten null bestimmen will, dann äh kann ich hier durch diese vier ausgehenden Kanten iterieren. Habe dann eben jeweils eins hochgezählt und dann weiß ich den Grad. Ich muss nicht so eine ganze lange Zeile in der Zinsenzmatrix durchstreiten.

6:32 Also wie gesagt, das ist der Standard, den wir in aller Regel annehmen. Alles, was man damit gut machen kann, können wir gut machen mit den Grafen. Was man damit nicht gut machen kann, können wir nicht so gut machen. Wenn ich von zwei Knoten prüfen will, ob sie adjazent sind, also gibt's eine Kante zwischen 4 und 7, sehen Sie natürlich im Bild sofort nein. Wäre ja sonst hier. Aber wenn ich das in der Repräsentation prüfen will, dann muss ich von der vier z.B. die Liste durchlaufen und finde die sieben nicht. Also gibt's keine. Ich hätte umgekehrt auch von der sieben laufen können und die vier nicht finden, aber ich muss eine solche Liste durchlaufen und feststellen, dass ich die Kante dann da finde oder nicht finde. Das ist mit der Matrix schneller.

7:13 Die Frage, was davon tatsächlich besser ist, hängt auch ein bisschen von dem Graf ab. Und eine wichtige Eigenschaft ist diese Frage, wie dicht ist der Graf?

7:33 äh wie würde man Spar Spice Grabs äh dünn besetzt? Das ist sicher aus der Analogie von den Matrizen hergeleitet. Das ist glaube ich der gebräuchigste Begriff, den ich da im Kontext von Grafen kenne. Also die Frage ist einfach, wie viele Kanten von allen möglichen Kanten gibt es? Wenn da tendenziell die meisten da sind, dann ist die Matrix gut. dann sieht der Graf irgendwie so aus. Ähm, typische Grafen in Anwendung sind aber eher dünn besetzt. Ich habe eher wenig Kanten. Das ist kein Naturgesetz, aber das ist so die übliche Beobachtung. Und deshalb ist in der Regel die Adjazlistendarstellung die, die man nehmen möchte, weil die dafür effizienter ist. Das ist der übliche Tradeoff. Werden Sie noch Beispiele sehen? Okay. Äh Übersicht über die Laufzeiten für diese drei Darstellen Stellungen für Grafen. Äh die Kante Kantenliste, Adjazmatrix, Adiazlisten.

8:32 Äh und dann gibt's hier die Kategorien der Speicherplatz. äh hatten wir jetzt nicht viel drüber gesprochen. Ähm ergibt sich in jedem Fall relativ einfach aus der Darstellung und äh die Operationen, die eben besonders wichtig sind, sind über eine über die ausgehenden Kanten zu iterieren. Darauf basieren die meisten Grafalgorithmen. Und da sehen Sie, dass das hier ein Kompromiss ist zwischen diesen Extremen, die wir da haben. Ja, die diese Kantenliste ist so langsam, macht eigentlich selten Sinn.

9:09 Okay, wenn wir also jetzt wissen, unsere Darstellung der Wahl sind die Adzenlisten, dann sollten wir das auch in Java implementieren, damit wir damit arbeiten können.

9:16 Das sieht dann so aus. Ich habe einen Array gejacycy, mit dem ich die Indic werden die Knoten und jeder Eintrag ist ein Berg of integer, also die die Ziele der Kanten, die von diesem Knoten weggehen. Ähm Initialisierung macht halt ein neues Array davon mit leeren Bergs. muss ich explizit erstmal äh jeweils ein Objekt erstellen. Dann kann ich eine Kante hinzufügen, indem ich die in die entsprechenden Bags aufnehme. Also die Kante VW gibt einen neuen Eintrag in der Adzensliste von V, aber eben auch den umgekehrten Eintrag. Da wir hier ungerichtete Grafen haben und die Kanten ähm in beide Richtungen verwendet werden können, muss ich sie auch zweimal einfügen. Also, das ist hier ähm erstmal wichtig.

10:17 Sie sehen hier, dass auch in der Darstellung von Adenzlisten mit parallelen Kanten und Schleifen überhaupt kein Problem per se entsteht. Die Darstellung äh kommt damit zurecht. Wir wollen das nur oft aus logischer Sicht nicht unbedingt haben.

10:33 Okay. Und über ähm wenn ich die Nachbarn von einem Knoten haben möchte, dann bekomme ich eben einfach diese Berg intern zurück, äh in die ich dann hoffentlich nichts einfüge. Aber gut, Datenkapselung ist ein anderes Thema. Ja.