Co to jest Spanning Tree?

Biorąc pod uwagę nieukierunkowany i połączony wykres, drzewo rozpiętościowe wykresu może być drzewem rozpiętościowym (tzn. zawiera każdy wierzchołek ) i może być podgrafem (każdy wierzchołek w górę drzewa należy do ).

Co to jest drzewo o minimalnej rozpiętości?

Koszt drzewa rozpiętościowego to suma mas wszystkich boków drzewa. Często istnieje wiele drzew przęsłowych. Drzewo przęsłowe o minimalnej rozpiętości to drzewo przęsłowe, którego wartość jest minimalna wśród wszystkich drzew przęsłowych. Może istnieć również wiele minimalnych drzew rozpiętościowych.

Drzewo rozpiętości minimalnej ma bezpośrednie zastosowanie w projektowaniu sieci. Jest ono wykorzystywane w algorytmach przybliżających problem wędrownego handlowca, wielostanowiskowym minimalnym problemie cięcia i minimalnym koszcie ważonym perfekcyjnym dopasowaniem. Inne praktyczne zastosowania to:

Analiza klastrowa

Rozpoznawanie pisma odręcznego

Segmentacja obrazu

Istnieją dwa słynne algorytmy lokalizacji drzewa o minimalnym rozpiętości przęseł:

Algorytm Kruskala

Algorytm Kruskala buduje drzewo przęseł, dodając krawędzie jeden po drugim do rosnącego drzewa przęseł. Algorytm Kruskala stosuje chciwe podejście, ponieważ w każdej iteracji znajduje przedsionek, który ma najmniejszą wagę i dodaje go do rosnącego drzewa przęseł.

Algorytm Kroki:

Sortuj krawędzie wykresu w odniesieniu do ich wagi.

Zacznij dodawać krawędzie do MST od ukłucia o najmniejszej wadze do ukłucia o wadze najważniejszej.

Dodawaj tylko krawędzie, które nie tworzą cyklu, krawędzie, które łączą tylko odłączone komponenty.

Więc teraz pytanie to jest sposób na sprawdzenie czy wierzchołki są połączone czy nie ?

Można to zrobić za pomocą DFS, który zaczyna się od głównego wierzchołka, a następnie sprawdzić, czy drugi wierzchołek jest odwiedzony, czy nie. Ale DFS sprawi, że złożoność czasowa będzie duża, ponieważ ma kolejność, gdzie jest ta liczba wierzchołków, to jest ta liczba krawędzi. dlatego najlepszym rozwiązaniem jest “Disjoint Sets”:

Zestawy łączników to zestawy, których przecięciem jest to, że pusty zestaw oznacza, że nie mają one żadnego elementu wspólnego.

W algorytmie Kruskala, przy każdej iteracji wybieramy żądło z ciężarkiem dna skały. Zaczynamy więc najpierw od krawędzi obciążonej dnem skały, czyli od boków o wadze 1. Następnie wybieramy drugą najniższą krawędź obciążoną, czyli krawędź o wadze 2. Zauważ, że te dwie krawędzie są całkowicie rozłożone. Teraz kolejna krawędź będzie trzecią najniższą krawędzią ważoną, czyli krawędź z wagą 3, która łączy te dwa elementy wykresu. Teraz nie możemy wybrać żądełka z obciążnikiem 4, które będą tworzyć cykl i nie możemy mieć żadnych cykli. Tak więc wybierzemy piąty najniżej położony kant, czyli kant z wagą 5. Teraz dwa przeciwległe brzegi stworzą cykle, więc je zignorujemy. na końcu znajdziemy się z minimalnym drzewem rozpiętości o łącznym koszcie 11 ( = 1 + 2 + 3 + 5).W Algorytmie Prim zaczniemy od dowolnego węzła (nie ma znaczenia, który) i zaznaczymy go. W każdej iteracji zaznaczymy wierzchołek zastępczy, który przylega do tego, który już zaznaczyliśmy. Jako chciwy algorytm, algorytm Prim wybierze najbardziej efektywny kosztowo krawędź i zaznaczy ten punkt. Tak więc po prostu wybierzemy żądło o wadze 1. W następnej iteracji mamy trzy opcje, krawędzie o wadze 2, 3 i 4. Tak więc wybierzemy żądło z wagą 2 i zaznaczymy wierzchołek. Teraz ponownie mamy trzy opcje, brzegi o wadze 3, 4 i 5. Ale nie możemy wybrać krawędzi z wagą 3, ponieważ tworzy ona cykl. Wybieramy więc żądło z wagą 4 i znajdujemy się na drzewie o minimalnej rozpiętości 7 ( = 1 + 2 + 4).

#wliczając <iostream>

#zawierając <wektor>

#zawierając <utility>

#zawierając <algorytm>

używając przestrzeni nazw std;

const int MAX = 1e4 + 5;

int id[MAX], węzły, krawędzie;

para <długa długa, para<int, int> > p[MAX];

pusta inicjalizacja()

{

dla(int i = 0;i < MAX;++i)

id[i] = i;

}

int root(int x)

{

while(id[x] != x)

{

id[x] = id[id[x]];

x = id[x]; x = id[x];

}

wrócić x;

}

nieważny związek1(int x, int y)

