15: Breitensuche, DFS-Baum

0:00:00 Starten
0:00:09 Organisatorisches
0:03:12 Randbemerkung zu WWDC 2018
0:05:32 Rückblick Vorlesung 06.06.
0:07:56 Überblick heutige Vorlesung
0:08:18 Adjazenz-Matrix
0:08:52 Pfade zählen mittels LA
0:09:38 Graphentheorie und LA
0:15:39 Zusammenhangstest für Intervallgraphen
0:18:18 Beispiel
0:19:52 Graphenpräsentation: Zusammenfassung
0:21:30 Graph-Traversierung
0:23:14 Graphtraversierung als Kantenklassifizierung
0:26:23 Breitensuche
0:31:57 Repräsentation des Baumes
0:41:59 Repräsentation von Q und Q' mittels FIFO
0:45:45 Tiefensuche
0:47:04 Tiefensuchschema für G=(V,E)
0:52:43 DFS-Baum
1:00:08 DFS-Nummerierung
1:03:55 Fertigstellungszeit
1:06:03 Kantenklassifizierung bei DFS
1:07:47 Fertigstellungszeit
1:08:58 Topologishce Sortierung
1:13:38 Topologisches Sortieren mittels DFS
1:16:50 Starke Zusammenhangskomponenten
1:21:17 MehrDFS-basierte Linearzeitalgorithmen
1:22:37 BFS vs. DFS

Dozent:
Prof. Dr. Carsten Sinz | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik

Vorlesungsaufzeichnung: KIT | WEBCAST