Was ist der Unterscheid zwischen einem minimalen Spannbaum(Kruskal,Prim), einem kürzesten Weg(Dijkstra,Bellman-Ford) und Breiten/Tiefensuche?
Was unterscheidet diese drei Kategorien? Bin da irgendwie total irretiert.
1.minimaler Spannbaum(Kruskal,Prim)
2.Dijkstra,Bellman-Ford
3.Breiten/Tiefensuche
1 Antwort
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Informatik, Informatik
Ein minimaler Spannbaum ist die Untermenge der Kanten eines Graphen, die alle Knoten des Graphen miteinander verbindet und dabei das minimalste Gesamtgewicht aufweist.
Ein kürzester Weg ist die Untermenge der Kanten eines Graphen, die zwei gegebene Knoten (oder bei Djikstra einen gegebenen Knoten und alle anderen Knoten) miteinander verbindet und dabei das minimalste Gesamtgewicht entlang des Pfades zwischen den Knoten aufweist.
Breiten- und Tiefensuche sind Iterationsverfahren auf Knoten eines Graphen. (Oder alternativ Ordnungen.)