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
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
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.
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.
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
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.
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
![BLACK BAG - Official Trailer [HD] - Only in Theaters March 14](http://i.ytimg.com/vi/Du0Xp8WX_7I/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!
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
Wirklich super erklärt und das Intro ist der Banger
Vielen Dank, super als kleine Wiederholung vor der Kursarbeit in Info :)
Super video. Wünsche dir noch viel Erfolg. Bleib dran, dann wird er sicher kommen.
Küsschen. Hilft mir sehr für meine Algo & DS Klausur
Sehr schön, wie immer von dir :)
Genau wonach ich gesucht habe, danke!
danke für deine hilfe ich habe es innerhalb der ersten 2 minuten verstanden
Top, sehr gut und verständlich erklärt.... Bitte bei dieser Form der erklärung bleiben
sehr schön
Sehr gut erklärt.
warshall algorithmus bitte, allgemein wären themen rund um algorithmen und datenstrukturen toll. vielleicht auch pseudocode, landau symbole usw=)!
Hammer Video! Kannst du noch ein Video zur Erreichbarkeitsmatrix machen? =)
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
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.
ist es nicht auch in adjazenzliste konstanter zeit m ende?
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.
Ist das planner ? wenn ja woran erkennt man das ?
Vielen Dank
Danke!,
Was ist eine Kante?
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
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
Wir machen das in der 11. Klasse am Gymnasium.... Macht unser Lehrer was falsch?
woah krass, ich studiere mathe und lerne das hier haha