# Minimaler-Spannbaum-Rechner (Kruskal / Prim)

Berechnet den minimalen Spannbaum eines ungerichteten gewichteten Graphen (1–30 Kanten, eine pro Zeile: Knoten1, Knoten2, Gewicht) mit zwei Algorithmen: Kruskal sortiert nach Gewicht und prüft mit Union-Find, wobei jede angenommene oder als Zyklus abgelehnte Kante protokolliert wird; Prim startet an einem Anfangsknoten und wählt in jedem Schritt die günstigste die Komponente verlassende Kante und zeigt ihr Wachstum. Schlingen werden übersprungen; ein unzusammenhängender Graph wird mit Komponentenzahl abgelehnt; beide Algorithmen müssen im Gesamtgewicht übereinstimmen (interne Prüfung). Klassiker: A-B 4, A-C 2, B-C 5, B-D 10, C-E 3, D-E 4, D-F 11, E-F 8 → MST-Gewicht 21 (A—C, C—E, A—B, D—E, E—F), B—C als Zyklus abgelehnt.

> Kanonische Seite: https://elysiatools.com/de/tools/minimum-spanning-tree

- **Kategorie:** Math & Numbers

- **Schlagwörter:** minimaler spannbaum, mst, kruskal, prim, union-find, gieriger algorithmus, graph, netzwerkentwurf, spannbaum, diskrete mathematik

## Überblick

Der Minimaler-Spannbaum-Rechner ermittelt den minimalen Spannbaum (MST) für ungerichtete, gewichtete Graphen wahlweise nach dem Algorithmus von Kruskal oder Prim. Das Werkzeug liefert eine transparente Schritt-für-Schritt-Protokollierung inklusive Zykluserkennung via Union-Find oder Komponentenausbreitung, prüft den Graphen auf Zusammenhang und berechnet das minimale Gesamtgewicht exakt.

## Eingaben

- **Kanten (eine pro Zeile: Knoten1, Knoten2, Gewicht)** (textarea): One undirected edge per line: two node names (1–8 letters/digits) and a weight (negatives allowed).
- **Algorithmus** (select)
- **Startknoten (nur Prim, optional)** (text): e.g. D
- **Dezimalstellen** (number)

## Wann verwenden

- Schrittweise Verifikation von Aufgaben zur Graphentheorie und diskreten Mathematik für die Algorithmen von Kruskal und Prim.
- Kostenoptimierte Planung von Leitungs-, Straßen- oder Kommunikationsnetzen zur Vermeidung redundanter Verbindungszyklen.
- Validierung von Kantenentscheidungen und Gesamtgewichten bei zusammenhängenden Graphen mit bis zu 30 Kanten.

## Funktionsweise

- Graphenkanten zeilenweise im Format 'Knoten1 Knoten2 Gewicht' in das Eingabefeld eingeben.
- Den gewünschten Berechnungsalgorithmus (Kruskal mit Sortierung/Union-Find oder Prim mit schrittweisem Komponentenwachstum) auswählen.
- Bei Prim optional einen Startknoten definieren und die gewünschte Anzahl an Dezimalstellen für die Kantengewichte festlegen.
- Die schrittweise Entscheidungshistorie (akzeptierte Kanten vs. Zyklus-Ablehnungen) und das resultierende Gesamtgewicht des Spannbaums ablesen.

## Anwendungsfälle

- Netzwerkinfrastruktur: Minimierung von Glasfaser- oder Stromtrassenkosten bei vollständiger Vernetzung aller Standorte.
- Informatikstudium: Visuelles Nachvollziehen der Arbeitsweise von Greedy-Algorithmen und Datenstrukturen wie Union-Find.
- Logistikplanung: Identifikation der minimal notwendigen Verbindungsrouten zwischen Distributionszentren.

## Häufig gestellte Fragen

### Was passiert, wenn der eingegebene Graph nicht zusammenhängend ist?

Ein unzusammenhängender Graph wird abgewiesen und das Werkzeug gibt die genaue Anzahl der getrennten Zusammenhangskomponenten aus.

### Wie werden Selbstschleifen (Kanten von einem Knoten zu sich selbst) behandelt?

Schlingen werden bei der Berechnung automatisch übersprungen, da sie keinen Beitrag zu einem kreisfreien Spannbaum leisten können.

### Sind negative Kantengewichte im Graphen zulässig?

Ja, sowohl Kruskal als auch Prim verarbeiten negative Kantengewichte fehlerfrei.

### Liefern Kruskal und Prim immer dasselbe Gesamtgewicht?

Ja, bei identischem zusammenhängenden Graphen ist das minimale Gesamtgewicht bei beiden Algorithmen stets exakt gleich.

### Wie viele Kanten können maximal eingegeben werden?

Das Werkzeug unterstützt die Eingabe von 1 bis 30 ungerichteten Kanten pro Berechnung.

## Ähnliche Tools

