Algorytm Kruskala

Minimalne drzewo rozpinające

Wykres, który nie ma wskazówek, nazywa się niekierowanym wykresem. Każdy wykres musi mieć ścieżkę z jednego węzła do innego węzła. Drzewo rozpiętości to również niekierżawiony podłączony wykres, na którym wszystkie węzły wykresu są obecne z minimalnymi krawędziami. Jeśli drzewo spinka nie ma wszystkich węzłów wykresu, nie możemy powiedzieć, że jest to drzewo spinka. Całkowite ciężary drzewa spinka będą mniejsze niż oryginalna waga wykresu, ponieważ podłączyliśmy go przez minimalną wagę. Drzewo rozpiętości również nie ma cyklu. Każdy wykres ma więcej niż jedno drzewo spinki, ale tylko jeden z nich będzie wyjątkowy. Nazywamy to minimalnym drzewem rozpinającym, ponieważ próbujemy utworzyć pełny wykres ze wszystkimi węzłami, jednocześnie utrzymując niską wagę.

Zrozumiemy minimalne drzewo rozpinające z przykładem. Tak więc, jak wiemy, minimalne drzewo rozpinające jest częścią wykresu, ale z mniejszymi kosztami. Więc ten scenariusz można zilustrować przykładem. Załóżmy, że mamy taki wykres.

Powyższy wykres może być ułożony na różne sposoby, aby cykl wykresu został usunięty, w przeciwnym razie nie będzie to MST (minimalne drzewo rozpinające). Więc usuniemy cykl z wykresu i policzamy całkowity koszt wykresu. Mamy cztery węzły lub wierzchołki (A, B, C i D).

Przypadek 1:

Po usunięciu cyklu z wykresu powyższy koszt wykresu MST (minimalny drzewo rozpinającego) wynosi 56.

Przypadek -2:

Po usunięciu cyklu z wykresu powyższy koszt wykresu MST (minimalny drzewo rozpinającego) wynosi 53.

Przypadek - 3:

