Adjazenzmatrix und Adjazenzliste
Вставка
- Опубліковано 13 жов 2024
- In diesem Video präsentiert Prof. Dr. Oliver Lazar die Datenstrukturen Adjazenzmatrix und liste zum Abspeichern von Graphen. Dabei werden auch Vor und Nachteile der jeweiligen Lösung besprochen.
Nerdwest-Homepage mit weiteren Videos, Suchfunktion, Filtern, Quellcode etc.: www.nerdwest.de
![[UA] NAVI vs MOUZ | BO5 | IEM Rio 2024](http://i.ytimg.com/vi/CMBYk0cbGoA/mqdefault.jpg)
Sehr ausführlich erklärt. Er lässt das was mein Professor so abstrakt formuliert, kinderleicht aussehen.
Erstaunlich wie einfach es sein kann wenn man es gut erklärt :) Danke für das Video !
Viel Besser als der Prof, danke!
Küsschen. Hilft mir sehr für meine Algo & DS Klausur
Wirklich super erklärt und das Intro ist der Banger
Vielen Dank, super als kleine Wiederholung vor der Kursarbeit in Info :)
Ideal zum Anschauen nach der Vorlesung, die wie immer etwas wirr und kompliziert war. Echt sehr sehr gut erklärt! Perfektes Tempo, perfekte Erklärung :D
Super video. Wünsche dir noch viel Erfolg. Bleib dran, dann wird er sicher kommen.
Top, sehr gut und verständlich erklärt.... Bitte bei dieser Form der erklärung bleiben
Sehr geehrter Herr Prof. Dr. Lazar, Sie haben ein sehr gutes Video zu dieser Thematik gemacht. ich hätte da jedoch eine Frage: dürfen die Diagonalelemente bei einer Adjazenzmatrix Einsen enthalten? Denn in meinem Skript steht, dass diese 0 sind, da vorausgesetzt wird, dass diese "Schlingenfrei" sein müssen. Liebe Grüße
wenn die alle null sind wird es keine kante zwischen einem knoten mit sich selbst glaube ich, vielleicht heißt das bei euch sowas
oops just realized ist schon 4 jahre her lol
warshall algorithmus bitte, allgemein wären themen rund um algorithmen und datenstrukturen toll. vielleicht auch pseudocode, landau symbole usw=)!
Sehr schön, wie immer von dir :)
Hammer Video! Kannst du noch ein Video zur Erreichbarkeitsmatrix machen? =)
Genau wonach ich gesucht habe, danke!
ist es nicht auch in adjazenzliste konstanter zeit m ende?
danke für deine hilfe ich habe es innerhalb der ersten 2 minuten verstanden
Ist das planner ? wenn ja woran erkennt man das ?
Vielen Dank
Hhm ich hätte da eine Frage, würde es bei dem letzten Beispiel nicht Sinn ergeben noch mal eine Liste (B) erzeugen die so aufgebaut wäre:
A = { 1 => [ 2, 3, 7 ], 4 => [ 6 ], 5=> [ 4 ], 6 => [ 5, 6, 7 ], 7 => [ 5 ] }
B = { 1 => [ 1 ], 2 => [ 1 ], 3 => [ 1 ], 4 => [ 5 ], 6 => [ 4, 6 ], 7 => [ 1 ] }
Oder noch einfacher:
M = { 0 => A, 1 => B }
Mit M[0][1] würde man dann [ 2, 3, 7 ] erhalten und mit M[1][2][0] = M[1][3][0] = M[1][7][0]
Das verbraucht zwar mehr Speicher als die reine Liste, würde im Worst Case, wenn also jeder Graph mit jedem verbunden ist, auch nicht schlimmer sein als die Matrix.
Die Zugriffszeit müsste bei einem größeren Array auch nur von O(k) -> O(1) gehen, da bei einem vollen Array, lediglich ein Index zum Nachschlagen dazu käme.
Und hier bin ich mir nicht sicher aber wäre bei ganzer Ausfüllung nicht:
M[0] = Trans(M[1]) und
M[1] = Trans(M[0]) woraus folgt
M[0] = Trans(Trans(M[0]))
M[1] = Trans(Trans(M[1]))
bzw. das M[0] zu M[1] zueinander Invers sind?
[EDIT]
Bei genauerem drüber nachdenken, würde es nicht genügen jeden Liste mit dem Index 0 beginnen zu lassen und die Sprungmarken dann durch einen Restklassenring Z/Z(n // 2) zu speichern?
Immerhin gilt ja für zwei Werte a, b mit a=x und b=y:
a = a % b
m := b = b % a
a = a % b
Das a=y und b=x
Somit müsste doch eigentlich gelten:
a = m % b
b = m % a
Hallo Marc, vielen Dank für deinen (sehr sehr langen und umfangreichen) Kommentar. Mir fehlt allerdings gerade die Zeit, alles im Einzelnen nachzuvollziehen und angemessen zu beantworten.
Die Null (False) muss doch nicht gespeichert werden wenn man auf null / nothing prüft und dann default ein false returnt. Ist ein True vorhanden, dann kann man diesen einfach ausgeben.
sehr schön
Sehr gut erklärt.
Welcher Graph ist für die Implementierung eines Dykstras sinnvoller? Liste?
Hallo Mr. Smith. Es tut mir Leid, aber die Frage ist so absolut unlogisch. Ich denke mal, du möchtest wissen, ob man für die Implementierung des Dijkstra als Datenstruktur für den Graphen besser eine Liste oder eine Adjazenzmatrix verwendet. Falls ja, dann ist eine Adjazenzmatrix besser geeignet, wenn es einen dichten Graphen mit vielen Kanten hat, ein dünner Graph mit wenigen Kanten wird besser mit einer Adjazenliste verwendet.
nerdwest Danke. Warum ist es eigentlich abhängig von den Kanten und Knoten? Ist eine Adjazenzmatrix Implementierung in diesem Kontext nicht immer besser geeignet?
Das ist ein komplexes Thema. Ich schlage vor, dass du dir hierzu mal Seite 5 aus folgendem PDF anschaust: www.ruhr-uni-bochum.de/lmi/lehre/materialien/ds/minpath.pdf
Was ist eine Kante?
müsste Knoten 6 nach 6 nicht wert 2 haben in der Matrix?
Die Matrix kann doch nur 0 oder 1 enthalten (0 = keine Kante, 1 = Kante vorhanden).
nerdwest ich hab bisher gelernt das Knoten die eine loop auf sich selbst haben mit einer zwei markiert werden. Darum die Frage. Wobei jetzt auch auffällt das du einen gerichteten Graphen hast und keinen ungerichteten.
Der Datentyp der Marix ist boolean, d.h. es kann nur true (1) und false (0) geben.
also bei uns in der vorlesungsfolien gibt es zwei nur wenn es zwei kanten zwischen die knoten läuft, oder halt -1 gibt es wenn es ein gerichteter graph ist, aber hier hat er ja nur 0 und 1 in der sinne ob es überhaupt existiert oder nicht
Danke!,
Wir machen das in der 11. Klasse am Gymnasium.... Macht unser Lehrer was falsch?
woah krass, ich studiere mathe und lerne das hier haha