Dokładniejsza analiza zmodyfikowanego algorytmu Borůvka

Algorytm Borůvki jest jednym ze standardowych algorytmów do obliczania minimalnego drzewa opinającego dla wykresu , z . $G = (V,E)$ $|V| = n, |E| = m$

Pseudo-kod to:

MST T = empty tree
Begin with each vertex as a component
While number of components > 1
    For each component c
       let e = minimum edge out of component c
       if e is not in T
           add e to T  //merging the two components connected by e

Każdą iterację pętli zewnętrznej nazywamy rundą. W każdej rundzie wewnętrzna pętla zmniejsza liczbę elementów o co najmniej połowę. Dlatego jest co najwyżej rund . W każdej rundzie wewnętrzna pętla patrzy na każdą krawędź maksymalnie dwa razy (raz z każdego elementu). Dlatego czas działania wynosi co najwyżej . $O(\log n)$ $O(m \log n)$

Załóżmy teraz, że po każdej rundzie usuwamy wszystkie krawędzie, które łączą tylko wierzchołki w tym samym komponencie, a także usuwamy zduplikowane krawędzie między komponentami, tak aby wewnętrzna pętla patrzyła tylko na pewną liczbę krawędzi m '<m, które są krawędziami o minimalnej masie, które połącz dwa wcześniej odłączone komponenty.

Jak ta optymalizacja wpływa na czas działania?

Gdybyśmy w jakiś sposób wiedzieli, że w każdej rundzie zmniejszyłoby liczbę krawędzi o połowę, wówczas czas pracy zostałby znacznie skrócony: . $T(m) = T(m /2) + O(m) = O(m)$

Jednak podczas gdy optymalizacja radykalnie zmniejszy liczbę badanych krawędzi (tylko 1 krawędź do ostatniej rundy i co najwyżej # komponentów wybiera 2 ogólnie), nie jest jasne, w jaki sposób / jeśli możemy wykorzystać ten fakt do zaostrzenia analizy czasu wykonywania.

algorithms algorithm-analysis spanning-trees

— Joe
źródło

W najgorszym przypadku (łańcuch) usunąłbyś dokładnie jedną krawędź na rundę, więc nie możesz użyć tego faktu do poprawy granic dla ogólnego wykresu. Można jednak rozważyć np. Tylko pełne wykresy.

— Xodarap,

@ Xodarap, jeśli jest prostą ścieżką (czy to rozumiesz przez łańcuch?), To w pierwszej rundzie wybierasz co najmniej połowę krawędzi. Krawędzie te są usuwane z kolejnych rund.

G

$G$

— Joe

Zauważ, że możesz użyć jednej z wysoce zoptymalizowanych struktur znajdowania związków, aby ulepszyć ten algorytm.

— Raphael

Możliwe jest tworzenie przypadków testowych dla ogólnych wykresów, w których krok twojego Borůvki nie zmniejszyłby o połowę liczby krawędzi na każdym kroku, nawet jeśli zmniejszyłby o połowę liczbę wierzchołków. Interesującą uwagą jest to, że sugerowana optymalizacja działa dla grafów płaskich. Jest tak, ponieważ w przypadku wykresów płaskich i, e . I generalnie prowadzi to do przyspieszenia klasy małych zamkniętych rodzin grafów. $|E| \leq 3*|V|-6$ $|E| = O(|V|)$

Odniesienie:

Praca magisterska, Claude Anderson (na stronie 100 opisano najgorszy przypadek wprowadzenia algorytmu Borůvki). [połączyć]
„Dwa liniowe algorytmy czasowe dla MST na mniejszych klasach zamkniętych grafów”. Archivum mathematicum 40 (3): 315–320, 2004. [link]

— rizwanhudda
źródło