Adjazenzmatrix und Adjazenzliste

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

[@dariolukac8507]

Sehr ausführlich erklärt. Er lässt das was mein Professor so abstrakt formuliert, kinderleicht aussehen.

[@iscreamcsgo3055]

Erstaunlich wie einfach es sein kann wenn man es gut erklärt :) Danke für das Video !

[@BottropBoy]

Viel Besser als der Prof, danke!

[@Kaffekanne3]

Küsschen. Hilft mir sehr für meine Algo & DS Klausur

[@bittemitextrascharf]

Wirklich super erklärt und das Intro ist der Banger

[@JJmusic1915]

Vielen Dank, super als kleine Wiederholung vor der Kursarbeit in Info :)

[@azeylacalaty3182]

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

[@peterhanslooser]

Top, sehr gut und verständlich erklärt.... Bitte bei dieser Form der erklärung bleiben

[@bubkabu]

Super video. Wünsche dir noch viel Erfolg. Bleib dran, dann wird er sicher kommen.

[@MusikXStar]

Genau wonach ich gesucht habe, danke!

[@Emre-vl9wi]

danke für deine hilfe ich habe es innerhalb der ersten 2 minuten verstanden

[@HorrorGamingLP]

Sehr schön, wie immer von dir :)

[@kermi123d]

warshall algorithmus bitte, allgemein wären themen rund um algorithmen und datenstrukturen toll. vielleicht auch pseudocode, landau symbole usw=)!

[@kermi123d]

sehr schön

[@zulal8611]

ist es nicht auch in adjazenzliste konstanter zeit m ende?

[@2hamsi]

Sehr gut erklärt.

[@orph4nsx]

Ist das planner ? wenn ja woran erkennt man das ? Vielen Dank

[@jsstudychannel7405]

Was ist eine Kante?

[@Blackundercover]

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

[@zulal8611]

wenn die alle null sind wird es keine kante zwischen einem knoten mit sich selbst glaube ich, vielleicht heißt das bei euch sowas

[@zulal8611]

oops just realized ist schon 4 jahre her lol

[@Moriarty1982]

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

[@nerdwest2184]

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.

[@besnikbajrami5401]

Welcher Graph ist für die Implementierung eines Dykstras sinnvoller? Liste?

[@nerdwest2184]

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.

[@alisoltani5246]

nerdwest Danke. Warum ist es eigentlich abhängig von den Kanten und Knoten? Ist eine Adjazenzmatrix Implementierung in diesem Kontext nicht immer besser geeignet?

[@nerdwest2184]

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

[@johnnypepperonii]

Hammer Video! Kannst du noch ein Video zur Erreichbarkeitsmatrix machen? =)

[@leopoldstutch97]

Danke!,

müsste Knoten 6 nach 6 nicht wert 2 haben in der Matrix?

[@nerdwest2184]

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.

[@nerdwest2184]

Der Datentyp der Marix ist boolean, d.h. es kann nur true (1) und false (0) geben.

[@zulal8611]

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

[@pathfinderproject9381]

Wir machen das in der 11. Klasse am Gymnasium.... Macht unser Lehrer was falsch?

[@zulal8611]

woah krass, ich studiere mathe und lerne das hier haha