Zbiory rozłączne – implementacja za pomocą drzew


Tematy pokrewne   Podrozdziały
Drzewa
Podstawowe pojęcia dotyczące drzew
Przechodzenie drzew binarnych – DFS: pre-order, in-order, post-order
Przechodzenie drzew binarnych – BFS
Badanie drzewa binarnego
Prezentacja drzew binarnych
Kopiec
Drzewa wyrażeń
Drzewa poszukiwań binarnych – BST
Tworzenie drzewa BST
Równoważenie drzewa BST – algorytm DSW
Proste zastosowania drzew BST
Drzewa AVL
Drzewa Splay
Drzewa Czerwono-Czarne
Kompresja Huffmana
Zbiory rozłączne – implementacja za pomocą drzew

Zbiory rozłączne – implementacja w tablicy
Zbiory rozłączne – implementacja listowa

  Rozwiązanie nr 1
Rozwiązanie nr 2

Problem

Zaprojektować efektywną strukturę danych dla zbiorów rozłącznych.


Struktura zbiorów rozłącznych (ang. disjoint sets structure) umożliwia przechowywanie informacji o przynależności elementów do różnych zbiorów, które są rozłączne (tzn. nie posiadają wspólnych elementów). Dotychczas zaprezentowaliśmy dwa rozwiązania tej struktury: w tablicy oraz za pomocą list. Istnieje trzeci sposób oparty na drzewach.

 

Rozwiązanie nr 1

Zbiory rozłączne odwzorowujemy za pomocą lasu (ang. forest) prostych drzew. Reprezentantem zbioru jest korzeń drzewa (ang. root node). Każdy węzeł zawiera pole up wskazujące rodzica (w wielu implementacjach pole to nosi nazwę parent, czyli rodzic; my zachowujemy zgodność z podanymi wcześniej informacjami). Korzeń drzewa wskazuje na siebie samego.

Uwaga: korzeń oraz pozostałe węzły mogą posiadać dowolną liczbę potomków, to nie są drzewa binarne!

 

      

 

Zdefiniujmy trzy podstawowe operacje w tej strukturze danych:

 

MakeSet(x)

Tworzy jednowęzłowe drzewo. Węzeł staje się reprezentantem zbioru. Pole up zostaje ustawione na ten sam węzeł.

 

FindSet(x)

Przebiega przez kolejne węzły drzewa z węzłem x aż do korzenia i zwraca jego wskazanie.

 

UnionSets(x,y)

Czyni korzeń drzewa z węzłem y dzieckiem korzenia drzewa z węzłem x.

 

Algorytmy dla struktury zbiorów rozłącznych zrealizowanej za pomocą drzew – wersja 1

MakeSet(x)

Wejście
x   wskazanie węzła drzewa
Wyjście:

Utworzenie drzewa z jednym węzłem x.

Lista kroków:
K01: (xup) ← x ;rodzicem korzenia jest korzeń
K02: Zakończ  

 

FindSet(x)

Wejście
x   wskazanie węzła drzewa
Wyjście:

Wskazanie korzenia drzewa zawierającego węzeł x.

Elementy pomocnicze:
p    wskaźnik węzłów drzewa
Lista kroków:
K01: px  
K02: Dopóki (pup) ≠ p, wykonuj p ← (pup) ; idziemy w kierunku korzenia
K03: Zakończ z wynikiem p ; zwracamy adres korzenia

 

UnionSets(x,y)

Wejście
x,y   wskazania węzłów drzewa
Wyjście:

Dołącza drzewo z węzłem y do drzewa z węzłem x.

Elementy pomocnicze:
rx,ry    wskaźniki węzłów drzewa
Lista kroków:
K01: rx ← FindSet(x) ; odnajdujemy korzeń drzewa z węzłem x
K02: ry ← FindSet(y) ; odnajdujemy korzeń drzewa z węzłem y
K03: Jeśli rx = ry, to zakończ ; korzenie muszą być różne
K04: (ryup) ← rx ; dołączamy drzewo z y do korzenia drzewa z x
K05: Zakończ  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program tworzy 10 drzew jednowęzłowych, a następnie losuje 10 razy pary węzłów. Dla wylosowanych węzłów wykonywana jest operacja UnionSets, co powoduje połączenie drzew z tymi węzłami. Na końcu wypisana zostaje przynależność każdego elementu do określonego podzbioru, liczba podzbiorów oraz zawartość tych podzbiorów.

 

