Kruskalalgorithmus

Minimum Spanning Tree

Eine Grafik, die keine Anweisungen hat. Jedes Diagramm muss einen Pfad von einem Knoten zum anderen Knoten haben. Ein Spanning -Baum ist auch ein ungerichteter verbundenes Diagramm, in dem alle Knoten des Diagramms mit minimalen Kanten vorhanden sind. Wenn ein Spanning -Baum nicht alle Knoten des Diagramms hat, können wir nicht sagen, dass es sich um einen Spanning -Baum handelt. Das Spanning-Tree-Gesamtgewicht ist geringer als das ursprüngliche Gewicht des Diagramms. Der Spanning -Baum hat auch keinen Zyklus. Jedes Diagramm hat mehr als einen Spannungsbaum, aber nur eine davon wird einzigartig sein. Wir nennen es einen minimalen Spannungsbaum, da wir versuchen, ein vollständiges Diagramm mit allen Knoten zu erstellen, während wir das Gewicht niedrig halten.

Verstehen wir den minimalen Spannungsbaum mit einem Beispiel. Wie wir wissen, ist der minimale Spanning -Baum Teil des Diagramms, aber mit weniger Kosten. Dieses Szenario kann also mit einem Beispiel veranschaulicht werden. Nehmen wir an, wir haben eine solche Grafik.

Das obige Diagramm kann auf unterschiedliche Weise angeordnet werden, damit der Graphenzyklus entfernt wird, oder es ist kein MST (minimaler Spanning -Baum). Also entfernen wir den Zyklus aus dem Diagramm und zählen die Gesamtkosten des Diagramms. Wir haben vier Knoten oder Eckpunkte (A, B, C und D).

Fall 1:

Nach dem Entfernen des Zyklus aus dem Diagramm beträgt die oben genannte MST -Kosten (Mindestspannungsbaum) 56.

Fall -2:

Nach dem Entfernen des Zyklus aus dem Diagramm beträgt die oben genannte MST -Kosten (Mindestspannungsbaum) 53.

Fall - 3:

Nach dem Entfernen des Zyklus aus dem Diagramm beträgt die oben genannte MST -Kosten (Mindestspannungsbaum) 41.

Wir können sehen, dass das letzte Diagramm der Gesamtkosten von Case-3 im Vergleich zu den beiden anderen Grafiken viel niedriger ist. Diese Grafik ist also unser endgültiger MST (minimaler Spanning -Baum) für das Originaldiagramm. Das Motiv des Algoriths des Primes oder Kruskal besteht darin, die Grafikkosten so niedrig wie möglich zu finden. Das ist unser Motiv in diesem Artikel, diesen MST zu erklären.

Mit Hilfe der folgenden zwei Methoden können wir einen Spanning -Baum zeichnen:

1. Kruskals Algorithmus
2. Prims Algorithmus

In diesem Artikel werden wir den Algorithmus von Kruskal diskutieren. Der Algorithmus von Prim wird im nächsten Artikel erörtert.

Kruskals Algorithmus

Der Algorithmus von Kruskal ist im Vergleich zu Prims Algorithmus sehr einfach zu implementieren. In diesem Algorithmus startet der Algorithmus von Kruskal mit allen Scheitelpunkten des Diagramms. Wir wählen den Breit mit minimaler Gewichtskante und erstellen den minimalen Spannungsbaum. Wir wählen eine andere Kante mit dem minimalen Gewicht und fügen sie dem minimalen Spannungsbaum hinzu. Dieser Vorgang wird fortgesetzt, bis wir nicht alle Originalgraphenknoten hinzufügen. Sobald alle Knoten in der Grafik zum minimalen Spannungsbaum hinzugefügt werden, stoppt der Algorithmus. Während des Erstellens des minimalen Spannungsbaums eines Graphen müssen wir uns auch um diesen Diagramm kümmern und keine Zyklen erstellen, da sich die Zyklen nicht im minimalen Spannungsbaum befinden sollten.

Wenn also ein Knoten den Zyklus im minimalen Spannungsbaum erstellt, wählen wir den anderen Knoten, auch wenn das Gewicht dieses Knotens größer ist als der vorherige Knoten, der den Zyklus erstellt.

Der Algorithmus von Kruskal unterscheidet sich von Prims Algorithmus. Der Algorithmus von Prim startet beim Erstellen eines minimalen Spannungsbaum. Der Algorithmus von Kruskal kümmert sich jedoch nicht um den Adjazenzknoten und wählt immer diesen Knoten aus, der weniger Gewicht hat, aber dieser Knoten sollte keinen Zyklus im Minimum Spanning -Baum erstellen.

Kruskals Algorithmus -Schritte:

Die folgenden Schritte werden beim Schreiben des C ++ - Code für den Algorithmus von Kruskal unternommen.

1. Wir erstellen ein Array, um Gruppen der Knoten oder Scheitelpunkte des Diagramms zu speichern.
2. Wir erstellen ein weiteres Array, um Grafikkanten Gewichte zu speichern.
3. Für den Spanning -Baum erstellen wir ein neues Array.
4. Wir arrangieren das Kantenarray in aufsteigender Reihenfolge.
5. Wir wiederholen Schritt 6, bis das Array sortierter Kantengewichte nicht leer ist.
6. Wir vergleichen die beiden Gruppen nebeneinander. Wenn ein Knoten einer Gruppe nicht mit dem anderen Knoten übereinstimmt, fügen wir dem Spanning -Baum diese Kante hinzu und fügen ihn in dieselbe Gruppe hinzu.
7. Durch alle Kanten des Spanning Tree durchführen, um das Gesamtgewicht zu bestimmen.

