Algorithmen und Datenstrukturen · Senior · Frage 5 von 75
Wie unterscheiden sich die Algorithmen von Prim und Kruskal?
- 1Prim lässt einen Baum wachsen; Kruskal verbindet Wälder per günstigster Kante
- 2Prim findet kürzeste Wege; Kruskal Spannbäume
- 3Prim braucht sortierte Kanten; Kruskal eine Priority Queue von Knoten
Antwort zeigen
Richtige Antwort: Prim lässt einen Baum wachsen; Kruskal verbindet Wälder per günstigster Kante
Erklärung
Beide berechnen einen minimalen Spannbaum. Prim fügt die günstigste Kante hinzu, die den aktuellen Baum verlässt (Heap von Kanten); Kruskal sortiert alle Kanten und überspringt mit Union-Find Zyklen. Kruskal passt zu dünnen Kantenlisten, Prim zu dichten Graphen.