Lazarus
// Struktura zbiorów rozłącznych
// Data : 31.03.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------

const N = 10;                     // Liczba węzłów

// Węzeł
type
  PTNode = ^TNode;
  TNode =  record
    up   : PTNode;                // Rodzic węzła
    data : integer;               // Zawartość węzła
  end;

// Tworzy drzewo jednowęzłowe
//---------------------------
procedure MakeSet(x : PTNode);
begin
  x^.up := x;                     // x staje się korzeniem drzewa
end;

// Zwraca korzeń drzewa
//---------------------
function FindSet(x : PTNode) : PTNode;
var
  p : PTNode;
begin
  p := x;
  while p^.up <> p do p := p^.up; // Idziemy w kierunku korzenia drzewa
  FindSet := p;                   // Zwracamy adres korzenia
end;

// Dołącza korzeń drzewa y do korzenia drzewa x
//---------------------------------------------
procedure UnionSets(x,y : PTNode);
var
  rx,ry : PTNode;
begin
  rx := FindSet(x);               // Wyznaczamy korzeń drzewa z węzłem x
  ry := FindSet(y);               // Wyznaczamy korzeń drzewa z węzłem y
  if rx <> ry then                // Korzenie muszą być różne
    ry^.up := rx;                 // Korzeniem drzewa y staje się korzeń drzewa x
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  Z : array [0..N-1] of TNode;
  p : PTNode;
  i,j,x,y,c : integer;
begin
  Randomize;                      // Inicjujemy generator pseudolosowy

  for i := 0 to N - 1 do
  begin
    Z[i].data := i;               // Węzły numerujemy kolejno
    MakeSet(addr(Z[i]));          // i tworzymy z nich jednowęzłowe drzewa
  end;

  for i := 1 to 10 do
  begin
    x := random(N);               // Losujemy dwa węzły
    y := random(N);
    UnionSets(addr(Z[x]),addr(Z[y])); // Łączymy drzewa z wylosowanymi węzłami
  end;

  // Wypisujemy wyniki

  c := 0;                         // Licznik podzbiorów

  for i := 0 to N - 1 do
  begin
    x := FindSet(addr(Z[i]))^.data;
    if x = i then inc(c);
    writeln(i,' is in set ',x);
  end;

  writeln;

  writeln('Numeber of sets = ',c);

  writeln;

  for i := 0 to N - 1 do
  begin
    p := FindSet(addr(Z[i]));
    if p^.data = i then
    begin
      write('Set ',i,' : ');
      for j := 0 to N - 1 do
        if p = FindSet(addr(Z[j]))then write(j,' ');
      writeln;
    end;
  end;
end.
Code::Blocks
// Struktura zbiorów rozłącznych
// Data : 31.03.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 10;                 // Liczba węzłów

// Węzeł

struct TNode
{
  TNode *up;                      // Rodzic węzła
  int data;                       // Zawartość węzła
};

// Tworzy drzewo jednowęzłowe
//---------------------------
void MakeSet(TNode * x)
{
  x->up = x;                      // x staje się korzeniem drzewa
}

// Zwraca korzeń drzewa
//---------------------
TNode *  FindSet(TNode * x)
{
  TNode * p;

  for(p = x; p->up != p; p = p->up); // Idziemy w kierunku korzenia drzewa
  return p;                       // Zwracamy adres korzenia
}

// Dołącza korzeń drzewa y do korzenia drzewa x
//---------------------------------------------
void UnionSets(TNode * x, TNode * y)
{
  TNode *rx, *ry;

  rx = FindSet(x);                // Wyznaczamy korzeń drzewa z węzłem x
  ry = FindSet(y);                // Wyznaczamy korzeń drzewa z węzłem y
  if(rx != ry)                    // Korzenie muszą być różne
    ry->up = rx;                  // Korzeniem drzewa y staje się korzeń drzewa x
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  TNode Z[N],*p;
  int i,j,x,y,c;

  srand(time(NULL));              // Inicjujemy generator pseudolosowy

  for(i = 0; i < N; i++)
  {
    Z[i].data = i;                // Węzły numerujemy kolejno
    MakeSet(&Z[i]);               // i tworzymy z nich jednowęzłowe drzewa
  }

  for(i = 0; i < N; i++)
  {
    x = rand() % N;               // Losujemy dwa węzły
    y = rand() % N;
    UnionSets(&Z[x],&Z[y]);       // Łączymy drzewa z wylosowanymi węzłami
  }

  // Wypisujemy wyniki

  c = 0;                         // Licznik podzbiorów

  for(i = 0; i < N; i++)
  {
    x = FindSet(&Z[i])->data;
    if(x == i) c++;
    cout << i << " is in set " << x << endl;
  }

  cout << endl << "Numeber of sets = " << c << endl << endl;

  for(i = 0; i < N; i++)
  {
    p = FindSet(&Z[i]);
    if(p->data == i)
    {
      cout << "Set " << i << " : ";
      for(j = 0; j < N; j++)
        if(p == FindSet(&Z[j])) cout << j << " ";
      cout << endl;
    }
  }
  return 0;
}
Free Basic
' Struktura zbiorów rozłącznych
' Data : 31.03.2014
' (C)2014 mgr Jerzy Wałaszek
'----------------------------

