A minimaler Spannbaum (MST) ist definiert als a Spannbaum der unter allen möglichen Spannbäumen das geringste Gewicht hat
A Spannbaum ist definiert als ein baumartiger Teilgraph eines verbundenen, ungerichteten Graphen, der alle Eckpunkte des Graphen enthält. Oder, um es mit Laien auszudrücken: Es ist eine Teilmenge der Kanten des Graphen, die einen Baum bildet ( azyklisch ), wobei jeder Knoten des Diagramms Teil des Baums ist.
Der minimale Spannbaum hat alle Eigenschaften eines Spannbaums mit der zusätzlichen Einschränkung, dass er unter allen möglichen Spannbäumen die minimal möglichen Gewichte aufweist. Wie bei einem Spanning Tree kann es auch für einen Graphen viele mögliche MSTs geben.
Eigenschaften eines Spanning Tree:
Der Spannbaum enthält die unten aufgeführten Grundsätze :
Laufzeit Fehler
- Die Anzahl der Eckpunkte ( IN ) im Diagramm und der Spanning Tree ist derselbe.
- Es gibt eine feste Anzahl von Kanten im Spannbaum, die um eins kleiner ist als die Gesamtzahl der Eckpunkte ( UND = V-1 ).
- Der Spannbaum sollte nicht sein getrennt , da es nur eine einzige Komponentenquelle geben sollte, nicht mehr.
- Der Spannbaum sollte sein azyklisch, welche bedeutet, dass es keinen Zyklus im Baum geben würde.
- Die Gesamtkosten (oder das Gesamtgewicht) des Spannbaums sind definiert als die Summe der Kantengewichte aller Kanten des Spannbaums.
- Es kann viele mögliche Spannbäume für einen Graphen geben.
Minimaler Spanning Tree:
A minimaler Spannbaum (MST) ist definiert als a Spannbaum der unter allen möglichen Spannbäumen das geringste Gewicht hat.
Der minimale Spannbaum hat alle Eigenschaften eines Spannbaums mit der zusätzlichen Einschränkung, dass er unter allen möglichen Spannbäumen die minimal möglichen Gewichte aufweist. Wie bei einem Spanning Tree kann es auch für einen Graphen viele mögliche MSTs geben.
10 1 Million
- Schauen wir uns den MST des obigen Beispieldiagramms an.
Minimaler Spanning Tree
Algorithmen zum Ermitteln des minimalen Spanning Tree:
Es gibt mehrere Algorithmen, um den minimalen Spannbaum aus einem bestimmten Diagramm zu ermitteln. Einige davon sind unten aufgeführt:
Kruskals Minimum Spanning Tree-Algorithmus:
Dies ist einer der beliebtesten Algorithmen zum Ermitteln des minimalen Spannbaums aus einem verbundenen, ungerichteten Graphen. Das ist ein Zunächst werden alle Kanten des Diagramms nach ihren Gewichten sortiert.
Dieser Algorithmus kann mithilfe einer DSU-Datenstruktur (Disjoint-Set) effizient implementiert werden, um die verbundenen Komponenten des Diagramms zu verfolgen. Dies wird in einer Vielzahl praktischer Anwendungen wie Netzwerkdesign, Clustering und Datenanalyse verwendet.
Folgen Sie dem Artikel auf Kruskals Minimum Spanning Tree-Algorithmus zum besseren Verständnis und zur Implementierung des Algorithmus.
Prims Minimum Spanning Tree-Algorithmus:
Dies ist auch ein gieriger Algorithmus. Dieser Algorithmus hat den folgenden Workflow:
- Es beginnt mit der Auswahl eines beliebigen Scheitelpunkts und dem anschließenden Hinzufügen zum MST.
- Anschließend wird wiederholt nach dem minimalen Kantengewicht gesucht, das einen Scheitelpunkt des MST mit einem anderen Scheitelpunkt verbindet, der sich noch nicht im MST befindet.
- Dieser Vorgang wird fortgesetzt, bis alle Scheitelpunkte im MST enthalten sind.
Um die Kante mit minimalem Gewicht für jede Iteration effizient auszuwählen, verwendet dieser Algorithmus „priority_queue“, um die Scheitelpunkte sortiert nach ihrem aktuellen minimalen Kantengewicht zu speichern. Gleichzeitig verfolgt es auch den MST mithilfe eines Arrays oder einer anderen Datenstruktur, die für den gespeicherten Datentyp geeignet ist.
Gültige Java-Bezeichner
Dieser Algorithmus kann in verschiedenen Szenarien verwendet werden, beispielsweise zur Bildsegmentierung basierend auf Farbe, Textur oder anderen Merkmalen. Für die Routenplanung, etwa um den kürzesten Weg zwischen zwei Punkten zu finden, dem ein Lieferwagen folgen kann.
Folgen Sie dem Artikel auf Prims Minimum Spanning Tree-Algorithmus zum besseren Verständnis und zur Implementierung dieses Algorithmus.
Boruvkas Minimum Spanning Tree-Algorithmus:
Dies ist auch ein Graph-Traversal-Algorithmus, der verwendet wird, um den minimalen Spannbaum eines verbundenen, ungerichteten Graphen zu finden. Dies ist einer der ältesten Algorithmen. Der Algorithmus baut iterativ den minimalen Spannbaum auf, beginnend mit jedem Scheitelpunkt im Diagramm als eigenem Baum. In jeder Iteration findet der Algorithmus die günstigste Kante, die einen Baum mit einem anderen Baum verbindet, und fügt diese Kante dem minimal aufspannenden Baum hinzu. Dies ähnelt fast dem Prim-Algorithmus zum Finden des minimalen Spannbaums. Der Algorithmus hat den folgenden Workflow:
Zeichenfolge in c
- Initialisieren Sie einen Wald aus Bäumen, wobei jeder Scheitelpunkt im Diagramm ein eigener Baum ist.
- Für jeden Baum im Wald:
- Finden Sie die günstigste Kante, die ihn mit einem anderen Baum verbindet. Fügen Sie diese Kanten zum minimalen Spannbaum hinzu.
- Aktualisieren Sie den Wald, indem Sie die durch die hinzugefügten Kanten verbundenen Bäume zusammenführen.
- Wiederholen Sie die obigen Schritte, bis die Gesamtstruktur nur noch einen Baum enthält, der den minimalen Spannbaum darstellt.
Der Algorithmus kann mithilfe einer Datenstruktur wie einer Prioritätswarteschlange implementiert werden, um effizient die günstigste Kante zwischen Bäumen zu finden. Der Boruvka-Algorithmus ist ein einfacher und leicht zu implementierender Algorithmus zum Finden minimal aufspannender Bäume, er ist jedoch möglicherweise nicht so effizient wie andere Algorithmen für große Diagramme mit vielen Kanten.
Folgen Sie dem Artikel auf Boruvkas Minimum Spanning Tree-Algorithmus zum besseren Verständnis und zur Implementierung dieses Algorithmus.
Um mehr über die Eigenschaften und Eigenschaften von Minimum Spanning Tree zu erfahren, klicken Sie auf Hier.
Anwendungen von Minimum Spanning Trees:
- Netzwerk-Design : Spanning Trees können im Netzwerkdesign verwendet werden, um die Mindestanzahl von Verbindungen zu ermitteln, die zum Verbinden aller Knoten erforderlich sind. Insbesondere Minimum Spanning Trees können dazu beitragen, die Kosten der Verbindungen durch die Auswahl der günstigsten Kanten zu minimieren.
- Bildverarbeitung : Spanning Trees können in der Bildverarbeitung verwendet werden, um Regionen ähnlicher Intensität oder Farbe zu identifizieren, was für Segmentierungs- und Klassifizierungsaufgaben nützlich sein kann.
- Biologie : Spanning Trees und Minimum Spanning Trees können in der Biologie verwendet werden, um phylogenetische Bäume zu konstruieren, um evolutionäre Beziehungen zwischen Arten oder Genen darzustellen.
- Analyse sozialer Netzwerke : Spanning Trees und Minimum Spanning Trees können in der Analyse sozialer Netzwerke verwendet werden, um wichtige Verbindungen und Beziehungen zwischen Einzelpersonen oder Gruppen zu identifizieren.
Einige beliebte Interviewprobleme bei MST
| 1. | Finden Sie die Mindestkosten für die Verbindung aller Städte | Üben |
Einige FAQs zu Minimum Spanning Trees:
1. Kann es für einen bestimmten Graphen mehrere Bäume mit minimaler Spannweite geben?
Ja, ein Diagramm kann mehrere minimale Spannbäume haben, wenn es mehrere Kantensätze mit demselben minimalen Gesamtgewicht gibt.
2. Können der Kruskal-Algorithmus und der Prim-Algorithmus für gerichtete Graphen verwendet werden?
Nein, Kruskals Algorithmus und Prims Algorithmus sind nur für ungerichtete Graphen konzipiert.
3. Kann ein nicht zusammenhängender Graph einen minimalen Spannbaum haben?
Nein, ein nicht verbundener Graph kann keinen Spanning Tree haben, da er nicht alle Eckpunkte umfasst. Daher kann es auch keinen minimalen Spannbaum geben.
Zeile Autocad-Befehl
4. Kann mit dem Dijkstra-Algorithmus ein minimaler Spannbaum gefunden werden?
Nein, der Dijkstra-Algorithmus wird verwendet, um den kürzesten Weg zwischen zwei Eckpunkten in einem gewichteten Diagramm zu finden. Es ist nicht darauf ausgelegt, einen minimalen Spannbaum zu finden.
5. Wie groß ist die zeitliche Komplexität der Algorithmen von Kruskal und Prim?
Sowohl Kruskals als auch Prims Algorithmen haben eine Zeitkomplexität von O(ElogE) , wobei E die Anzahl der Kanten im Diagramm ist.