95925

Połączone listy sąsiadów 0(n+m)

struktura składająca się z tablicy n list, gdzie lista dowiązana do komórki i-tej zawiera wszystkie krawędzie incydentne z wierzchołkiem i-tym (waga krawędzi i oznaczenie wierzchołka).

Zauważmy, że w przypadku grafu nieskierowanego każda krawędź (i; j) wyst ępuje w tej strukturze 2 razy _ w liście i-tej oraz j-tej.

Zaletą struktury jest to, że wszystkie krawędzie (luki) z danego wierzchołka mamy zgrupowane w jednym miejscu (są dostępne bez konieczności przeszukiwania całego grafu).

Pęk wyjściowy 0(n + m)

odmiana poprzedniej struktury dla sytuacji, gdy nie wykonujemy na grafie operacji dodawania / usuwania krawędzi. Składa się z 3 tablic _ pierwszej o długości n oraz dwóch o długości m. Dwie ostatnie tablice zawierają odpowiednio etykiety wierzchołków końcowych i wagi wszystkich krawędzi, pogrupowane w zbiory ze sobą incydentne, a pierwsza tablica (odpowiadająca wierzchołkom początkowym) zawiera wskaźniki rozdzielające poszczególne grupy (np. jeśli wierzchołek 1 ma 5 krawędzi incydentnych, to komórki [1] i [2] pierwszej tablicy zawierają odpowiednio wskaźniki na komórki [1] i [6] tablicy drugiej). Struktura posiada zaletę struktury wcześniejszej _ zgrupowanie krawędzi incydentnych poszczególnych wierzchołków, przy braku typów wskaźnikowych.

3. Algorytmy wyznaczania MST Kruskal

polega na dołączaniu kolejno krawędzi w porządku ich niemalejących wag , o ile dołączana krawędź nie utworzy cyklu z już wybranymi krawędziami. Ważna jest efektywna metoda na sprawdzanie cykli - np. tablica o dł n do malowania wierzchołków, tablica do przechowywania ilości elementów poddrzew

Złożoność obliczeniowa:

•    Kolorowanie wierzchołków - O(n)

•    Posortowanie struktury - 0(m logm)

•    Sprawdzanie kolejno krawędzi - p pętli (n-1 - m) , za każdym razem czy jest cykl - O(pm)

0(mlogm + pm)

•    Lepiej wtedy umieścić krawędzie w kopcu i pobierać za każdym razem najkrótszą z jeszcze niedołączonych z korzenia. Wtedy takie pobranie będzie zajmować O(logm), a takich pobrań będzie p, zatem złożoność całego algorytmu wyniesie

•    O(p(logm+m)) = O(pm)

•    Możliwe jest też takie zaimplementowanie algorytmu Kruskala, że jego złożoność wyniesie 0(m logm) - kopiec Fibonacciego.

Prime

rozpoczyna się od wybrania dowolnego wierzchołka i sukcesywnym dołączkaniu najbliższego sąsiada (tj. wierzchołka, który jest połączony z którymś zjuż dołączonych krawędzią o najmniejszej wadze). Dzięki temu, że w każdym kroku algorytmu dołączamy nowy wierzchołek do istniejącego poddrzewa, nigdy nie spowoduje to powstania cyklu, a wszystkich iteracji będzie n-1.