const N = 10                      ' Liczba węzłów

' Węzeł

Type TNode
  up As TNode Ptr                 ' Rodzic węzła
  Data As Integer                 ' Zawartość węzła
End Type

' Tworzy drzewo jednowęzłowe
'---------------------------
Sub MakeSet(ByVal x As TNode Ptr)
  x->up = x                       ' x staje się korzeniem drzewa
End Sub

' Zwraca korzeń drzewa
'---------------------
Function FindSet(ByVal x As TNode Ptr) As TNode Ptr

  Dim As TNode Ptr p

  p = x
  While p->up <> p                ' Idziemy w kierunku korzenia drzewa
    p = p->up
  Wend
  Return p                        ' Zwracamy adres korzenia
End Function

' Dołącza korzeń drzewa y do korzenia drzewa x
'---------------------------------------------
Sub UnionSets(ByVal x As TNode Ptr, ByVal y As TNode Ptr)

  Dim As TNode Ptr rx,ry

  rx = FindSet(x)                 ' Wyznaczamy korzeń drzewa z węzłem x
  ry = FindSet(y)                 ' Wyznaczamy korzeń drzewa z węzłem y
  If rx <> ry Then                ' Korzenie muszą być różne
    ry->up = rx                   ' Korzeniem drzewa y staje się korzeń drzewa x
  End If
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As TNode Z(N)
Dim As TNode Ptr p
Dim As Integer i,j,x,y,c

Randomize                         ' Inicjujemy generator pseudolosowy

For i = 0 To N - 1
  Z(i).data = i                   ' Węzły numerujemy kolejno
  MakeSet(VarPtr(Z(i)))           ' i tworzymy z nich jednowęzłowe drzewa
Next

For i = 0 To N - 1
  x = Int(Rnd * N)                ' Losujemy dwa węzły
  y = Int(Rnd * N)
  UnionSets(VarPtr(Z(x)),VarPtr(Z(y))) ' Łączymy drzewa z wylosowanymi węzłami
Next

' Wypisujemy wyniki

c = 0                             ' Licznik podzbiorów

For i = 0 To N - 1
  x = FindSet(VarPtr(Z(i)))->Data
  If x = i Then c += 1
  Print i;" is in set";x
Next

Print
Print "Numeber of sets =";c
Print

For i = 0 To N - 1
  p = FindSet(VarPtr(Z(i)))
  If p->data = i Then
    Print "Set";i;" :";
    For j = 0 To N - 1
      If p = FindSet(VarPtr(Z(j))) Then Print j;
    Next
    Print
  End If
Next

End
Wynik
0 is in set 1
1 is in set 1
2 is in set 2
3 is in set 1
4 is in set 8
5 is in set 1
6 is in set 1
7 is in set 8
8 is in set 8
9 is in set 9

Numeber of sets = 4

Set 1 : 0 1 3 5 6
Set 2 : 2
Set 8 : 4 7 8
Set 9 : 9

 

Rozwiązanie nr 2

Pokażemy teraz, jak usprawnić naszą strukturę zbiorów rozłącznych. Najpierw zajmijmy się operacją FindSet(x). Operacja ta zwraca adres korzenia drzewa, które zawiera testowany węzeł x. Wymaga to przejścia przez kolejne węzły nadrzędne w strukturze drzewa. Zmienimy ją zatem tak, aby w trakcie przechodzenia przez te węzły ustawiała w ich polach up adres korzenia:

 

 

Operacji tej nie da się efektywnie przeprowadzić w jednym wywołaniu funkcji FindSet. Będzie ona realizowana stopniowo. Jeśli wywołamy FindSet(x), to ustawi ona pola up na korzeń drzewa w węźle x oraz we wszystkich jego węzłach nadrzędnych, przez które przejdzie w drodze do korzenia. Węzły potomne węła x pozostaną niezmienione.

 

 

