Dodaj nową krawędź do wykresu i znajdź nowe drzewo opinające w O (n)

Załóżmy, że podajemy minimalne drzewo T rozpinające dany wykres G (z n wierzchołkami i m krawędziami) i nową krawędzią e = (u, v) wagi w, którą dodamy do G. Podaj skuteczny algorytm, aby znaleźć minimalne drzewo opinające wykresu G + e. Twój algorytm powinien działać w O (n) czasie, aby otrzymać pełny kredyt.Dodaj nową krawędź do wykresu i znajdź nowe drzewo opinające w O (n)

start Prim lub Kruskala alg z U lub V aż docieramy fragment podane obejmującym drogi drzewa? Wygląda na to, że nowe drzewo opinające wiele się nie zmieni od jednej nowej krawędzi.

Źródło

2011-01-26 yetanothercoder

Ponieważ jest to problem pracy domowej, można wyjaśnić bardziej szczegółowo, co chcesz pomóc? To wielki problem, ale nie zamierzamy dać ci odpowiedzi. – templatetypedef

Określanie ścieżki między punktami końcowymi nowej krawędzi w G. Jeśli maksymalna długość krawędzi w tej ścieżce jest większa niż krawędzi nowej, zastąp ją nową krawędzią. To działa w czasie O (N).

Źródło: Trail Maintenance IOI 2003

Źródło

2011-01-26 20:22:48 marcog

Doskonała odpowiedź na pytanie inne niż domowe. Ale jest to zadanie domowe, więc -1. –

+16

@j_random_hacker - Niektórzy ludzie są ciekawi, dlaczego wzgardziłeś: zobacz [to pytanie na Meta] (http://meta.stackexchange.com/questions/76694). Co powinien powiedzieć marcog, aby uczynić to lepszym rozwiązaniem na pytanie o pracę domową? – ChrisW

Wow! Nie spodziewałem się wzbudzać tak wielu kontrowersji. Dzięki @ChrisW dla wskaźnika. Spróbuję wyjaśnić moje stanowisko w tym pytaniu o Metę (co moim zdaniem jest świetnym przykładem pytania o Metę, BTW). –

Dodaj nową krawędź do wykresu i znajdź nowe drzewo opinające w O (n)

Odpowiedz

Powiązane problemy