{

int p = korzeń(x);

int q = korzeń(y); int q = korzeń(y);

id[p] = id[q];

}

long long kruskal(para<long long, para<int, int> > p[])

{

Int x, y;

długi koszt, minimumCost = 0;

dla(int i = 0;i < krawędzie;++i)

{

// Wybieranie krawędzi jeden po drugim w rosnącej kolejności od początku

x = p[i].second.first;

y = p[i].second.second. = p[i].second.second;

koszt = p[i].first;

// Sprawdź, czy wybrane zbocze tworzy cykl czy nie

if(root(x) != korzeń(y))

{

minimumCost += koszt;

związek1(x, y);

}

}

wrócić minimumCost;

}

intymny()

{

Int x, y;

długa waga, koszt, minimumCost;

inicjalizować();

cin >> węzły >> krawędzie;

dla(int i = 0;i < krawędzie;++i)

{

cin >> x >> y >> waga;

p[i] = make_pair(waga, make_pair(x, y)));

}

// Sortuj krawędzie w kolejności rosnącej

sort(p, p + krawędzie);

minimumCost = kruskal(p);

cout << minimumCost << endl;

powrót 0;

}

Złożoność czasowa:

W algorytmie Kruskala najbardziej czasochłonną operacją jest sortowanie, ponieważ cała złożoność operacji Disjoint-Set będzie, czyli ogólna złożoność czasowa algorytmu.

Algorytm Prim’a

Algorytm Prim’a używa również chciwego podejścia do poszukiwania drzewa o minimalnej rozpiętości. W Algorytmie Prim’a rozwijamy drzewo rozpiętości z pozycji wyjściowej. W przeciwieństwie do podpórki w Kruskal’s, dodajemy wierzchołek do drzewa rozpiętości w Prim’s. W Algorytmie Prim’s dodajemy wierzchołek do drzewa rozpiętości.

Kroki Algorytmu:

Utrzymujemy dwa zestawy wierzchołków. Jeden zawiera wierzchołki, które znajdują się w rosnącym drzewie przęseł, a drugi nie znajduje się w rosnącym drzewie przęseł.

Wybierz najbardziej ekonomiczny wierzchołek, który jest połączony z rosnącym drzewem przęseł, a nie znajduje się w rosnącym drzewie przęseł i dodaj go do rosnącego drzewa przęseł. zostanie to zrobione przy użyciu Kolejek Priorytetów. Wstaw punkty, które są podłączone do drzewa rozpiętości rosnących, do kolejki priorytetowej.

Zaznacz cykle. aby spróbować to zrobić, zaznacz węzły, które są już zaznaczone i wstaw tylko te węzły w kolejce priorytetowej, które nie są zaznaczone.

Weź pod uwagę poniższą instancję:

W Algorytmie Prim, zaczniemy od dowolnego węzła (nie ma znaczenia który z nich) i zaznaczymy go. W każdej iteracji zaznaczamy wierzchołek zastępczy, który przylega do tego, który już zaznaczyliśmy. Jako chciwy algorytm, algorytm Prim wybierze najbardziej efektywny kosztowo krawędź i zaznaczy ten punkt. Tak więc po prostu wybierzemy żądło o wadze 1. W następnej iteracji mamy trzy opcje, krawędzie o wadze 2, 3 i 4. Tak więc wybierzemy żądło z wagą 2 i zaznaczymy wierzchołek. Teraz ponownie mamy trzy opcje, brzegi o wadze 3, 4 i 5. Ale nie możemy wybrać krawędzi z wagą 3, ponieważ tworzy ona cykl. Wybieramy więc żądło z wagą 4 i znajdujemy się na drzewie o minimalnej rozpiętości 7 ( = 1 + 2 + 4).

Realizacja:

#zawierając <iostream>

#zawierając <wektor>

#include <queue>

#zawierając <funkcjonalne>

#zawierając <utility>

używając przestrzeni nazw std;

const int MAX = 1e4 + 5;

typeedef pair<long long, int> PII;

bool oznaczony[MAX];

wektor <PII> adj[MAX]; wektor <PII> adj[MAX];

długa długa prim(int x)

{

priority_queue<PII, wektor<PII>, większy<PII> > Q;

w y;

long long minimumCost = 0;

PII p;

Q.push(make_pair(0, x)));

while(!Q.empty())

{

// Wybierz krawędź z minimalną wagą

p = Q.top();

Q.pop();

x = p.second;

// Sprawdzanie cyklu

if(marked[x] == true)

Kontynuować;

minimumCost += p.pierwsze;

oznaczone[x] = prawda;

for(int i = 0;i < adj[x].size();++i)

{

y = adj[x][i].second;

if(marked[y] == false)

Q.push(adj[x][i]);

}

}

wrócić minimumCost;

}

intymny()

{

w węzłach, krawędziach, x, y;

długi długi ciężar, minimumCost;

cin >> węzły >> krawędzie;

dla(int i = 0;i < krawędzie;++i)

{

cin >> x >> y >> waga;

adj[x].push_back(make_pair(weight, y)));

adj[y].push_back(make_pair(weight, x)));

}

// Wybranie 1 jako węzła startowego

minimumCost = prim(1);

cout << minimumCost << endl;

powrót 0;

}