W poprzednim wykładzie implementowaliśmy, że te połączenia wspominają o strukturze danych, aw
tym wykładzie zamierzamy zaimplementować algorytm międzyklasowy.
Więc mamy klasę algorytmu Kruskala, dobrze.
W konstruktorze lub bloku inicjalizacyjnym otrzymamy listę wierzchołków.
Więc Vertex wymienia i mamy Edgerly'ego.
Więc lista Ajaya jest tak zwinna.
I oczywiście tworzymy zmienną instancji odpowiednio.
Więc Vertex List jest listą wierzchołków.
Mamy listę jako listę krawędzi i oczywiście musimy znaleźć funkcję najkrótszej ścieżki.
A więc przede wszystkim, co musimy zrobić?
Oczywiście musimy stworzyć tę wspólną strukturę danych. Czy jest to nowy rozłączny zbiór, OK?
Oczywiście musimy zdefiniować ja, tę listę wierzchołków i co dalej?
Oczywiście musimy stworzyć minimalne drzewo wydatków.
Zamierzamy użyć struktury danych listowych w celu przechowywania wierzchołków i krawędzi w odniesieniu do
drzewa minimalnych wydatków.
Następnie musimy wykonać algorytm drzewa minimalnych wydatków.
Przede wszystkim musimy posortować krawędzie, aby posortować krawędzie na podstawie parametrów wagi.
Więc co musimy zrobić?
S, że faktycznie jest to ten rodzaj i ponieważ zdefiniowaliśmy tę funkcję lasdun dla danych krawędzi.
Więc to jest Python z funkcją Lasdun.
Wszyscy wiemy, OK, posortowane zamówienie zostanie skonstruowane na podstawie parametrów wagi.
Dlatego właśnie możemy wywołać funkcję miecza, a następnie musimy wziąć pod uwagę krawędzie.
Rozważ więc krawędzie w posortowanej kolejności.
Więc dla krawędzi w s ta lista krawędzi, którą mamy, jest blisko wierzchołka początku krawędzi.
Mamy V, które jest równe wierzchołkowi punktu docelowego na krawędzi.
Musimy sprawdzić, czy węzły skojarzone z tobą i wierzchołkami są w tych samych rozłącznych zbiorach, czy
nie.
Więc zasadniczo, jeśli mają ten sam węzeł główny lub reprezentanta.
Więc co musimy zrobić, jeśli D sac znajduje się dla ciebie, a reprezentant nie jest tym samym, co
zbiór rozłączny, jeśli chodzi o wierzchołek V, to znaczy, że możemy uwzględnić daną krawędź w
minimalnych wydatkach drzewo.
I oczywiście do tego musimy uzyskać węzeł.
Więc U będzie reprezentować wierzchołek na wykresie.
Ale my szukamy węzła.
Węzeł będzie reprezentował strukturę drzewa rozłącznego zbioru.
Dlatego właśnie musimy użyć węzła punktowego i węzła punktowego v, OK?
I oczywiście po tym musimy scalić te wspólne zestawy.
Dlatego właśnie mamy funkcję scalania z węzłem i węzłem v iw zasadzie chodzi o algorytm
międzyklasowy.
Dlatego jest absolutnie niezbędne, aby zaimplementować zestaw rozłączny, ponieważ jeśli mamy podstawę tych
połączonych struktur danych, to algorytm Kruskala jest taki łatwy.
Zasadniczo mówiliśmy o tym, że najpierw musimy posortować krawędzie, a
następnie rozważyć krawędzie w posortowanej kolejności.
I nawet podane wierzchołki skojarzone z daną krawędzią są obojętnymi zbiorami rozłącznymi, to daną
krawędź uwzględniamy w drzewie minimalnych wydatków i scalamy podane zbiory rozłączne.
Następnie musimy zrobić to samo dla następnej krawędzi w posortowanej kolejności i tak dalej.
I oczywiście nie możemy dojść do wniosku, że dwa węzły związane z wierzchołkami, jeśli chodzi o
dane krawędzie, należą do tego samego zbioru rozłącznego.
W tym przypadku możemy dojść do wniosku, że dana przewaga nie występuje w drzewku minimalnych wydatków.
Dlatego musimy wziąć pod uwagę wszystkie krawędzie i sprawdzić, czy dany zbiór rozłączny Cię znajdzie.
Ten węzeł nie jest tym samym, co węzeł strzałki.
Więc zasadniczo twój przedstawiciel nie jest tym samym, co przedstawiciel WI, co oznacza, że nie są
w tym samym rozłącznym zbiorze.
Wtedy możemy dojść do wniosku, że przewaga znajduje się w drzewku minimalnych wydatków.
I oczywiście musimy to połączyć, biorąc pod uwagę te wspólne zestawy.
I oczywiście, po rozważeniu wszystkich krawędzi, dlaczego musimy to robić, musimy iterować
przez krawędzie w drzewie minimalnych wydatków i wypisać nazwę początkowego wierzchołka, nazwę wierzchołka docelowego.
I na przykład użyjmy.
Uczą, więc mamy przewagę, która czeka, OK?
W następnym wykładzie sprawdzimy, czy algorytm działa dobrze, czy nie.
Dzięki za oglądanie.