- [Dichterechner (ρ = m/V)](https://elysiatools.com/de/tools/density-calculator): Berechnet Dichte, Masse oder Volumen aus den anderen beiden, mit spezifischer Dichte und Schwimmverhalten
- [Pumpen-NPSH-Rechner (Netto-Förderhöhe der Saugseite) und Kavitationsprüfung](https://elysiatools.com/de/tools/pump-npsh-calculator): Berechnet die verfügbare Netto-Förderhöhe der Saugseite der Pumpe: NPSH_a = (p_surface - p_vapor)/(ρ·g) + H_static - h_friction (in m). Oberflächen- und Dampfdruck sind absolut; H_static ist positiv bei flutender Saugung (Flüssigkeit über der Pumpe) und negativ bei Saughub (Flüssigkeit unter der Pumpe). Vergleich mit dem NPSH_r der Pumpenkennlinie liefert die Reserve margin = NPSH_a - NPSH_r und das Verhältnis ratio = NPSH_a/NPSH_r; Einstufung safe (sicher), marginal (Reserve < 0,5 m) oder cavitation likely (Kavitation wahrscheinlich). Ist NPSH_r = 0, wird nur NPSH_a ausgegeben. Drücke in Pa/kPa/bar/atm/psi, Länge in m/ft, Dichte in kg/m³/g/cm³/lb/ft³.
- [Wörter in Zahl](https://elysiatools.com/de/tools/words-to-number): Wandelt englische Zahlenwörter in Ziffern um. Behandelt Größenordnungen, „and", Dezimalstellen über „point" und Bindestriche und ersetzt das Zahlen-Segment vor Ort.
- [Adaptives dezentes 12-Punkt-Wasserzeichen](https://elysiatools.com/de/tools/adaptive-12-point-hidden-watermark): Fügt einem Bild oder jedem unterstützten Bild in einem ZIP ein dezentes Textwasserzeichen an allen, zufälligen oder ausgewählten Randpunkten hinzu und wählt je nach lokalem Hintergrund automatisch hellen oder dunklen Kontrast.
- [FENa-Rechner (Fraktionelle Natriumexkretion)](https://elysiatools.com/de/tools/fractional-excretion-sodium): Fraktionelle Natriumexkretion FENa = (Na-Urin×SCr)/(Na-Serum×UCr)×100%. Differenziert oligurische AKI: <1% spricht für prärenale Azotämie (Volumenmangel, Herzinsuffizienz, hepatorenales Syndrom, natriumsparende Zustände); ≥1% für intrinsische Schädigung (typisch ATN, geschädigte Tubuli reabsorbieren Natrium nicht); >4% gelegentlich bei Postobstruktion. Diuretika verfälschen den Wert (FEUrea<35% verwenden); kontrast-/sepsisbedingte ATN kann niedrige FENa zeigen; chronische CKD und Glukosurie erhöhen FENa. Im klinischen Kontext interpretieren. Keine medizinische Beratung.
- [Twitter-/X-Thread-Splitter](https://elysiatools.com/de/tools/twitter-thread-splitter): Fügen Sie einen langen Text ein und teilen Sie ihn in einen nummerierten X-Thread auf, der die 280-Zeichen-Grenze einhält. Trennt an Wort-/Satz-/Absatzgrenzen, fügt 1/N-Nummerierung hinzu, gewichtet CJK- und Vollbreitzeichen korrekt, zählt URLs als 23 Zeichen und zeigt eine X-Karte mit Zeichenzähler.
- [AHU-Leistungsrechner (Kühlen / Heizen)](https://elysiatools.com/de/tools/ahu-capacity-calculator): Berechnet die Leistung eines AHU-Registers aus Ein-/Austrittszustand und dem Massenstrom trockener Luft ṁ_da: Gesamtleistung Qt=ṁ_da·(h1−h2), fühlbar Qs=ṁ_da·cp_ma·(T1−T2) (cp_ma≈1,006+1,86·W), latent Ql=Qt−Qs, SHR=Qs/Qt. Zustände durch Trockenkugel T und einen Feuchteparameter (rel. Feuchte φ oder Feuchtegehalt W); W über Magnus, Enthalpie h=1,006·T+W·(2501+1,86·T). Vorzeichenbehaftetes Ergebnis für Kühlen oder Heizen.
- [Auftriebs-Rechner (Archimedes, F = ρ·V·g)](https://elysiatools.com/de/tools/buoyancy-calculator): Berechnet Auftrieb, Fluiddichte oder verdrängtes Volumen aus zwei davon, mit Schwimm-Analyse

## Beispiele

- [Web Python Bildverarbeitung Beispiele](https://elysiatools.com/de/samples/web-image-processing-python): Web Python Bildverarbeitungsbeispiele mit PIL/Pillow einschließlich Lesen, Speichern, Skalieren und Formatkonvertierung
- [SVG Beispiele](https://elysiatools.com/de/samples/svg-samples): Beispiele für skalierbare Vektorgrafiken (SVG), die verschiedene SVG-Funktionen und -Techniken demonstrieren
- [Android Java Bildverarbeitungsbeispiele](https://elysiatools.com/de/samples/android-image-processing-java): Android Java Bildverarbeitungsbeispiele einschließlich Lesen/Schreiben, Skalierung und Formatkonvertierung
- [Android Kotlin Bildverarbeitungsbeispiele](https://elysiatools.com/de/samples/android-image-processing-kotlin): Android Kotlin Bildverarbeitungsbeispiele einschließlich Lesen/Schreiben, Skalierung und Formatkonvertierung