Zysk pojawi się w kolejnych wywołaniach FindSet. Jak widać na powyższym rysunku, po wykonaniu FindSet(C) kolejne wykonania funkcji FindSet(C) i FindSet(B) będą już szybsze (wykonają się w czasie stałym). Także szybsze będzie teraz wykonanie FindSet(D), które również ustawi w węźle D pole up na korzeń drzewa. Operację taką nazywamy kompresją ścieżki (ang. path compression).

Drugie usprawnienie dotyczy operacji UnionSets. Dodajmy do każdego węzła nowe pole o nazwie rank (ang. poziom, ranga, stopień). Gdy drzewo jest tworzone, pole rank przyjmuje wartość 0. Teraz operacja UnionSets(x,y) porównuje pola rank obu drzew z węzłami x i y. Jeśli ranga drzewa x jest większa od rangi drzewa y, to drzewo y (jako "niższe w randze") zostaje dołączone do drzewa x. W przeciwnym razie następuje dołączenie odwrotne: do korzenia drzewa y dołączane jest drzewo x, a pole rank drzewa y zostaje zwiększone o 1 (awansuje w randze). Innymi słowy: zawsze przy łączeniu dwóch drzew korzeń "mniejszego" drzewa zostaje dołączony do korzenia drzewa "większego". Działanie to gwarantuje nam, iż wysokość drzew nie będzie niekontrolowanie rosnąć.

 

 

Algorytmy dla struktury zbiorów rozłącznych zrealizowanej za pomocą drzew – wersja 2

MakeSet(x)

Wejście
x   wskazanie węzła drzewa
Wyjście:

Utworzenie drzewa z jednym węzłem x.

Lista kroków:
K01: (xup) ← x ; rodzicem korzenia jest korzeń
K02: (xrank) ← 0 ; zerujemy rangę

 

FindSet(x)

Wejście
x   wskazanie węzła drzewa
Wyjście:

Wskazanie korzenia drzewa zawierającego węzeł x. Dodatkowo ustawia pola up na korzeń w węźle x oraz we wszystkich węzłach nadrzędnych.

Lista kroków:
K01: Jeśli (xup) ≠ x, to (xup) ← FindSet(xup) ; jeśli x nie jest korzeniem, to wywołujemy funkcję rekurencyjnie i ustawiamy pole up na korzeń
K02: Zakończ z wynikiem (xup) ; zwracamy adres korzenia

 

UnionSets(x,y)

Wejście
x,y   wskazania węzłów drzewa
Wyjście:

Dołącza drzewo z węzłem y do drzewa z węzłem x. Modyfikuje pola up i rank.

Elementy pomocnicze:
rx,ry    wskaźniki węzłów drzewa
Lista kroków:
K01: rx ← FindSet(x) ; odnajdujemy korzeń drzewa z węzłem x
K02: ry ← FindSet(y) ; odnajdujemy korzeń drzewa z węzłem y
K03: Jeśli rx = ry, to zakończ ; korzenie muszą być różne
K04: Jeśli (rxrank) > (ryrank), to
    (ryup) ← rx
    Zakończ
; sprawdzamy rangi korzeni drzew i jeśli ranga rx jest większa,
; to do drzewa rx (większego) dołączamy drzewo ry (mniejsze)
; i kończymy
K05: (rxup) ← ry ; w przeciwnym razie dołączamy drzewo rx do drzewa ry
K06: Jeśli (rxrank) = (ryrank), to
    (ryrank) ← (ryrank) + 1
; jeśli rangi są równe, to zwiększamy rangę drzewa y,
; gdyż stało się ono teraz większe
K07: Zakończ  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program tworzy 10 drzew jednowęzłowych, a następnie losuje 10 razy pary węzłów. Dla wylosowanych węzłów wykonywana jest operacja UnionSets, co powoduje połączenie drzew z tymi węzłami. Na końcu wypisana zostaje przynależność każdego elementu do określonego podzbioru, liczba podzbiorów oraz zawartość tych podzbiorów z ich rangą.

 

Lazarus
// Struktura zbiorów rozłącznych
// Data : 1.04.2014
// (C)2014 mgr Jerzy Wałaszek
//------------------------------

const N = 10;                     // Liczba węzłów

