DAA - Spanning Tree

EIN spanning tree ist eine Teilmenge eines ungerichteten Graphen, bei dem alle Eckpunkte durch eine minimale Anzahl von Kanten verbunden sind.

Wenn alle Eckpunkte in einem Diagramm verbunden sind, gibt es mindestens einen Spannbaum. In einem Diagramm kann mehr als ein Spanning Tree vorhanden sein.

Eigenschaften

• Ein Spanning Tree hat keinen Zyklus.
• Jeder Scheitelpunkt kann von jedem anderen Scheitelpunkt aus erreicht werden.

Beispiel

In der folgenden Grafik bilden die hervorgehobenen Kanten einen Spannbaum.

Minimum Spanning Tree

EIN Minimum Spanning Tree (MST)ist eine Teilmenge von Kanten eines verbundenen gewichteten ungerichteten Graphen, der alle Scheitelpunkte mit dem minimal möglichen Gesamtkantengewicht verbindet. Um einen MST abzuleiten, kann der Prim-Algorithmus oder der Kruskal-Algorithmus verwendet werden. Daher werden wir in diesem Kapitel den Prim-Algorithmus diskutieren.

Wie wir bereits besprochen haben, kann ein Graph mehr als einen Spanning Tree haben. Wenn es gibtn Anzahl der Eckpunkte, die der Spanning Tree haben sollte n - 1Anzahl der Kanten. Wenn in diesem Zusammenhang jede Kante des Diagramms einem Gewicht zugeordnet ist und mehr als ein Spannbaum vorhanden ist, müssen wir den minimalen Spannbaum des Diagramms ermitteln.

Wenn doppelte gewichtete Kanten vorhanden sind, kann der Graph außerdem mehrere minimale Spannbäume aufweisen.

In der obigen Grafik haben wir einen Spanning Tree gezeigt, obwohl dies nicht der minimale Spanning Tree ist. Die Kosten für diesen Spannbaum betragen (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38.

Wir werden den Prim-Algorithmus verwenden, um den minimalen Spannbaum zu finden.

Prims Algorithmus

Prims Algorithmus ist ein gieriger Ansatz, um den minimalen Spannbaum zu finden. In diesem Algorithmus können wir zur Bildung eines MST von einem beliebigen Scheitelpunkt ausgehen.

Algorithm: MST-Prim’s (G, w, r) 
for each u є G.V 
   u.key = ∞ 
   u.∏ = NIL 
r.key = 0 
Q = G.V 
while Q ≠ Ф 
   u = Extract-Min (Q) 
   for each v є G.adj[u] 
      if each v є Q and w(u, v) < v.key 
         v.∏ = u 
         v.key = w(u, v)

Die Funktion Extract-Min gibt den Scheitelpunkt mit minimalen Kantenkosten zurück. Diese Funktion funktioniert auf Min-Heap.

Beispiel

Mit dem Prim-Algorithmus können wir von jedem Scheitelpunkt aus beginnen. Lassen Sie uns vom Scheitelpunkt aus beginnen 1.

Scheitel 3 ist mit dem Scheitelpunkt verbunden 1 mit minimalen Kantenkosten, daher Kante (1, 2) wird dem Spanning Tree hinzugefügt.

Als nächstes Rand (2, 3) wird als das Minimum unter den Kanten angesehen {(1, 2), (2, 3), (3, 4), (3, 7)}.

Im nächsten Schritt bekommen wir Rand (3, 4) und (2, 4)mit minimalen Kosten. Kante(3, 4) wird zufällig ausgewählt.

In ähnlicher Weise Kanten (4, 5), (5, 7), (7, 8), (6, 8) und (6, 9)ausgewählt sind. Da alle Scheitelpunkte besucht werden, stoppt der Algorithmus jetzt.

Die Kosten für den Spanning Tree betragen (2 + 2 + 3 + 2 + 5 + 2 + 3 + 4) = 23. In diesem Diagramm gibt es keinen Spanning Tree mehr mit Kosten von weniger als 23.