Jetzt werden wir die obigen Algorithmusschritte mit einem Beispiel implementieren. Wir haben die folgende Grafik und werden den minimalen Spanning -Baum für diesen Diagramm herausfinden.

Nach dem Algorithmus wählen wir also zunächst die kleinste Gewichtskante, nämlich AB. Also haben wir diese Kante ausgewählt und sie in der Spanning Tree Array gehalten. Das Gewicht der AB -Kante beträgt 9.

Jetzt wählen wir die nächst kleinste Gewichtskante, CD und halten diese Kante im minimalen Spanning -Baumarray. Das CD -Kantengewicht beträgt 12.

Die nächst kleinste Kante, die wir bekamen, war BC, das wir in der Array behalten haben. Die gewichtete BC -Kante ist 17.

Unser Algorithmus wird hier aufhören, weil wir alle Scheitelpunkte eines Diagramms haben und wir unseren Mindestspannungsbaum haben. Das Gesamtgewicht dieses MST beträgt 9 + 12 + 17 = 38.

Programm: Das folgende ist ein C ++ - Code für den Algorithmus von Kruskal.

#enthalten
#enthalten
#enthalten
Klasse Edgegraph
öffentlich:
int nodestart;
int nodeend;
int wght;
EdgeGraph ()
EdgeGraph (int node_1, int node_2, int Gewicht): nodestart (node_1),
nodeend (node_2), wght (Gewicht)
;
bool CompareedGecost (const Edgegraph A, const Edgegraph B)
Rückkehr a.wght < b.wght;

Klasse G
Privatgelände:
int num_of_nodes;
STD :: Vektor EdgeGraphList;
STD :: Vektor Elternknoten;
STD :: Vektor Ranknode;
öffentlich:
G()
G (int num_of_nodes)

this-> num_of_nodes = num_of_nodes;
Elternknoten.Größe (num_of_nodes);
Ranknode.Größe (num_of_nodes);

void addiertgraph (EdgeGraph e);
int findParentnode (int node);
void kruskalmst_algo (std :: vector&);
void DisplayEdgeGraphs (STD :: Vektor&);
;
void g :: AddgeGraph (EdgeGraph e)
EdgeGraphList.push_back (e);

int g :: findParentnode (int node)
if (Knoten != ParentNode [Knoten])
ParentNode [Knoten] = findParentNode (ParentNode [Knoten]);
Return ParentNode [Knoten];

void g :: displayEdgeGraphs (std :: vector& mst)
int cost = 0;
std :: Cout << "EdgeGraphs of MST : ";
für (auto & e: mst)
std :: Cout << "[" << e.nodeSTART << "-" << e.nodeEND
<< "](" << e.wght << ") ";
Kosten += e.wght;

std :: Cout << "\n Kruskal MST Cost : " << cost << std :: endl;

// Dies ist die Hauptfunktion des Hauptkruskal -Algorithmus, die suchen
// der minimale Spannungsbaum.
void g :: kruskalmst_algo (std :: vector& Ergebnis)
für (int i = 0; iParentNode [i] = i;
Ranknode [i] = 0;

Sortieren (EdgeGraphList.begin (), EdgeGraphList.Ende(),
Vergleiche);
für (Auto & E: EdgeGraphList)
int root_1 = findParentnode (e.nodestart);
int root_2 = findParentnode (e.Nodeend);
if (root_1 != root_2)
Ergebnis.push_back (e);
if (ranknode [root_1] < rankNode[root_2])
ParentNode [root_1] = root_2;
Ranknode [root_2] ++;
anders
ParentNode [root_2] = root_1;
Ranknode [root_1] ++;




int main ()
int num_of_nodes = 6; // (0, 1, 2, 3, 4, 5)
EdgeGraph E1 (0, 1, 4);
EdgeGraph E2 (0, 2, 1);
EdgeGraph E3 (0, 3, 5);
Edgegraph E4 (1, 3, 2);
Edgegraph E5 (1, 4, 3);
Edgegraph E6 (1, 5, 3);
Edgegraph E7 (2, 3, 2);
Edgegraph E8 (2, 4, 8);
Edgegraph E9 (3, 4, 1);
EdgeGraph E10 (4, 5, 3);
G g1 (num_of_nodes);
G1.Hinzugefügt (E1);
G1.Hinzugefügt (e2);
G1.Hinzugefügt (E3);
G1.Hinzugefügt (E4);
G1.Hinzugefügt (E5);
G1.Hinzugefügt (E6);
G1.Hinzugefügt (e7);
G1.Hinzugefügt (E8);
G1.Hinzugefügt (E9);
G1.Hinzugefügt (e10);
STD :: Vektor MST; // Dies speichert den minimalen Spannungsbaum
G1.Kruskalmst_algo (MST);
G1.DisplayEdgeGraphs (MST);
Rückkehr 0;

Ausgang:

Kanten von MST: [0-2] (1) [3-4] (1) [1-3] (2) [2-3] (2) [1-5] (3)
Kruskal MST Kosten: 9

Abschluss:

Wir haben Kruskals Mindestspannungsbaum untersucht, was die erste Präferenz der meisten Menschen ist, wenn sie das MST -Diagramm aus einem Diagramm finden müssen. Der Algorithmus von Kruskal ist in einer realen Anwendung einfach zu erfassen und zu implementieren. Wie der Algorithmus von Prim ist auch der Algorithmus von Kruskal in realen Anwendungen sehr nützlich. Wir müssen diesen Algorithmus also verstehen.