// Węzeł
type
  PTNode = ^TNode;
  TNode =  record
    up   : PTNode;                // Rodzic węzła
    rank : integer;               // Ranga
    data : integer;               // Zawartość węzła
  end;

// Tworzy drzewo jednowęzłowe
//---------------------------
procedure MakeSet(x : PTNode);
begin
  x^.up := x;                     // x staje się korzeniem drzewa
  x^.rank := 0;                   // Rangę zerujemy
end;

// Zwraca korzeń drzewa i ustawia pola up
// wszystkich węzłów nadrzędnych aż do korzenia
//---------------------------------------------
function FindSet(x : PTNode) : PTNode;
begin
  if x^.up <> x then x^.up := FindSet(x^.up);
  FindSet := x^.up;
end;

// Łączy ze sobą drzewa z x i z y
//-------------------------------
procedure UnionSets(x,y : PTNode);
var
  rx,ry : PTNode;
begin
  rx := FindSet(x);               // Wyznaczamy korzeń drzewa z węzłem x
  ry := FindSet(y);               // Wyznaczamy korzeń drzewa z węzłem y
  if rx <> ry then                // Korzenie muszą być różne
  begin
    if rx^.rank > ry^.rank then   // Porównujemy rangi drzew
       ry^.up := rx               // rx większe, dołączamy ry
    else
    begin
      rx^.up := ry;               // równe lub ry większe, dołączamy rx
      if rx^.rank = ry^.rank then inc(ry^.rank);
    end;
  end;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  Z : array [0..N-1] of TNode;
  p : PTNode;
  i,j,x,y,c : integer;
begin
  Randomize;                      // Inicjujemy generator pseudolosowy

  for i := 0 to N - 1 do
  begin
    Z[i].data := i;               // Węzły numerujemy kolejno
    MakeSet(addr(Z[i]));          // i tworzymy z nich jednowęzłowe drzewa
  end;

  for i := 1 to 10 do
  begin
    x := random(N);               // Losujemy dwa węzły
    y := random(N);
    UnionSets(addr(Z[x]),addr(Z[y])); // Łączymy drzewa z wylosowanymi węzłami
  end;

  // Wypisujemy wyniki

  c := 0;                         // Licznik podzbiorów
  for i := 0 to N - 1 do
  begin
    x := FindSet(addr(Z[i]))^.data;
    if x = i then inc(c);
    writeln(i,' is in set ',x);
  end;
  writeln;
  writeln('Numeber of sets = ',c);
  writeln;
  for i := 0 to N - 1 do
  begin
    p := FindSet(addr(Z[i]));
    if p^.data = i then
    begin
      write('Set ',i,' rank = ',p^.rank,' : ');
      for j := 0 to N - 1 do
        if p = FindSet(addr(Z[j]))then write(j,' ');
      writeln;
    end;
  end;
end.
Code::Blocks
// Struktura zbiorów rozłącznych
// Data : 1.04.2014
// (C)2014 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 10;                 // Liczba węzłów

// Węzeł

struct TNode
{
  TNode *up;                      // Rodzic węzła
  int rank;                       // Ranga
  int data;                       // Zawartość węzła
};

// Tworzy drzewo jednowęzłowe
//---------------------------
void MakeSet(TNode * x)
{
  x->up = x;                      // x staje się korzeniem drzewa
  x->rank = 0;                    // Rangę zerujemy
}

// Zwraca korzeń drzewa i ustawia pola up
// wszystkich węzłów nadrzędnych aż do korzenia
//---------------------------------------------
TNode * FindSet(TNode * x)
{
  if(x->up != x) x->up = FindSet(x->up);
  return x->up;
}

