Algorytmy i Struktury Danych - Zbiory rozłączne

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:

make_set(x)

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

find_set(x)

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

union_sets(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

make_set(x)

Wejście:

x : wskazanie węzła drzewa.

Wyjście:

Utworzenie drzewa z jednym węzłem x.

Lista kroków:

K01: (x→up) ← x ; rodzicem korzenia jest korzeń
K02: Zakończ

find_set(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: p ← x
K02: Dopóki p→up ≠ p, ; idziemy w kierunku korzenia
     wykonuj: p ← p→up
K03: Zakończ z wynikiem p ; zwracamy adres korzenia

union_sets(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 ← find_set(x) ; odnajdujemy korzeń drzewa z węzłem x
K02: ry ← find_set(y) ; odnajdujemy korzeń drzewa z węzłem y
K03: Jeśli rx = ry, ; korzenie muszą być różne
     to zakończ
K04: ry→up ← rx ; dołączamy drzewo z y do korzenia drzewa z x
K05: Zakończ

Przykładowe programy

Uwaga:

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 union_sets, 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.

Pascal

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

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

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

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

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

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

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

var
  Z : array [0..N-1] of Tnode;
  p : PTnode;
  i, j, x, y, c : integer;
begin
  Randomize;
  for i := 0 to N-1 do
  begin
    // Węzły numerujemy kolejno
    Z[i].data := i;
    // i tworzymy z nich jednowęzłowe drzewa
    make_set(addr(Z[i]));
  end;
  for i := 1 to 10 do
  begin
    // Losujemy dwa węzły
    x := random(N);
    y := random(N);
    // Łączymy drzewa z wylosowanymi węzłami
    union_sets(addr(Z[x]), addr(Z[y]));
  end;

  // Wypisujemy wyniki

  // Licznik podzbiorów
  c := 0;
  for i := 0 to N-1 do
  begin
    x := find_set(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 := find_set(addr(Z[i]));
    if p^.data = i then
    begin
      write('Set ', i, ' : ');
      for j := 0 to N-1 do
        if p = find_set(addr(Z[j])) then
          write(j, ' ');
      writeln;
    end;
  end;
end.

C++

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

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

using namespace std;

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

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

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

// Zwraca korzeń drzewa
//---------------------
Tnode *  find_set(Tnode * x)
{
  Tnode * p;

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

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

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

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

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

  srand(time(NULL));
  for(i = 0; i < N; i++)
  {
    // Węzły numerujemy kolejno
    Z[i].data = i;
    // i tworzymy z nich
    // drzewa jednowęzłowe
    make_set(&Z[i]);
  }
  for(i = 0; i < N; i++)
  {
    // Losujemy dwa węzły
    x = rand() % N;
    y = rand() % N;
    // Łączymy drzewa
    // z wylosowanymi węzłami
    union_sets(&Z[x],&Z[y]);
  }

  // Wypisujemy wyniki

  // Licznik podzbiorów
  c = 0;
  for(i = 0; i < N; i++)
  {
    x = find_set(&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 = find_set(&Z[i]);
    if(p->data == i)
    {
      cout << "Set " << i << ": ";
      for(j = 0; j < N; j++)
        if(p == find_set(&Z[j]))
          cout << j << " ";
      cout << endl;
    }
  }
  return 0;}

Basic

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

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

' Węzeł
Type Tnode
  ' Rodzic węzła
  up As Tnode Ptr
  ' Zawartość węzła
  data As Integer
End Type

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

' Zwraca korzeń drzewa
'---------------------
Function find_set(ByVal x As Tnode Ptr) _
                          As Tnode Ptr
  Dim As Tnode Ptr p

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

' Dołącza korzeń drzewa y
' do korzenia drzewa x
'------------------------
Sub union_sets(ByVal x As Tnode Ptr, _
               ByVal y As Tnode Ptr)
  Dim As Tnode Ptr rx, ry

  ' Wyznaczamy korzeń drzewa z węzłem x
  rx = find_set(x)
  ' Wyznaczamy korzeń drzewa z węzłem y
  ry = find_set(y)
  ' Korzenie muszą być różne
  If rx <> ry Then
    ' Korzeniem drzewa y
    ' staje się korzeń drzewa x
    ry->up = rx
  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
For i = 0 To N-1
  ' Węzły numerujemy kolejno
  Z(i).data = i
  ' i tworzymy z nich
  ' drzewa jednowęzłowe
  make_set(VarPtr(Z(i)))
Next
For i = 0 To N-1
  ' Losujemy dwa węzły
  x = Int(Rnd * N)
  y = Int(Rnd * N)
  ' Łączymy drzewa z wylosowanymi węzłami
  union_sets(VarPtr(Z(x)), VarPtr(Z(y)))
Next

' Wypisujemy wyniki

' Licznik podzbiorów
c = 0
For i = 0 To N-1
  x = find_set(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 = find_set(VarPtr(Z(i)))
  If p->data = i Then
    Print "Set";i;":";
    For j = 0 To N-1
      If p = find_set(VarPtr(Z(j))) Then _
        Print j;
    Next
    Print
  End If
Next
End

Python (dodatek)

# Struktura zbiorów rozłącznych
# Data : 19.08.2024
# (C)2024 mgr Jerzy Wałaszek
#------------------------------

import random

# Liczba węzłów
N = 10


# Węzeł
class Tnode:


    def __init__(self, d):
        # Rodzic węzła
        self.up = None
        # Zawartość węzła
        self.data = d


# Tworzy drzewo jednowęzłowe
#---------------------------
def make_set(x):
    # x staje się korzeniem drzewa
    x.up = x


# Zwraca korzeń drzewa
#---------------------
def find_set(x):
    p = x
    # Idziemy w kierunku korzenia drzewa
    while p.up is not p:
        p = p.up
    # Zwracamy adres korzenia
    return p


# Dołącza korzeń drzewa y
# do korzenia drzewa x
#------------------------
def union_sets(x,y):
    # Wyznaczamy korzeń drzewa z węzłem x
    rx = find_set(x)
    # Wyznaczamy korzeń drzewa z węzłem y
    ry = find_set(y)
    # Korzenie muszą być różne
    if rx is not ry:
        # Korzeniem drzewa y
        # staje się korzeń drzewa x
        ry.up = rx


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

Z = [Tnode(i) for i in range(N)]

# tworzymy drzewa jednowęzłowe

for i in range(N):
    make_set(Z[i])
for i in range(N):
    # Losujemy dwa węzły
    x = random.randrange(N)
    y = random.randrange(N)
    # Łączymy drzewa
    # z wylosowanymi węzłami
    union_sets(Z[x], Z[y])

# Wypisujemy wyniki

# Licznik podzbiorów
c = 0
for i in range(N):
    x = find_set(Z[i]).data
    if x == i: c += 1
    print(i,"is in set",x)
print()
print("Numeber of sets =",c)
print()
for i in range(N):
    p = find_set(Z[i])
    if p.data == i:
        print("Set", i, ":", end=" ")
        for j in range(N):
            if p is find_set(Z[j]):
                print(j, end=" ")
        print()

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

Na początek: podrozdziału strony

Pokażemy teraz, jak usprawnić naszą strukturę zbiorów rozłącznych. Najpierw zajmijmy się operacją find_set(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 find_set( ). Będzie ona realizowana stopniowo. Jeśli wywołamy find_set(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ęzła x pozostaną niezmienione.

Zysk pojawi się w kolejnych wywołaniach find_set( ). Jak widać na powyższym rysunku, po wykonaniu find_set(C) kolejne wykonania funkcji find_set(C) i find_set(B) będą już szybsze (wykonają się w czasie stałym). Także szybsze będzie teraz wykonanie find_set(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 union_sets( ). 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 union_sets(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

make_set(x)

Wejście:

x : wskazanie węzła drzewa.

Wyjście:

Utworzenie drzewa z jednym węzłem x.

Lista kroków:

K01: x→up ← x ; rodzicem korzenia jest korzeń
K02: x→rank ← 0 ; zerujemy rangę
K03: Zakończ

find_set(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 x→up ≠ x, ; jeśli x nie jest korzeniem,
     to x→up ← find_set(x→up) ; to wywołujemy funkcję
     ; rekurencyjnie i ustawiamy pole up na korzeń
K02: Zakończ z wynikiem x→up ; zwracamy adres korzenia

union_sets(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 ← find_set(x) ; odnajdujemy korzeń drzewa z węzłem x
K02: ry ← find_set(y) ; odnajdujemy korzeń drzewa z węzłem y
K03: Jeśli rx = ry, ; korzenie muszą być różne
     to zakończ
K04: Jeśli rx→rank > ry→rank, ; sprawdzamy rangi korzeni drzew
     to ry→up ← rx i zakończ ; i jeśli ranga rx jest większa,
     ; to do drzewa rx (większego) dołączamy drzewo ry (mniejsze)
     ; i kończymy
K05: rx→up ← ry ; w przeciwnym razie dołączamy drzewo rx
     ; do drzewa ry
K06: Jeśli rx→rank = ry→rank, ; jeśli rangi są równe,
     to ry→rank ← ry→rank+1 ; to zwiększamy rangę drzewa y,
     ; gdyż stało się ono teraz większe
K07: Zakończ

Przykładowe programy

Uwaga:

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 union_sets( ), 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ą.

Pascal

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

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

// 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 make_set(x : PTnode);
begin
  // x staje się korzeniem drzewa
  x^.up := x;
  // Rangę zerujemy
  x^.rank := 0;
end;

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

// Łączy ze sobą drzewa z x i z y
//-------------------------------
procedure union_sets(x, y : PTnode);
var
  rx, ry : PTnode;
begin
  // Wyznaczamy korzeń drzewa
  // z węzłem x
  rx := find_set(x);
  // Wyznaczamy korzeń drzewa
  // z węzłem y
  ry := find_set(y);
  // Korzenie muszą być różne
  if rx <> ry then
  begin
    // Porównujemy rangi drzew
    if rx^.rank > ry^.rank then
       // rx większe, dołączamy ry
      ry^.up := rx
    else
    begin
      // równe lub ry większe,
      // dołączamy rx
      rx^.up := ry;
      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;
  for i := 0 to N-1 do
  begin
    // Węzły numerujemy kolejno
    Z[i].data := i;
    // i tworzymy z nich
    // jednowęzłowe drzewa
    make_set(addr(Z[i]));
  end;
  for i := 1 to 10 do
  begin
    // Losujemy dwa węzły
    x := random(N);
    y := random(N);
    // Łączymy drzewa
    // z wylosowanymi węzłami
    union_sets(addr(Z[x]), addr(Z[y]));
  end;

  // Wypisujemy wyniki

  // Licznik podzbiorów
  c := 0;
  for i := 0 to N-1 do
  begin
    x := find_set(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 := find_set(addr(Z[i]));
    if p^.data = i then
    begin
      write('Set ', i, ' rank = ',
            p^.rank, ' : ');
      for j := 0 to N-1 do
        if p = find_set(addr(Z[j])) then
          write(j, ' ');
      writeln;
    end;
  end;
  readln;
end.

C++

// 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 make_set(Tnode * x)
{
  // x staje się korzeniem drzewa
  x->up = x;
  // Rangę zerujemy
  x->rank = 0;
}

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

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

  // Wyznaczamy korzeń drzewa
  // z węzłem x
  rx = find_set(x);
  // Wyznaczamy korzeń drzewa
  // z węzłem y
  ry = find_set(y);
  // Korzenie muszą być różne
  if(rx != ry)
  {
    // Porównujemy rangi drzew
    if(rx->rank > ry->rank)
      // rx większe, dołączamy ry
      ry->up = rx;
    else
    {
      // równe lub ry większe,
      // dołączamy rx
      rx->up = ry;
      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));
  for(i = 0; i < N; i++)
  {
    // Węzły numerujemy kolejno
    Z[i].data = i;
    // i tworzymy z nich
    // jednowęzłowe drzewa
    make_set(&Z[i]);
  }
  for(i = 0; i < N; i++)
  {
    // Losujemy dwa węzły
    x = rand() % N;
    y = rand() % N;
    // Łączymy drzewa
    // z wylosowanymi węzłami
    union_sets(&Z[x], &Z[y]);
  }

  // Wypisujemy wyniki

  // Licznik podzbiorów
  c = 0;
  for(i = 0; i < N; i++)
  {
    x = find_set(&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 = find_set(&Z[i]);
    if(p->data == i)
    {
      cout << "Set " << i
           << " rank = " << p->rank
           << ": ";
      for(j = 0; j < N; j++)
        if(p == find_set(&Z[j]))
          cout << j << " ";
      cout << endl;
    }
  }
  return 0;
}

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 make_set(ByVal x As Tnode Ptr)
  ' x staje się korzeniem drzewa
  x->up = x
  x->rank = 0 ' Rangę zerujemy 
End Sub

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

' Łączy ze sobą drzewa z x i z y
'-------------------------------
Sub union_sets(ByVal x As Tnode Ptr, _
               ByVal y As Tnode Ptr)
  Dim As Tnode Ptr rx, ry

  ' Wyznaczamy korzeń drzewa z węzłem x
  rx = find_set(x)
  ' Wyznaczamy korzeń drzewa z węzłem y
  ry = find_set(y)
  ' Korzenie muszą być różne
  If rx <> ry Then
    ' Porównujemy rangi drzew
    If rx->rank > ry->rank Then
      ' rx większe, dołączamy ry
      ry->up = rx
    Else
      ' równe lub ry większe,
      ' dołączamy rx
      rx->up = ry
      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
For i = 0 To N-1
  ' Węzły numerujemy kolejno
  Z(i).data = i
  ' i tworzymy z nich jednowęzłowe drzewa
  make_set(VarPtr(Z(i)))
Next
For i = 0 To N-1
  ' Losujemy dwa węzły
  x = Int(Rnd * N)
  y = Int(Rnd * N)
  ' Łączymy drzewa z wylosowanymi węzłami
  union_sets(VarPtr(Z(x)), VarPtr(Z(y)))
Next

' Wypisujemy wyniki

c = 0 ' Licznik podzbiorów
For i = 0 To N-1
  x = find_set(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 = find_set(VarPtr(Z(i)))
  If p->data = i Then
    Print "Set";i;" rank =";p->rank;":";
    For j = 0 To N-1
      If p = find_set(VarPtr(Z(j))) Then _
        Print j;
    Next
    Print
  End If
Next
End

Python (dodatek)

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

import random

N = 10 # Liczba węzłow


# Węzeł
class Tnode:


    def __init__(self,d):
        # Rodzic węzła
        self.up = None
        # Ranga
        self.rank = 0
        # Zawartość węzła
        self.data = d


# Tworzy drzewo jednowęzłowe
#---------------------------
def make_set(x):
    # x staje się korzeniem drzewa
    x.up = x
    x.rank = 0 # Rangę zerujemy 


# Zwraca korzeń drzewa i ustawia
# pola up wszystkich węzłów
# nadrzędnych aż do korzenia
#-------------------------------
def find_set(x):
    if x.up is not x:
        x.up = find_set(x.up)
    return x.up


# Łączy ze sobą drzewa z x i z y
#-------------------------------
def union_sets(x, y):
    # Wyznaczamy korzeń drzewa
    # z węzłem x
    rx = find_set(x)
    # Wyznaczamy korzeń drzewa
    # z węzłem y
    ry = find_set(y)
    # Korzenie muszą być różne
    if rx is not ry:
        # Porównujemy rangi drzew
        if rx.rank > ry.rank:
            # rx większe,
            # dołączamy ry
            ry.up = rx
        else:
            # równe lub ry większe,
            # dołączamy rx
            rx.up = ry
            if rx.rank == ry.rank:
                ry.rank += 1


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

z = [Tnode(i) for i in range(N)]
for i in range(N):
    # tworzymy jednowęzłowe drzewa
    make_set(z[i])
for i in range(N):
    # Losujemy dwa węzły
    x = random.randrange(N)
    y = random.randrange(N)
    # Łączymy drzewa
    # z wylosowanymi węzłami
    union_sets(z[x],z[y])

# Wypisujemy wyniki

c = 0 # Licznik podzbiorów
for i in range(N):
    x = find_set(z[i]).data
    if x == i: c += 1
    print(i,"is in set",x)
print()
print("Numeber of sets =",c)
print()
for i in range(N):
    p = find_set(z[i])
    if p.data == i:
        print("Set", i, "rank =",
              p.rank, ":", end=" ")
        for j in range(N-1):
            if p is find_set(z[j]):
                print(j, end=" ")
        print()

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

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Zbiory rozłączne – implementacja za pomocą drzew

Problem

Rozwiązanie nr 1

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

make_set(x)

Wejście:

Wyjście:

Lista kroków:

find_set(x)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

union_sets(x, y)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 2

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

make_set(x)

Wejście:

Wyjście:

Lista kroków:

find_set(x)

Wejście:

Wyjście:

Lista kroków:

union_sets(x, y)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy