▴

Minimaler-Spannbaum-Rechner

Kruskal's Algorithm · Prim's Algorithm · Graph-Visualisierung

Gib einen gewichteten ungerichteten Graphen als Kantenliste ein und berechne den MST mit den Algorithmen von Kruskal und Prim algorithms. See step-by-step tables und a canvas visualization.

Schnellbeispiele

Was ist ein Spannbaum?

A spanning tree of a connected undirected graph G = (V, E) is a subgraph that includes all vertices V und a subset of edges forming a tree — a connected, acyclic graph. For a graph with n vertices, every spanning tree has exactly n−1 edges. The concept is fundamental to network design, where you want every node reachable from every other node with no redundant connections.

Was ist ein minimaler Spannbaum?

A minimum spanning tree (MST) is a spanning tree whose total edge weight is minimised over all possible spanning trees of the graph. Given a weighted undirected graph, the MST answers the question: "What is the cheapest way to connect all vertices?" For a graph with n vertices und m edges, the MST contains exactly n−1 edges und its total weight is the smallest achievable.

Two classical greedy algorithms solve this problem efficiently: Kruskal's algorithm und Prim's algorithm. Both are guaranteed to find an MST, und when all edge weights are distinct they both find the same unique tree.

Kruskal-Algorithmus

Kruskal's algorithm processes edges globally, sorted by weight. It starts with each vertex in its own component und merges components by greedily adding the cheapest edge that does not create a cycle.

Schritts

  1. Sortiere alle Kanten aufsteigend nach Gewicht.
  2. Initialisiere eine Union-Find-Struktur (Disjoint-Set), bei der jeder Knoten seine eigene Menge ist.
  3. For each edge (u, v, w) in sorted order: if u und v are in different components, add the edge to the MST und union the two components.
  4. Stoppe, wenn n−1 Kanten hinzugefügt wurden.

The Union-Find data structure with path compression und union by rank makes the cycle detection nearly O(1) per edge, giving Kruskal's algorithm an overall time complexity of O(E log E) — dominated by the sort.

Prim-Algorithmus

Der Prim-Algorithmus lässt den MST ausgehend von einem einzelnen Startknoten wachsen und wählt immer die günstigste Kante aus, die den aktuellen MST mit einem noch nicht im Baum befindlichen Knoten verbindet.

Schritts

  1. Beginne mit einem beliebigen Knoten; markiere ihn als besucht.
  2. Füge alle Kanten vom aktuellen MST zu einer Min-Prioritätswarteschlange hinzu.
  3. Extrahiere die Kante (u, v) mit dem minimalen Gewicht, wobei v unbesucht ist; füge sie zum MST hinzu.
  4. Mark v visited und enqueue its edges. Repeat until n−1 edges are added.

Mit einem binären Heap läuft Prim in O(E log V). Mit einem Fibonacci-Heap erreicht er O(E + V log V), was für dichte Graphen überlegen ist.

Kruskal vs. Prim — Vergleich

EigenschaftKruskalPrim
AnsatzGlobale KantensortierungKnoten-für-Knoten-Wachstum
DatenstrukturUnion-FindMin-Heap / Prioritätswarteschlange
ZeitkomplexitätO(E log E)O(E log V)
Am besten fürDünnbesetzte GraphenDichte Graphen
StartpunktKeiner (alle Kanten)Gewählter Startknoten
Produziert gleichen MST?Ja (für eindeutige Gewichte)Ja (für eindeutige Gewichte)

Eindeutigkeit des MST

Ein MST ist eindeutig, wenn alle Kantengewichte verschieden sind. Wenn sich zwei Kanten dasselbe Gewicht teilen, können mehrere MSTs mit gleichem Gesamtgewicht existieren. Das MST-Gesamtgewicht ist jedoch immer eindeutig.

Unzusammenhängende Graphen — Spannwälder

If the graph is disconnected, no spanning tree exists. Instead, each connected component has its own MST, und together they form a minimum spanning forest. For a graph with n vertices und k components, the spanning forest contains exactly n−k edges.

Praxisanwendungen

  • Netzwerkdesign: Entwurf von Telefon-, Strom- oder Internetnetzwerken mit minimaler Gesamtkabellänge.
  • Kabel-/Pipeline-Verlegung: Den günstigsten Weg finden, um Städte oder Infrastruktur zu verbinden.
  • Clusteranalyse: Hierarchisches Clustering verwendet MSTs, um ähnliche Datenpunkte zu gruppieren.
  • TSP-Näherung: Der MST liefert eine 2-Approximation für das metrische Problem des Handlungsreisenden.
  • Bildsegmentierung: Graphbasierte Segmentierungsalgorithmen erstellen MSTs über Pixelähnlichkeitsgraphen.
  • VLSI-Schaltungsentwurf: Minimierung der Drahtlänge zur Verbindung von Schaltungskomponenten auf einem Chip.

Häufig gestellte Fragen

Was ist ein minimaler Spannbaum?
A minimum spanning tree is a spanning tree of a connected weighted undirected graph with the smallest possible total edge weight. It contains all n vertices of the graph connected by exactly n−1 edges with no cycles, und no other spanning tree of the same graph has a smaller sum of edge weights.
What is the difference between Kruskal's und Prim's algorithm?
Kruskal's algorithm works globally — it sorts all edges und greedily adds each one if it does not form a cycle (detected via Union-Find). It is efficient for sparse graphs with O(E log E) time. Prim's algorithm works locally — starting from one vertex, it always picks the cheapest edge reaching an unvisited node, growing the MST outward. It runs in O(E log V) with a binary heap und suits dense graphs. Both algorithms always find a valid MST.
Hat jeder zusammenhängende Graph einen minimalen Spannbaum?
Yes. Every finite connected weighted undirected graph has at least one minimum spanning tree. The proof follows from the fact that the set of all spanning trees is finite und non-empty (for a connected graph), so a spanning tree of minimum weight always exists. For disconnected graphs, each connected component separately has an MST, forming a minimum spanning forest overall.
Ist der minimale Spannbaum immer eindeutig?
The MST is unique if und only if all edge weights are distinct. When distinct weights are used, both Kruskal's und Prim's always select the same edges. When some edges share the same weight, multiple MSTs may exist, all having the same total weight. The total MST weight is always uniquely determined regardless of how ties are broken.
Wie hoch ist die Zeitkomplexität des Kruskal-Algorithmus?
Kruskal's algorithm runs in O(E log E) time, where E is the number of edges. Sorting the edges dominates. The Union-Find operations, with path compression und union by rank, run in O(E α(V)) where α is the inverse Ackermann function — effectively a constant less than 5 for any practical input size. For dense graphs where E ≈ V², this becomes O(V² log V).
Was sind die realen Anwendungen von minimalen Spannbäumen?
MSTs appear throughout engineering und computer science: designing minimum-cost telecommunications und electrical grid layouts; laying cables, water pipes, or roads between cities at minimum total cost; single-linkage hierarchical clustering in machine learning; constructing 2-approximation solutions for the Travelling Salesman Problem; image segmentation in computer vision; VLSI circuit layout minimising wire length; und finding bottleneck spanning trees for network reliability analysis.
Was ist ein Spannwald?
A spanning forest is the generalization of a spanning tree to disconnected graphs. It is a maximal acyclic subgraph — equivalently, a collection of spanning trees, one for each connected component. If a graph has n vertices und k connected components, its minimum spanning forest contains exactly n−k edges und minimises total weight across all components.

Ähnliche Rechner

Dijkstra's Shortest Path Rechner
Adjacency Matrix Rechner
Graph Coloring Rechner
Hamiltonian Path Checker
Linear Programming Solver