Nie chcę, aby znaleźć wszystkie minimalne drzewo rozpinające, ale chcę wiedzieć, ile ich tam jest, tutaj jest metoda Uważałem:Jak znaleźć całkowitą liczbę minimalnych drzew opinających na wykresie?
- Znajdź jeden minimalne drzewo rozpinające użyciu Prim lub Algorytm Kruskala i następnie odszukaj ciężary wszystkich drzew opinających i zwiększ licznik bieżący, gdy jest on równy ciężarowi minimalnego drzewa opinającego.
Nie mogłem znaleźć żadnej metody, aby znaleźć wagi wszystkich drzew opinających, a także liczba drzew opinających może być bardzo duża, więc ta metoda może nie być odpowiednia dla problemu. Ponieważ liczba minimalnych rozpinających się drzew jest wykładnicza, liczenie ich nie będzie dobrym pomysłem.
- Wszystkie wagi będą dodatnie.
- Możemy również założyć, że żadna waga nie pojawi się więcej niż trzy razy na wykresie.
- Liczba wierzchołków będzie mniejsza lub równa 40 000.
- Liczba krawędzi będzie mniejsza lub równa 100 000.
Na wykresie znajduje się tylko jedno minimalne drzewo opinające, w którym waga wierzchołków jest różna. Myślę, że najlepszym sposobem znalezienia liczby minimalnego drzewa opinającego musi być coś korzystającego z tej właściwości.
EDIT:
Znalazłem rozwiązanie tego problemu, ale nie jestem pewien, dlaczego to działa. Czy ktoś może to wyjaśnić.
Rozwiązanie: Problem znalezienia długości minimalnego drzewa opinającego jest dość dobrze znany; dwa najprostsze algorytmy do znalezienia minimalnego drzewa opinającego to algorytm Prima i algorytm Kruskala. Z tych dwóch algorytm Kruskala przetwarza krawędzie w rosnącej kolejności ich ciężarów. Jest ważny klucz do rozważenia algorytmu Kruskala, jednak: gdy rozważa się listę krawędzi posortowanych według wagi, krawędzie mogą być chciwie dodane do drzewa opinającego (o ile nie łączą one dwóch wierzchołków, które są już w jakiś sposób połączone).
Rozważ teraz częściowo uformowane drzewo opinające za pomocą algorytmu Kruskala. Wstawiliśmy pewną liczbę krawędzi o długości mniejszej niż N, a teraz musimy wybrać kilka krawędzi o długości N. Algorytm stwierdza, że musimy wstawić te krawędzie, jeśli to możliwe, przed dowolnymi krawędziami o długości większej niż N. Jednakże możemy wstaw te krawędzie w dowolnej kolejności. Zauważ również, że bez względu na to, które wstawimy, w ogóle nie zmienia to połączenia grafu. (Rozważmy dwa możliwe wykresy, jeden z krawędzią od wierzchołka A do wierzchołka B i drugi bez. Drugi wykres musi mieć A i B jako część tego samego połączonego komponentu, w przeciwnym razie krawędź od A do B byłaby wstawiona o jeden punkt.)
Te dwa fakty razem implikują, że nasza odpowiedź będzie iloczynem sposobów, za pomocą algorytmu Kruskala, wstawienia krawędzi o długości K (dla każdej możliwej wartości K). Ponieważ istnieją co najwyżej trzy krawędzie o dowolnej długości, różne przypadki mogą być wymuszone przez wymuszenie, a połączone komponenty mogą zostać określone po każdym kroku, tak jak normalnie.
Problem, który próbuję rozwiązać, ma krawędzie do 100 000. Tak więc algorytm prim z każdego brzegu zajmie dużo czasu. – 2147483647
Można go przyspieszyć, sprawdzając, czy wykres pośredni jest wykresem, który już napotkano jako wykres pośredni. Każdy taki wykres z pewnością zapewni minimum drzew, które już mamy. Chociaż będzie cię to kosztować w pamięci. W każdym razie pozostanie wolne. – bowmore
Możesz uruchomić algorytm dla każdej krawędzi początkowej jednocześnie: zacznij od utworzenia lasu wszystkich drzew, które są wynikiem pierwszego kroku algorytmu Prim. (z 40k wierzchołków daje to około 20 tys. drzew) Następnie wykonaj kolejny krok algorytmu na każdym z drzew w tym lesie i utwórz nowy las zawierający drzewa o dwóch krawędziach (prawdopodobnie usuwając nawet więcej duplikatów). Każdy krok będzie nadal eliminował duplikaty, a ta struktura pozwala również w łatwy sposób obsługiwać wiele możliwości jako kolejny krok, dodając wszystkie możliwości do lasu następnej generacji. – bowmore