WorksheetsAL Tutorium 11
Total questions: 12
Worksheet time: 8mins
Welcher Algo kann alle kürzesten Pfade zum Startknoten berechnen (ungewichtete Graphen)?
BFS
Bellman-Ford
DFS
Dijkstra
Welcher Algo berechnet Zusammenhangskomponenten?
BFS
DFS
Bellman-Ford
Dijkstra
Welches Problem löst Bellman-Ford im Gegensatz zu Dijkstra?
Nicht-zusammenhängende Graphen
Graphen mit negative Kreisen
findet alle kürzesten Pfade
Graphen mit Kreisen
Welche Kanten relaxiert Bellman-Ford zuerst?
Mit geringstem Gewicht
MIt größtem Gewicht
Mit negativem Gewicht
egal
Wie oft wird jede Kante bei Bellman-Ford relaxiert?
(n-1)-mal
(m-1)-mal
1-mal
2-mal
Wie oft wird jede Kante bei Dijkstra relaxiert (ungerichtete Graphen)?
(n-1)-mal
(m-1)-mal
1-mal
2-mal
Wiederholung: Was sind gültige Baumeigenschaften?
n-1 Kanten
Kreisfrei
Genau ein Pfad zwischen allen Knotenpaaren
immer ungerichtet
Was sind Eigenschaften aller MSTs?
Enthält jede Kante mit kleinstem Gewicht
Enthält alle Knoten
Gewicht < Gewicht vom Graph
Kreisfrei
Welche Aussagen sind wahr bei unterschiedlichen Gewichten?
Leichteste Kreiskante in jedem MST
Schwerste Kreiskante in keinem MST
Leichteste Schnittkante in jedem MST
Schwerste Schnittkante in keinem MST
Welcher Algo nutzt Union-Find?
Kruskal
Bellman-Ford
Prim
Toposort
Was liefert find(x) bei Union-Find?
Wurzel des Baums, in dem x ist
Elter von x
Vertreter der Menge von x
x
Wer ist vertreter der Menge, die bei union(x,y) entsteht?
x
y
x, wenn Rang von x höher als Rang von y
nichts der anderen Antworten
