Algorithmen I, SS 2015, gehalten am 15.06.2015, Vorlesung 17
1 hour 28 minutes Posted Dec 8, 2015 at 8:59 am.
Kap. 9: Graphtraversierung
Graphtraversierung als Kantenklassifizierung
Breitensuche
Repräsentation des Baums
Repräsentation von Q und Q‘ mittels FIFO
Alternative Repräsentation von Q und Q‘
Tiefensuche
Tiefensuchschema für G = (V,E)
DFS-Baum
DFS-Nummerierung
Fertigstellungszeit
Kantenklassifizierung bei DFS
Topologische Sortierung
Topologisches Sortieren mittels DFS
Starke Zusammenhangskomponenten
Mehr DFS-basierte Linearzeitalgorithmen
BFS – DFS
Kap. 10: Kürzeste Wege
Anwendungen
Grundlagen
Kantengewichte grösser gleich Null
Dijkstras Algorithmus
Korrektheit der Bindfäden
Edsger Wybe Dijkstra (1930-2002)
Allgemeine Definitionen
Kante (u,v) relaxieren
Dijkstras Algorithmus: Pseudocode
Beispiel
0:00
1:28:47
Show notes
17: Vorlesung |
Watch Video
