Prim-Algorithmus
Zuletzt aktualisiert
Der Prim-Algorithmus baut einen minimalen Spannbaum (MST) - die günstigste Menge an Kanten, die alle Knoten ohne Zyklen verbindet - indem er einen einzigen Baum von einem Startknoten aus nach außen wachsen lässt. In jedem Schritt betrachtet er alle Kanten, die vom Baum zu einem Knoten außerhalb kreuzen, und fügt die günstigste hinzu. Drücken Sie oben auf Wiedergabe, um zu sehen, wie der Baum wächst und dabei stets die Kante mit dem geringsten Gewicht nimmt, die einen neuen Knoten erreicht.
Da er stets die minimale kreuzende Kante wählt, ist jede Hinzufügung sicher (garantiert Teil eines MST). Mit einer auf einem binären Heap basierenden Prioritätswarteschlange, die nach der günstigsten Kante zu jedem äußeren Knoten indiziert ist, läuft Prim in O(E log V). Er steht im Kontrast zu Kruskal, der alle Kanten global sortiert, anstatt einen einzigen zusammenhängenden Baum wachsen zu lassen.
Zeit- und Speicherkomplexität
| Implementierung | Komplexität | Hinweise |
|---|---|---|
| Binärer Heap | O(E log V) | Prioritätswarteschlange der kreuzenden Kanten |
| Adjazenzmatrix | O(V²) | Einfacher; gut für dichte Graphen |
| Speicher | O(V + E) | Baumzugehörigkeit + Prioritätswarteschlange |
| Am besten für | Dichte Graphen | Wächst von einem einzigen Startknoten |
Schritt für Schritt
| Schritt | Was passiert |
|---|---|
| 1 | Starten Sie den Baum mit einem beliebigen einzelnen Knoten. |
| 2 | Betrachten Sie alle Kanten, die vom Baum zu einem Knoten außerhalb kreuzen. |
| 3 | Wählen Sie die kreuzende Kante mit dem kleinsten Gewicht. |
| 4 | Fügen Sie diese Kante und ihren neuen Knoten zum Baum hinzu. |
| 5 | Wiederholen Sie, bis alle Knoten im Baum sind. |
Durchgerechnetes Beispiel
Aufbau des MST eines Graphen mit 4 Knoten und den Kanten A-B=1, A-C=3, B-C=2, B-D=4, C-D=5, ausgehend von A:
| Schritt | Baum | Kreuzende Kanten | Gewählte Kante |
|---|---|---|---|
| 1 | {A} | A-B=1, A-C=3 | A-B (Gewicht 1) |
| 2 | {A, B} | A-C=3, B-C=2, B-D=4 | B-C (Gewicht 2) |
| 3 | {A, B, C} | B-D=4, C-D=5 | B-D (Gewicht 4) |
| 4 | {A, B, C, D} | keine - alle Knoten im Baum | fertig: MST-Gewicht 1+2+4 = 7 |
Wann man den Prim-Algorithmus verwenden sollte
| Verwenden, wenn | Vermeiden, wenn |
|---|---|
| Sie einen minimalen Spannbaum eines zusammenhängenden, ungerichteten, gewichteten Graphen benötigen. | Der Graph gerichtet ist oder Sie kürzeste Wege benötigen - verwenden Sie stattdessen Dijkstra oder Bellman-Ford. |
Der Graph dicht ist (E nahe V²); die O(V²)-Matrixform ist einfach und schnell. | Der Graph dünn besetzt ist und die Kanten bereits sortiert oder leicht zu sortieren sind - Kruskal ist oft einfacher. |
| Sie möchten, dass der Baum von einer Region nach außen wächst (z. B. inkrementelles Netzwerklayout). | Der Graph nicht zusammenhängend ist - Prim überspannt nur eine Komponente; Sie benötigen einen minimalen Spannwald. |
| Sie bereits eine Adjazenzstruktur und eine Prioritätswarteschlange verfügbar haben. | Sie Zyklen über eine globale Kantenmenge erkennen müssen - Union-Find (Kruskal) passt besser zu dieser Form. |
Prim's Algorithm-Code
Eine saubere, lauffähige Prim's Algorithm-Implementierung in Python, JavaScript, Java, C++, C. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.
Prim's Algorithm-Code in Python
Python
1import heapq2
3
4def prim(graph, start):5 visited = {start}6 heap = [(w, start, v) for v, w in graph[start]]7 heapq.heapify(heap)8 mst, total = [], 09 while heap and len(visited) < len(graph):10 w, u, v = heapq.heappop(heap)11 if v in visited:12 continue13 visited.add(v)14 mst.append((u, v, w))15 total += w16 # Offer the new node's edges to the frontier17 for neighbor, weight in graph[v]:18 if neighbor not in visited:19 heapq.heappush(heap, (weight, v, neighbor))20 return mst, total21
22
23graph = {24 "A": [("B", 4), ("C", 1)],25 "B": [("A", 4), ("C", 3), ("D", 2)],26 "C": [("A", 1), ("B", 3), ("D", 5)],27 "D": [("B", 2), ("C", 5), ("E", 7)],28 "E": [("D", 7)],29}30
31mst, total = prim(graph, "A")32for u, v, w in mst:33 print(f"{u} - {v} (weight {w})")34print("Total MST weight:", total)Prim's Algorithm-Code in JavaScript
JavaScript
1const graph = {2 A: { B: 4, C: 2 },3 B: { A: 4, C: 1, D: 5 },4 C: { A: 2, B: 1, D: 8, E: 10 },5 D: { B: 5, C: 8, E: 2 },6 E: { C: 10, D: 2 },7};8
9function prim(start) {10 const inTree = new Set([start]);11 const mst = [];12 let total = 0;13 while (inTree.size < Object.keys(graph).length) {14 // JS has no built-in heap: scan all crossing edges for the cheapest15 let best = null;16 for (const u of inTree) {17 for (const [v, w] of Object.entries(graph[u])) {18 if (!inTree.has(v) && (best === null || w < best[2])) {19 best = [u, v, w];20 }21 }22 }23 const [u, v, w] = best;24 inTree.add(v);25 mst.push(`${u}-${v} (${w})`);26 total += w;27 }28 return { mst, total };29}30
31const { mst, total } = prim("A");32console.log("MST edges:", mst.join(", "));33console.log("Total weight:", total);Prim's Algorithm-Code in Java
Java
1import java.util.ArrayList;2import java.util.List;3import java.util.PriorityQueue;4
5public class Main {6 public static void main(String[] args) {7 int n = 6;8 List<List<int[]>> adj = new ArrayList<>();9 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());10 int[][] edges = {11 {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},12 {2, 3, 4}, {3, 4, 2}, {4, 5, 6}, {2, 5, 7}13 };14 for (int[] e : edges) {15 adj.get(e[0]).add(new int[]{e[1], e[2]});16 adj.get(e[1]).add(new int[]{e[0], e[2]});17 }18
19 boolean[] inMst = new boolean[n];20 // Always grow the tree along the cheapest crossing edge21 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);22 pq.add(new int[]{0, 0}); // {node, edge weight}23 int total = 0, taken = 0;24 while (!pq.isEmpty() && taken < n) {25 int[] cur = pq.poll();26 if (inMst[cur[0]]) continue;27 inMst[cur[0]] = true;28 total += cur[1];29 taken++;30 for (int[] edge : adj.get(cur[0])) {31 if (!inMst[edge[0]]) pq.add(edge);32 }33 }34 System.out.println("MST nodes reached: " + taken);35 System.out.println("MST total weight: " + total);36 }37}Prim's Algorithm-Code in C++
C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 // Undirected weighted graph: adj[u] = {(neighbor, weight), ...}7 std::vector<std::vector<std::pair<int, int>>> adj = {8 {{1, 2}, {3, 6}}, // 09 {{0, 2}, {2, 3}, {3, 8}, {4, 5}}, // 110 {{1, 3}, {4, 7}}, // 211 {{0, 6}, {1, 8}}, // 312 {{1, 5}, {2, 7}}, // 413 };14 int n = static_cast<int>(adj.size());15 std::vector<bool> inMST(n, false);16 using State = std::pair<int, int>; // (edge weight, node)17 std::priority_queue<State, std::vector<State>, std::greater<State>> pq;18 pq.push({0, 0});19 int total = 0, picked = 0;20 // Always grow the tree along the cheapest crossing edge21 while (!pq.empty() && picked < n) {22 auto [w, u] = pq.top();23 pq.pop();24 if (inMST[u]) continue;25 inMST[u] = true;26 total += w;27 ++picked;28 std::cout << "Add node " << u << " (edge weight " << w << ")\n";29 for (auto [v, weight] : adj[u]) {30 if (!inMST[v]) pq.push({weight, v});31 }32 }33 std::cout << "MST total weight: " << total << "\n";34 return 0;35}Prim's Algorithm-Code in C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8 // Undirected weighted graph: w[u][v] = 0 means no edge9 int w[N][N] = {10 {0, 2, 0, 6, 0},11 {2, 0, 3, 8, 5},12 {0, 3, 0, 0, 7},13 {6, 8, 0, 0, 0},14 {0, 5, 7, 0, 0},15 };16 int key[N], parent[N];17 bool inMST[N] = {false};18 for (int v = 0; v < N; v++) {19 key[v] = INF;20 parent[v] = -1;21 }22 key[0] = 0;23 int total = 0;24 // O(V^2) scan for the cheapest crossing edge (no heap needed here)25 for (int iter = 0; iter < N; iter++) {26 int u = -1;27 for (int v = 0; v < N; v++) {28 if (!inMST[v] && (u == -1 || key[v] < key[u])) u = v;29 }30 inMST[u] = true;31 total += key[u];32 if (parent[u] != -1) {33 printf("Add edge %d - %d (weight %d)\n", parent[u], u, key[u]);34 }35 for (int v = 0; v < N; v++) {36 if (w[u][v] > 0 && !inMST[v] && w[u][v] < key[v]) {37 key[v] = w[u][v];38 parent[v] = u;39 }40 }41 }42 printf("MST total weight: %d\n", total);43 return 0;44}FAQ zum Prim-Algorithmus
Wie ist die Zeitkomplexität des Prim-Algorithmus?
Mit einer auf einem binären Heap basierenden Prioritätswarteschlange läuft Prim in
O(E log V). Eine einfachere Adjazenzmatrix-Version, die in jedem Schritt nach der minimalen kreuzenden Kante sucht, ist O(V²), was bei dichten Graphen schneller sein kann. Beide verwenden O(V + E) Speicher.Was ist der Unterschied zwischen dem Prim- und dem Kruskal-Algorithmus?
Beide finden einen minimalen Spannbaum gierig. Prim lässt einen einzigen zusammenhängenden Baum von einem Startknoten aus wachsen und fügt wiederholt die günstigste Kante hinzu, die den Baum verlässt (mit einer Prioritätswarteschlange). Kruskal betrachtet alle nach Gewicht sortierten Kanten und fügt die günstigste hinzu, die keinen Zyklus bildet (mit Union-Find). Prim wird oft bei dichten Graphen bevorzugt, Kruskal bei dünn besetzten.
Findet der Prim-Algorithmus immer den optimalen MST?
Ja. In jedem Schritt ist die günstigste Kante, die den aktuellen Baum kreuzt, sicher hinzuzufügen - sie gehört zu einem minimalen Spannbaum (die Schnitteigenschaft). Das wiederholte Hinzufügen sicherer Kanten ergibt einen echten minimalen Spannbaum, sofern der Graph zusammenhängend ist.
Wann sollte ich den Prim-Algorithmus statt Kruskal verwenden?
Greifen Sie zu Prim, wenn der Graph dicht ist, da seine
O(V²)-Matrixform das Sortieren aller E Kanten vermeidet und einen einzigen Baum von einem Startknoten aus wachsen lässt. Kruskal glänzt bei dünn besetzten Graphen, bei denen das Sortieren der Kantenliste günstig ist und Union-Find die Zyklusprüfungen schnell hält. Beide erzeugen einen korrekten MST, daher hängt die Wahl hauptsächlich von der Kantendichte und den bereits vorhandenen Datenstrukturen ab.Beeinflusst der Startknoten den resultierenden MST?
Nein - das Gesamtgewicht des MST ist unabhängig davon, von welchem Knoten Sie starten, gleich, da das Gewicht des minimalen Spannbaums eines zusammenhängenden Graphen eindeutig ist. Die konkreten Kanten können sich nur unterscheiden, wenn mehrere Kanten dasselbe Gewicht haben und mehrere MSTs existieren. Andernfalls erreicht Prim unabhängig vom Startknoten genau denselben Baum.
Kann der Prim-Algorithmus mit nicht zusammenhängenden Graphen umgehen?
Nicht direkt. Prim lässt einen einzigen Baum wachsen und überspannt daher nur die zusammenhängende Komponente, die den Startknoten enthält, und lässt den Rest unberührt. Um jede Komponente abzudecken, würden Sie Prim wiederholt von einem unbesuchten Knoten aus ausführen und so einen minimalen Spannwald statt eines einzigen Baums erzeugen.
Verwandte Ressourcen
Mehr Visualisierungen