// Łączy ze sobą drzewa z x i z y
//-------------------------------
void UnionSets(TNode *x, TNode *y)
{
  TNode *rx,*ry;

  rx = FindSet(x);                // Wyznaczamy korzeń drzewa z węzłem x
  ry = FindSet(y);                // Wyznaczamy korzeń drzewa z węzłem y
  if(rx != ry)                    // Korzenie muszą być różne
  {
    if(rx->rank > ry->rank)       // Porównujemy rangi drzew
       ry->up = rx;               // rx większe, dołączamy ry
    else
    {
      rx->up = ry;                // równe lub ry większe, dołączamy rx
      if(rx->rank == ry->rank) ry->rank++;
    }
  }
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  TNode Z[N],*p;
  int i,j,x,y,c;

  srand(time(NULL));              // Inicjujemy generator pseudolosowy

  for(i = 0; i < N; i++)
  {
    Z[i].data = i;                // Węzły numerujemy kolejno
    MakeSet(&Z[i]);               // i tworzymy z nich jednowęzłowe drzewa
  }

  for(i = 0; i < N; i++)
  {
    x = rand() % N;               // Losujemy dwa węzły
    y = rand() % N;
    UnionSets(&Z[x],&Z[y]);       // Łączymy drzewa z wylosowanymi węzłami
  }

  // Wypisujemy wyniki

  c = 0;                         // Licznik podzbiorów

  for(i = 0; i < N; i++)
  {
    x = FindSet(&Z[i])->data;
    if(x == i) c++;
    cout << i << " is in set " << x << endl;
  }

  cout << endl << "Numeber of sets = " << c << endl << endl;

  for(i = 0; i < N; i++)
  {
    p = FindSet(&Z[i]);
    if(p->data == i)
    {
      cout << "Set " << i << " rank = " << p->rank << " : ";
      for(j = 0; j < N; j++)
        if(p == FindSet(&Z[j])) cout << j << " ";
      cout << endl;
    }
  }
  return 0;
}
Free Basic
' Struktura zbiorów rozłącznych
' Data : 1.04.2014
' (C)2014 mgr Jerzy Wałaszek
'------------------------------

const N = 10                      ' Liczba węzłow

' Węzeł

Type TNode
  up As TNode Ptr                 ' Rodzic węzła
  rank As Integer                 ' Ranga
  Data As Integer                 ' Zawartość węzła
End Type

' Tworzy drzewo jednowęzłowe
'---------------------------
Sub MakeSet(ByVal x As TNode Ptr)
  x->up = x                       ' x staje się korzeniem drzewa
  x->rank = 0                     ' Rangę zerujemy  
End Sub

' Zwraca korzeń drzewa i ustawia pola up
' wszystkich węzłów nadrzędnych aż do korzenia
'---------------------------------------------
Function FindSet(ByVal x As TNode Ptr) As TNode Ptr
  If x->up <> x Then x->up = FindSet(x->up)
  return x->up
End Function

' Łączy ze sobą drzewa z x i z y
'-------------------------------
Sub UnionSets(ByVal x As TNode Ptr, ByVal y As TNode Ptr)

  Dim As TNode Ptr rx,ry

  rx = FindSet(x)                 ' Wyznaczamy korzeń drzewa z węzłem x
  ry = FindSet(y)                 ' Wyznaczamy korzeń drzewa z węzłem y
  If rx <> ry Then                ' Korzenie muszą być różne
    If rx->rank > ry->rank Then   ' Porównujemy rangi drzew
      ry->up = rx                 ' rx większe, dołączamy ry
    Else
      rx->up = ry                 ' równe lub ry większe, dołączamy rx
      If rx->rank = ry->rank Then ry->rank += 1
    End If
  End If
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As TNode Z(N)
Dim As TNode Ptr p
Dim As Integer i,j,x,y,c

Randomize                         ' Inicjujemy generator pseudolosowy

For i = 0 To N - 1
  Z(i).data = i                   ' Węzły numerujemy kolejno
  MakeSet(VarPtr(Z(i)))           ' i tworzymy z nich jednowęzłowe drzewa
Next

For i = 0 To N - 1
  x = Int(Rnd * N)                ' Losujemy dwa węzły
  y = Int(Rnd * N)
  UnionSets(VarPtr(Z(x)),VarPtr(Z(y))) ' Łączymy drzewa z wylosowanymi węzłami
Next

' Wypisujemy wyniki

c = 0                             ' Licznik podzbiorów

For i = 0 To N - 1
  x = FindSet(VarPtr(Z(i)))->Data
  If x = i Then c += 1
  Print i;" is in set";x
Next

Print
Print "Numeber of sets =";c
Print

For i = 0 To N - 1
  p = FindSet(VarPtr(Z(i)))
  If p->data = i Then
    Print "Set";i;" rank =";p->rank;" :";
    For j = 0 To N - 1
      If p = FindSet(VarPtr(Z(j))) Then Print j;
    Next
    Print
  End If
Next

End
Wynik
0 is in set 2
1 is in set 3
2 is in set 2
3 is in set 3
4 is in set 3
5 is in set 3
6 is in set 6
7 is in set 2
8 is in set 3
9 is in set 3

Numeber of sets = 3

Set 2 rank = 1 : 0 2 7
Set 3 rank = 2 : 1 3 4 5 8 9
Set 6 rank = 0 : 6

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.