Siemano! Moim zadaniem na tę noc jest implementacja MST za pomocą Kruskala. Jest wszystko ok, lista krawędzi elegancko posortowana jednak problem zaczyna się przy tworzeniu tych zbiorów rozłącznych. Nie wiem dokładnie jak sprawdzać czy dodanie krawędzi, a dokładnie jej wierzchołków nie spowoduje cyklu. Znalazłem jakieś gotowe implementacje, które pomogłoby mi (tak przynajmniej myślałem :x) z własną jednak są tam funkcje typu FindSet czy MakeSet czego wolałbym uniknąć i napisać, że tak powiem "na czysto". Na co powinienem zwrócić uwagę przy tworzeniu MST i dodawaniu krawędzi tak by uniknąć stworzenia cyklu...
0
0
Nie rozumiem pytania. Przecież zbiory rozłączne są dość jasną konstrukcją.
Dla każdego wierzchołka przechowujesz informację o "głowie" zbioru w którym sie znajduje. Pojedynczy wierzchołek jest sam dla siebie głową. Dołączenie krawędzi oznacza połączenie zbiorów w których znajdują się wierzchołki na końcach tej krawędzi. Połączenie zbiorów polega na ustawieniu głowie jednego ze zbiorów głowy na głowę tego drugiego zbioru. W efekcie oczywiście dla niektórych wierzchołków szukanie głowy będzie wymagało pętli bo będą wierzchołki które myślą że głową jest X, a X myśli że Y a Y myśli że Z więc musimy sobie przeskakiwać aż do Z. Można zrobić tzw. kompresje ścieżki co jakiś czas, czyli dla danego zbioru policzyć kto jest glową (czyli dojść sobie do Z) a potem ustawić ten wierzchołek jako głowę każdemu w zbiorze.
Oczywiście od razu widać czy dana krawędź utworzy cykl - jeśli oba wierzchołki są w tym samym zbiorze (mają taką samą "głowę").
0
ok dzięki za odpowiedź :)