minimum spanning tree tutorial
Ten samouczek języka C ++ wyjaśnia, czym jest minimalne drzewo rozpinające (MST) wraz z algorytmami Prim i Kruskala do znajdowania MST na wykresie i jego aplikacjach:
Drzewo opinające można zdefiniować jako podzbiór wykresu, który składa się ze wszystkich wierzchołków obejmujących minimum możliwych krawędzi i nie ma cyklu. Nie można odłączyć drzewa opinającego.
Każdy połączony i nieukierunkowany wykres ma co najmniej jedno drzewo opinające. Odłączony graf nie ma drzewa opinającego, ponieważ nie jest możliwe uwzględnienie wszystkich wierzchołków.
=> Zobacz tutaj, aby poznać pełną listę samouczków języka C ++.
Czego się nauczysz:
Drzewo opinające w C ++
Rozważ następujący połączony wykres.
Jak pokazano powyżej, dla danego połączonego Grafu zawierającego 3 wierzchołki mamy trzy drzewa rozpinające. Ogólnie rzecz biorąc, jeśli N jest liczbą węzłów na grafie, to cały połączony graf ma maksimum NN-2liczba drzew rozpinających. Zatem na powyższym wykresie N = 3, więc ma 3(3-2)= 3 rozpinane drzewa.
Poniżej wymieniono niektóre właściwości drzewa opinającego:
- Połączony wykres może mieć więcej niż jedno drzewo opinające.
- Wszystkie drzewa opinające na wykresie mają taką samą liczbę węzłów i krawędzi.
- Jeśli usuniemy jedną krawędź z drzewa opinającego, stanie się minimalnie połączony i spowoduje odłączenie wykresu.
- Z drugiej strony, dodanie jednej krawędzi do drzewa opinającego sprawi, że to zrobi maksymalnie acykliczny tworząc w ten sposób pętlę.
- Drzewo opinające nie ma pętli ani cyklu.
Co to jest minimalne drzewo rozpinające (MST)
Minimalne drzewo opinające to takie, które zawiera najmniejszą wagę spośród wszystkich innych drzew rozpinających połączonego wykresu ważonego. Dla wykresu może istnieć więcej niż jedno minimalne drzewo opinające.
Istnieją dwa najpopularniejsze algorytmy używane do znajdowania minimalnego drzewa opinającego na wykresie.
Zawierają:
- Algorytm Kruskala
- Algorytm Prima
Omówmy oba te algorytmy!
Algorytm Kruskala
Algorytm Kruskala to algorytm znajdowania MST na połączonym grafie.
Algorytm Kruskala znajduje taki podzbiór grafu G, że:
- Tworzy drzewo z każdym wierzchołkiem.
- Suma wag jest minimum spośród wszystkich drzew rozpinających, które można utworzyć z tego wykresu.
Sekwencja kroków algorytmu Kruskala jest następująca:
- Najpierw posortuj wszystkie krawędzie od najniższej do najwyższej wagi.
- Weź przewagę o najmniejszej wadze i dodaj ją do drzewa opinającego. Jeśli cykl zostanie utworzony, odrzuć krawędź.
- Dodawaj krawędzie jak w kroku 1, aż wszystkie wierzchołki zostaną uwzględnione.
Pseudokod algorytmu Kruskala
Poniżej podano pseudokod algorytmu Kruskala
Zobaczmy teraz ilustrację algorytmu Kruskala.
Teraz wybieramy krawędź o najmniejszej wadze 2-4.
Następnie wybierz następną najkrótszą krawędź 2-3.
Następnie wybieramy kolejną krawędź z najkrótszą krawędzią, która nie tworzy cyklu czyli 0-3
darmowe oprogramowanie do wirtualizacji dla systemu Windows 10
Następnym krokiem jest wybranie najkrótszej krawędzi, tak aby nie tworzyła cyklu. To jest 0-1.
Jak widać, omówiliśmy wszystkie wierzchołki i mamy tutaj drzewo opinające z minimalnym kosztem.
Następnie zaimplementujemy algorytm Kruskala w C ++.
#include #include #include using namespace std; #define graph_edge pair class Graph { private: int V; // number of nodes in graph vector> G; // vector for graph vector> T; // vector for mst int *parent; public: Graph(int V); void AddEdge(int u, int v, int wt); int find_set(int i); void union_set(int u, int v); void kruskal_algorithm(); void display_mst(); }; Graph::Graph(int V) { parent = new int[V]; for (int i = 0; i Wynik:
Minimalne drzewo rozpinające (MST) według algorytmu Kruskala:
Krawędź: waga
2 - 4: 1
2 - 3: 2
0 - 1: 3
0 - 3: 3
Zauważ, że użyliśmy tego samego przykładowego wykresu w programie, którego użyliśmy na ilustracji algorytmu Kruskala powyżej. W tej implementacji używamy dwóch wektorów; jeden do przechowywania wykresu, a drugi do przechowywania minimalnego drzewa rozpinającego. Rekurencyjnie znajdujemy krawędzie o najmniejszej wadze i dodajemy je do wektora MST, aż wszystkie wierzchołki zostaną pokryte.
Algorytm Prima
Algorytm Prima to kolejny algorytm do znalezienia minimum obejmującego drzewo wykresu. W przeciwieństwie do algorytmu Kruskala, który zaczyna się od krawędzi grafu, algorytm Prim zaczyna się od wierzchołka. Zaczynamy od jednego wierzchołka i dodajemy krawędzie o najmniejszej wadze, aż wszystkie wierzchołki zostaną pokryte.
Sekwencja kroków algorytmu Prim jest następująca:
- Wybierz losowy wierzchołek jako wierzchołek początkowy i zainicjuj minimalne drzewo rozpinające.
- Znajdź krawędzie, które łączą się z innymi wierzchołkami. Znajdź krawędź o minimalnej wadze i dodaj ją do drzewa opinającego.
- Powtarzaj krok 2, aż do uzyskania drzewa opinającego.
Pseudokod dla algorytmu Prim
Zobaczmy teraz ilustrację algorytmu Prim.
W tym celu używamy tego samego przykładowego wykresu, którego używaliśmy w algorytmie Illustration of Kruskal.
Wybierzmy węzeł 2 jako losowy wierzchołek.
Następnie wybieramy krawędź o najmniejszej wadze z 2. Wybieramy krawędź 2-4.
Następnie wybieramy inny wierzchołek, którego jeszcze nie ma w drzewie opinającym. Wybieramy krawędź 2-3.
Teraz wybierzmy krawędź o najmniejszej wadze z powyższych wierzchołków. Mamy przewagę 3-0, która ma najmniejszą wagę.
Następnie wybieramy krawędź o najmniejszej wadze z wierzchołka 0. To jest krawędź 0-1.
Z powyższego rysunku widzimy, że pokryliśmy teraz wszystkie wierzchołki wykresu i otrzymaliśmy pełne drzewo rozpinające przy minimalnym koszcie.
Teraz zaimplementujmy algorytm Prim w C ++.
Zauważ, że również w tym programie użyliśmy powyższego przykładowego wykresu jako danych wejściowych, abyśmy mogli porównać dane wyjściowe podane przez program z ilustracją.
Program jest podany poniżej:
#include #include using namespace std; #define INF 9999 // graph contains 5 vertices #define V 5 // an array G that stores adjacency matrix for input graph int G[V][V] = { {0, 3, 0, 3, 0}, {3, 0, 0, 0, 4}, {0, 0, 0, 2, 1}, {3, 3, 2, 0, 0}, {0, 4, 1, 0, 0}}; int main () { int num_edge; // number of edge // mst_vertex - array to track vertices selected for spanning tree int mst_vertex[V]; // set selected false initially memset (mst_vertex, false, sizeof (mst_vertex)); // set number of edge to 0 num_edge = 0; //let 0th vertex be the first to be selected mst_vertex[0] = true; int x; // row int y; // col // print details of MST cout<<'The Minimum Spanning Tree as per Prim's Algorithm:'< G[i][j]) { min = G[i][j]; x = i; y = j; } } } } } cout << x << ' - ' << y << ' : ' << G[x][y]; cout << endl; mst_vertex[y] = true; num_edge++; } return 0; }
Wynik:
Minimalne drzewo rozpinające zgodnie z algorytmem Prim:
Krawędź: waga
0 - 1: 3
0 - 3: 3
3 - 2: 2
2 - 4: 1
Zastosowania Spanning Tree
Oto niektóre z zastosowań drzew rozpinających:
# 1) Konfiguracja sieci komunikacyjnej: Kiedy chcemy skonfigurować sieć komunikacyjną za pomocą łączy komunikacyjnych, wówczas koszt zestawienia łączy komunikacyjnych między dwoma punktami najlepiej określić za pomocą MST.
# 2) Analiza klastrów: Można go użyć do rozwiązania problemu klastrowania K poprzez znalezienie minimalnego drzewa rozpinającego i usunięcie najdroższych krawędzi k-1.
# 3) Planowanie sieci drogowych / kolejowych: Kiedy układamy różne sieci drogowe lub kolejowe pomiędzy miastami lub w ich obrębie, koszt projektu jest bardzo ważnym czynnikiem. Możemy znaleźć najlepszą ścieżkę przy minimalnych kosztach przy użyciu minimalnej liczby drzew rozpinających.
# 4) Planowanie udogodnień mieszkaniowych: Usługi, takie jak elektryczność, woda, ścieki itp., Które mają być dostarczane do wielu domów, również wymagają optymalnej ceny i odbywa się to za pomocą MST.
# 5) Rozwiązywanie problemu komiwojażera: Możemy użyć MST, aby rozwiązać problem komiwojażera, który wymaga odwiedzenia każdego punktu przynajmniej raz.
Wniosek
Minimalne drzewo rozpinające jest podzbiorem grafu g, a ten podzbiór zawiera wszystkie wierzchołki grafu, a całkowity koszt krawędzi łączących wierzchołki jest minimalny.
Omówiliśmy dwa algorytmy, tj. Kruskala i Prim, w celu znalezienia minimalnego drzewa rozpinającego na wykresie. Zastosowania drzewa opinającego zostały również wyjaśnione w tym samouczku.
=> Sprawdź najlepsze samouczki szkoleniowe C ++ tutaj.
rekomendowane lektury
- Samouczek dotyczący refleksji w języku Java z przykładami
- Struktura danych B Tree i B + Tree w C ++
- Python DateTime Tutorial z przykładami
- Samouczek Bugzilli: Praktyczny samouczek dotyczący narzędzia do zarządzania defektami
- Struktura danych drzewa binarnego w C ++
- Ponad 20 samouczków MongoDB dla początkujących: bezpłatny kurs MongoDB
- Samouczek dotyczący fragmentacji bazy danych MongoDB z przykładem
- Samouczek dotyczący tworzenia bazy danych MongoDB