Potrzebuję pomocy ze zrozumieniem i podpowiedzi w jaki sposób można nałożyć warunek wyboru ścieżki tak, aby nie zapętlić drzewa (tj. przy wyborze krawędzi o minimalnej wartości nie dopuścić do sytuacji 1-2 2-3 1-3). Mam klasę Wierzchołek, w której mam hashmapę z wierzchołek/krawędź przechowującą wierzchołki i krawędzie z nimi połączone. Ciężko mi idą algorytmy, w których trzeba coś optymalizować, zamiast wybrać po prostu najmniejsze - wybierz najmniejsze, które spełnia warunek opisany powyżej. Prosiłbym o pomoc, jeśli coś źle napisałem proszę zadać pytania i zwrócić mi uwagę, dziękuję.
0
1
"trzeba coś optymalizować, zamiast wybrać po prostu najmniejsze" - w algorytmie minimalnego drzewa rozpinającego wynikiem ma być minimalne drzewo rozpinające, które zawsze będzie istniało przy spełnieniu założenia spójności dla grafu nieskierowanego, więc celem nie jest optymalizacja, tylko "wybierz najmniejsze" jak wspomniałeś. Sama specyfika wynika z tego, że algorytm jest zachłanny (z tego co kojarzę, inne warianty znalezienia MST też są zachłanne).
Postępując zgodnie z algorytmem, nie jesteś w stanie stworzyć cyklu - zawsze przetwarzasz wierzchołek, który nie znajduje się w obecnym MST i dodajesz krawędź.
Aby powstał cykl musiałbyś przetworzyć więcej niż raz ten sam wierzchołek.
1
Dodawaj odwiedzone wierzcholki do seta (albo zrob tablice booleanow) i pomijaj je przy kolejnych operacjach.
0
W takim razie nie zrozumiałem, w algorytmie prima idziemy wierzchołek 1 (3 krawędzie wybieramy najlżejszą), wierzchołek 2 (2 krawędzie cięższe od 2 pozostałych wierzchołka 1, więc wybieramy znowu krawędź z pierwszego) wierzchołek 4 itd. Czy w ten sposób nie jesteśmy przypadkiem w stanie stworzyć połączenia np 1-2 2-3 1-3? Skoro rozpatrujemy wszystkie krawędzie z odwiedzonych już wierzchołków i wybieramy najmniejsze?
1
Nie jesteśmy w stanie stworzyć, spójrz:
Mamy pierwszy arbitralnie wybrany wierzchołek 1. Dodajemy do kolejki priorytetowej wszystkich jego sąsiadów, w kolejce priorytetowej priorytetem są wagi krawędzi, a jego samego do naszego MST (obecnie składa się z 1 wierzchołka) - przetwarzamy. Skoro stworzyliśmy krawędź 1-2 jako pierwszą to oznacza że miała ona najmniejszą wagę spośród wszystkich sąsiadów wierzchołka 1 oraz po tej operacji uznajemy wierzchołek 2 jako przetworzony. Zajmujemy się wierzchołkiem 2, dodajemy do kolejki jego sąsiadów. Po tym zabiegu mamy w kolejce priorytetowej wszystkich sąsiadów wierzchołków 1 oraz 2, wierzchołki 1 i 2 oznaczone jako przetworzone. Jako, że dodana została krawędź 2-3 to oznacza, że wierzchołek 3 jest sąsiadem wierzchołka 2 oraz krawędź między nimi ma najmniejszą wagę (jest na początku kolejki). Dodajemy sąsiadów wierzchołka 3 do kolejki. W kolejce mamy wszystkich sąsiadów 1, 2 oraz 3. Jeśli najlepszą krawędzią jest 3-1, to nie możemy jej wybrać bo wierzchołek 1 został przetworzony na samym początku, więc cykl nie powstanie.
0
O faktycznie, takiej odpowiedzi poszukiwałem, dziękuję bardzo! Czyli najlepiej będzie hashmapę zamienić na pq i w metodzie juz przerzucać z tych wierzchołków ich kolejki priorytetowe do głównej. Dzieki!