Po usunięciu cyklu z wykresu powyższy koszt wykresu MST (minimum.

Widzimy, że ostatni wykres całkowitego kosztu Case-3 jest znacznie niższy w porównaniu z pozostałymi dwoma wykresami. Tak więc ten wykres jest naszym ostatnim mST (minimalne drzewo rozpinające) dla oryginalnego wykresu. Motywem algorytmów Prim lub Kruskala jest znalezienie kosztu wykresu jak najniższe. To jest nasz motyw w tym artykule do wyjaśnienia tego MST.

Możemy narysować drzewo opinające za pomocą następujących dwóch metod:

1. Algorytm Kruskala
2. Algorytm Prim

W tym artykule omówimy algorytm Kruskala. Algorytm Prim zostanie omówiony w następnym artykule.

Algorytm Kruskala

Algorytm Kruskala jest bardzo łatwy do wdrożenia w porównaniu z algorytmem Prim, ponieważ nie musimy dbać o wierzchołki sąsiedności w tym algorytmie. W tym algorytmie algorytm Kruskala zaczyna się od wszystkich wierzchołków wykresu. Wybieramy minimalną krawędzi masy i zaczynamy tworzyć minimalne drzewo rozpinające. Wybieramy kolejną krawędź o minimalnej masie i dodajemy ją do minimalnego drzewa rozpinającego. Ten proces trwa, dopóki nie dodamy wszystkich oryginalnych węzłów wykresowych. Gdy wszystkie węzły na wykresie zostaną dodane do minimalnego drzewa rozpinającego, algorytm się zatrzyma. Podczas tworzenia minimalnego drzewa rozpinającego wykresu musimy również zająć się tym wykresem, nie tworząc żadnych cykli, ponieważ cykle nie powinny znajdować.

Tak więc, jeśli jakikolwiek węzeł tworzy cykl w minimalnym drzewie rozpinającym, wybieramy drugi węzeł, nawet jeśli waga tego węzła jest większa niż poprzedni węzeł, który tworzy cykl.

Algorytm Kruskala różni się od algorytmu Prim. Algorytm Prim, podczas tworzenia minimalnego drzewa rozpinającego, zaczyna od dowolnego węzła lub wertice, a następnie dodaje kolejny węzeł lub wertice tylko z węzłów sąsiadujących. Ale algorytm Kruskala nie dba o węzeł sąsiedności i zawsze wybiera ten węzeł, który ma mniejszą wagę, ale ten węzeł nie powinien tworzyć cyklu w minimalnym drzewie rozpinającym.

Algorytm Kruskala kroki:

Podczas pisania kodu C ++ dla algorytmu Kruskala są podejmowane następujące kroki.

1. Tworzymy tablicę do przechowywania grup węzłów lub wierzchołków wykresu.
2. Tworzymy kolejną tablicę do przechowywania krawędzi krawędzi.
3. Dla drzewa spinka tworzymy nową tablicę.
4. Umieszczamy tablicę krawędzi w kolejności rosnącej.
5. Powtarzamy krok 6, aż szereg posortowanych ciężarów krawędzi nie będzie pusta.
6. Porównujemy dwie grupy obok siebie. W takim przypadku, jeśli jeden węzeł grupy nie pasuje do drugiego węzła, dodajemy tę krawędź do drzewa rozpinającego i dodajemy ją do tej samej grupy.
7. Iteruj wszystkie krawędzie drzewa spinka, aby określić jego całkowitą wagę.

Teraz zaimplementujemy powyższe kroki algorytmu za pomocą przykładu. Mamy poniższy wykres i dowiemy się minimalnego drzewa rozpinającego się dla tego wykresu.

Zatem, zgodnie z algorytmem, najpierw wybieramy najmniejszą krawędź ciężarów, czyli AB. Więc wybraliśmy tę krawędź i trzymaliśmy ją w macierzy drzew spinka. Waga krawędzi AB wynosi 9.

Teraz wybieramy następną najmniejszą krawędź, CD, i utrzymujemy tę krawędź w minimalnej tablicy drzew obejmujących. Waga krawędzi CD wynosi 12.

Kolejną najmniejszą przewagą, jaką otrzymaliśmy, był BC, którą trzymaliśmy w tablicy. Ważona krawędź BC wynosi 17.

Nasz algorytm zatrzyma się tutaj, ponieważ mamy wszystkie wierzchołki wykresu i mamy nasze minimalne drzewo spinka. Całkowita waga tego MST wynosi 9 + 12 + 17 = 38.

Program: Poniżej to kod C ++ dla algorytmu Kruskala.

#włączać
#włączać
#włączać
klasa Edgegraph
publiczny:
int nodestart;
int nodeend;
int wght;
Edgegraph ()
Edgegraph (int node_1, int node_2, int waga): nodeStart (node_1),
nodeend (node_2), wght (waga)
;
bool compareedgecost (const edgegraph a, const edgegraph b)
Zwrot a.Wght < b.wght;

Klasa G
prywatny:
int num_of_nodes;
STD :: wektor EdgegraphList;
STD :: wektor ParentNode;
STD :: wektor RankNode;
publiczny:
G()
G (int num_of_nodes)

this-> num_of_nodes = num_of_nodes;
ParentNode.rozmiar (num_of_nodes);
RankNode.rozmiar (num_of_nodes);

void addGegraph (edgegraph e);
int findParentNode (int node);
void Kruskalmst_Algo (std :: vectorI);
void displayEdgegraphs (std :: wektorI);
;
void g :: addGegraph (edgegraph e)
EdgegraphList.push_back (e);

int g :: findParentNode (int node)
if (węzeł != ma nadrzędny [węzeł])
ma nadrzędny [węzeł] = findParentNode (parynode [węzeł]);
return nadrzędny [węzeł];

void G :: DisplayEdgegraphs (std :: wektor& mST)
Int Cost = 0;
STD :: Cout << "EdgeGraphs of MST : ";
dla (auto i e: mST)
STD :: Cout << "[" << e.nodeSTART << "-" << e.nodeEND
<< "](" << e.wght << ") ";
koszt += e.Wght;

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

// To jest główna funkcja algorytmu Kruskala, która wyszukuje
// minimalne drzewo rozpinające.
void g :: kruskalmst_algo (std :: vector& wynik)
dla (int i = 0; imacierz [i] = i;
RankNode [i] = 0;

Sort (EdgegraphList.początek (), EdgeGraphList.koniec(),
PorównajgEdGecost);
dla (auto i e: edgegraphList)
int root_1 = findParentNode (e.nodestart);
int root_2 = findParentNode (e.nodeend);
if (root_1 != root_2)
wynik.push_back (e);
if (ranknode [root_1] < rankNode[root_2])
ma nadrzędny [root_1] = root_2;
RankNode [root_2] ++;
w przeciwnym razie
ma nadrzędny [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.AddGegraph (e1);
G1.AddGegraph (E2);
G1.AddGeGraph (e3);
G1.AddGegraph (e4);
G1.AddGegraph (e5);
G1.AddGeGraph (e6);
G1.AddGegraph (e7);
G1.AddGegraph (e8);
G1.AddGegraph (E9);
G1.AddGeGraph (E10);
STD :: wektor mST; // to będzie przechowywać minimalne drzewo spinka
G1.Kruskalmst_algo (MST);
G1.DisplayEdgegraphs (MST);
powrót 0;

Wyjście:

Edgegraphs MST: [0-2] (1) [3-4] (1) [1-3] (2) [2-3] (2) [1-5] (3)
Kruskal MST Koszt: 9

Wniosek:

Badaliśmy minimalne drzewo rozpinające Kruskala, które jest pierwszą preferencją większości ludzi, gdy muszą znaleźć wykres MST z wykresu. Algorytm Kruskala jest łatwy do zrozumienia i wdrożenia w rzeczywistej aplikacji. Podobnie jak algorytm Prima, algorytm Kruskala jest również bardzo przydatny w rzeczywistych aplikacjach. Musimy więc zrozumieć ten algorytm.