Ein Minimum Spanning Tree ( MST ) oder Minimum Weight Spanning Tree ist eine Teilmenge der Kanten eines zusammenhängenden, kantengewichteten ungerichteten Graphen, der alle Knoten miteinander verbindet, ohne Zyklen und mit dem minimal möglichen Gesamtkantengewicht. Das heißt, es ist ein aufspannender Baum, dessen Summe der Kantengewichte kleiner oder gleich dem Gewicht jedes anderen aufspannenden Baums ist. Allgemeiner gesagt hat jeder kantengewichtete ungerichtete Graph (nicht notwendigerweise zusammenhängend) einen minimalen Spannwald , der eine Vereinigung der minimalen Spannbäume für seine verbundenen Komponenten ist. Das Gewicht eines Spannbaums ist die Summe der Gewichte, die jeder Kante des Spannbaums gegeben wird. Es gibt zwei Methoden, um den minimalen Spanning Tree zu finden:
- Kruskals Algorithmus
- Prims Algorithmus
Contents
Prims Algorithmus
Der Algorithmus von Prim wird verwendet, um den minimalen Spannbaum aus einem Graphen zu finden. Der Algorithmus von Prim findet die Teilmenge der Kanten, die jeden Knoten des Graphen enthält, so dass die Summe der Gewichte der Kanten minimiert werden kann. Der Algorithmus von Prim beginnt mit dem einzelnen Knoten und untersucht bei jedem Schritt alle benachbarten Knoten mit allen Verbindungskanten. Die Kanten mit den minimalen Gewichtungen, die keine Zyklen im Diagramm verursachen, werden ausgewählt.
Anwendungen des Algorithmus von Prim
- Verlegen von Kabeln elektrischer Leitungen
- Im Netzwerkdesign
- Erstellen von Protokollen in Netzwerkzyklen
Fakten über Prims Algorithmus
- Dieser Algorithmus dient zum Erhalten eines minimalen Spannbaums durch Auswählen der benachbarten Scheitel von bereits ausgewählten Scheiteln.
- Der Algorithmus von Prim beginnt mit einem Knoten.
- Die Algorithmen von Prim reichen von einem Knoten zum anderen.
- Es durchquert einen Knoten mehr als einmal, um den Mindestabstand zu erhalten.
- Der Algorithmus von Prim hat eine Zeitkomplexität von O(V2), wobei V die Anzahl der Scheitelpunkte ist und mit Fibonacci-Heaps auf O(E + log V) verbessert werden kann.
- Der Algorithmus von Prim liefert eine verbundene Komponente und funktioniert nur auf einem verbundenen Graphen.
- Der Algorithmus von Prim läuft in dichten Graphen schneller.
Kruskals Algorithmus
Der Algorithmus von Kruskal als ein Algorithmus mit minimalem Spannbaum verwendet eine andere Logik als der Algorithmus von Prim, um den MST eines Graphen zu finden. Anstatt von einem Scheitelpunkt aus zu beginnen, sortiert Kruskals Algorithmus alle Kanten von niedriger bis hoher Gewichtung und fügt die niedrigsten Kanten hinzu, bis alle Scheitelpunkte bedeckt sind, wobei die Kanten ignoriert werden, die einen Zyklus erzeugen. Der Algorithmus von Kruskal folgt dem gierigen Ansatz, der in jeder Phase der Fokussierung auf ein globales Optimum eine optimale Lösung findet.
Anwendungen des Kruskal-Algorithmus
- Elektrische Verdrahtungsanordnung
- Computernetzwerk (LAN-Verbindung)
Fakten über Kruskals Algorithmus
- Dieser Algorithmus dient zum Erhalten eines minimalen Spannbaums, aber es ist nicht notwendig, benachbarte Scheitel von bereits ausgewählten Scheiteln auszuwählen.
- Der Algorithmus von Kruskal beginnt mit einer Kante.
- Der Algorithmus von Kruskal wählt die Kanten so aus, dass die Position der Kante nicht auf dem letzten Schritt basiert.
- Es durchquert einen Knoten nur einmal.
- Die Zeitkomplexität des Kruskal-Algorithmus ist O(E log V), wobei V die Anzahl der Knoten ist.
- Der Algorithmus von Kruskal kann in jeder Instanz einen Wald (nicht verbundene Komponenten) generieren und auch mit nicht verbundenen Komponenten arbeiten.
- Der Algorithmus von Kruskal läuft in spärlichen Graphen schneller.
Lesen Sie auch: Unterschied zwischen Baum und Graph
Unterschied zwischen Prims und Kruskals Algorithmus in Tabellenform
| VERGLEICHSGRUNDLAGE | PRIMs ALGORITHMUS | KRUSKALS ALGORITHMUS |
| Beschreibung | Dieser Algorithmus dient zum Erhalten eines minimalen Spannbaums durch Auswählen der benachbarten Scheitel von bereits ausgewählten Scheiteln. | Dieser Algorithmus dient zum Erhalten eines minimalen Spannbaums, aber es ist nicht notwendig, benachbarte Scheitel von bereits ausgewählten Scheiteln auszuwählen. |
| Einleitung | Der Algorithmus von Prim beginnt mit einem Knoten. | Der Algorithmus von Kruskal beginnt mit einer Kante. |
| Spannend | Die Algorithmen von Prim reichen von einem Knoten zum anderen. | Der Algorithmus von Kruskal wählt die Kanten so aus, dass die Position der Kante nicht auf dem letzten Schritt basiert. |
| Traversieren | Es durchquert einen Knoten mehr als einmal, um den Mindestabstand zu erhalten. | Es durchquert einen Knoten nur einmal. |
| Zeitkomplexität | Der Algorithmus von Prim hat eine Zeitkomplexität von O(V2), wobei V die Anzahl der Scheitelpunkte ist und mit Fibonacci-Heaps auf O(E + log V) verbessert werden kann. | Die Zeitkomplexität des Kruskal-Algorithmus ist O(E log V), wobei V die Anzahl der Knoten ist. |
| Angeschlossene Komponenten | Der Algorithmus von Prim liefert eine verbundene Komponente und funktioniert nur auf einem verbundenen Graphen. | Der Algorithmus von Kruskal kann in jeder Instanz einen Wald (nicht verbundene Komponenten) generieren und auch mit nicht verbundenen Komponenten arbeiten. |
| Geschwindigkeit | Der Algorithmus von Prim läuft in dichten Graphen schneller. | Der Algorithmus von Kruskal läuft in spärlichen Graphen schneller. |
Lesen Sie auch: Unterschied zwischen DFS und BFS bei künstlicher Intelligenz