Struktury danych dla rodzin zbiorow rozłącznych

Zadanie AL12.1 Wykorzystując reprezentację drzewiastą rodzin zbiorów rozłącznych (z łączeniem według rangi i kompresją ścieżek) naszkicuj, jak będzie wyglądać utworzona reprezentacja zbiorów po wykonaniu następujących operacji:

Z[0] = MakeSet(0);

Z[1] = MakeSet(1);

....

Z[9] = MakeSet(9);

Union(FindSet(Z[0]),FindSet(Z[1]))

Union(FindSet(Z[2]),FindSet(Z[3]))

Union(FindSet(Z[1]),FindSet(Z[2]))

Union(FindSet(Z[5]),FindSet(Z[6]))

Union(FindSet(Z[7]),FindSet(Z[8]))

Union(FindSet(Z[3]),FindSet(Z[5]))

Union(FindSet(Z[0]),FindSet(Z[7]))

Zadanie AL12.2 (3 pkt) Zaimplementuj reprezentację drzewiastą (z łączeniem wg rangi oraz kompresją ścieżki) zbiorów rozłącznych (operacje MakeSet, FindSet, Union). Przetestuj działanie tych funkcji wykonując np. ciąg operacji jak w zadaniu AL12.1 i następnie drukując dla każdego elementu Z[i] jego scieżkę do korzenia i analizując poprawność otrzymanego wyniku. Żeby sprawdzić poprawność wyniku, w czasie prezentacji rozwiązania należy przedstawić szkic końcowego drzewa (drzew) (na kartce lub innym nośniku informacji).

Zadanie AL12.3 (2 pkt). Wykorzystując zaimplementowane operacje na zbiorach rozłącznych, napisz program realizujący algorytm Kruskala znajdowania drzewa spinającego o minimalnym koszcie dla danego ważonego nieskierowanego grafu prostego G = (V, E, w). Zakładamy, że wejście stanowi ciąg krawędzi wraz z ich wagami. Jako wynik powinny być wypisane krawędzie drzewa spinającego o minimalnym koszcie wraz z ich wagami. W czasie prezentacji rozwiązania należy przedstawić rysunek grafu (na kartce lub innym nośniku informacji).