Algorytmy i Struktury Danych - Zbiory rozłączne

Struktura zbiorów rozłącznych (ang. disjoint sets structure) pozwala reprezentować zbiory, które nie posiadają części wspólnych. Podstawowym problemem jest określenie sposobu rozpoznawania przynależności elementu do jednego z podzbiorów. Otóż umówmy się, że w każdym z podzbiorów wybierzemy dokładnie jeden element. Element ten będzie reprezentantem danego podzbioru.

obrazek

Na powyższym rysunku widzimy cztery rozłączne zbiory. W każdym ze zbiorów jeden element jest reprezentantem i oznaczyliśmy go kolorem czerwonym. Teraz możemy powiedzieć, że są to zbiory H, K, L i E. Zbiór H jest reprezentowany przez element H, zbiór K reprezentuje element K, itd.

W strukturze zbiorów rozłącznych definiuje się zwykle dwie operacje:

Find ( x ) – zwraca reprezentanta podzbioru, do którego należy element x. Np. w naszym przykładzie Find ( G ) = K, Find ( F ) = L, itd. Operacja ta pozwala określić przynależność elementu x do jednego z podzbiorów struktury.
Union ( x, y ) – łączy ze sobą podzbiory zawierające elementy x i y w jeden nowy podzbiór. Reprezentantem nowego podzbioru staje się jeden z reprezentantów poprzednich podzbiorów zawierających x lub y. Np. Union ( C, A ) tworzy podzbiór:

obrazek

Strukturę zbiorów rozłącznych można prosto zrealizować w postaci dwóch tablic o tym samym rozmiarze. W jednej tablicy przechowujemy elementy. W drugiej tablicy przechowujemy reprezentantów podzbiorów, zawierających poszczególne elementy. Nazwijmy te tablice odpowiednio E (elementy) i R (reprezentanci ). W naszym przykładzie tablice te posiadają następującą zawartość:

Tablica E
indeks	zawartość
0	A
1	B
2	C
3	D
4	E
5	F
6	G
7	H
8	I
9	J
10	K
11	L

Tablica R
indeks	zawartość
0	L
1	H
2	H
3	E
4	E
5	L
6	K
7	H
8	K
9	L
10	K
11	L

Operacja Find otrzymuje indeks elementu w tablicy E i zwraca element o tym indeksie z tablicy R. Wykonywana jest zatem w czasie stałym O ( 1 ).

Operacja Union jest tutaj bardziej skomplikowana. Otrzymuje ona indeksy elementów x i y w tablicy E. Najpierw Union musi sprawdzić, czy oba elementy należą do różnych podzbiorów. W tym celu wykonuje Find ( x ) i Find ( y ), zapamiętując wyniki w rx i ry. Jeśli rx i ry są różnymi reprezentantami, to Union musi połączyć reprezentowane przez nie podzbiory w jeden podzbiór, który będzie zawierał elementy z obu podzbiorów. Operacja ta polega na przypisaniu wszystkim elementom podzbioru ry reprezentanta rx (lub na odwrót ). Wymaga to przeglądnięcia całej tablicy R i zamienienia wszystkich elementów ry na rx. Otrzymujemy złożoność liniową O ( n ).

Jeśli elementy tworzą spójny zbiór wartości, to można uprościć strukturę zbiorów rozłącznych do jednej tablicy R. W takim przypadku indeksy odpowiadają bezpośrednio elementom zbioru, a zawartości komórek odpowiadają reprezentantom (indeksom elementów, które są reprezentantami ). Zamieńmy w naszym przykładzie literki na numery elementów od 0 do 11. Otrzymamy:

Tablica R
indeks	zawartość
0	11
1	7
2	7
3	4
4	4
5	11
6	10
7	7
8	10
9	11
10	10
11	11

Operacja Find dla danego elementu (indeksu) zwraca zawartość komórki tablicy R o tym indeksie, czyli zwraca reprezentanta podzbioru, który zawiera dany element. Np. Find ( 6 ) = 10, czyli element nr 6 znajduje się w podzbiorze o reprezentancie 10.

Operacja Union ( x, y ) najpierw zapamiętuje w zmiennych rx i ry odpowiednio komórki R [ x ] i R [ y ]. Jeśli rx i ry są różne, to elementy x i y leżą w rozłącznych podzbiorach. W takim razie Union zastępuje w tablicy R wszystkie wystąpienia ry przez rx (lub na odwrót, wg uznania lub potrzeb ).

Na samym początku korzystania ze struktury zbiorów rozłącznych tablicę R należy odpowiednio zainicjować. W tym przypadku wystarczy wprowadzić do jej komórek ich indeksy. Będzie to odpowiadało utworzeniu n rozłącznych zbiorów jednoelementowych:

Tablica R
indeks	zawartość
0	0
1	1
2	2
3	3
4	4
5	5
6	6
7	7
8	8
9	9
10	10
11	11

Algorytmy obsługi struktury zbiorów rozłącznych w zrealizowanej w tablicy

Find ( R, x )

Wejście:

R	–	tablica reprezentantów.
x	–	element zbioru, indeks w tablicy R. x ∈ C.

Wyjście:

Reprezentant podzbioru, w którym znajduje się element x.

Lista kroków

K01:	Zakończ z wynikiem R [ x ] .

Algorytm Union ( R, n, x, y )

Wejście:

R	–	tablica reprezentantów.
n	–	liczba elementów, n ∈ C.
x, y	–	elementy zbiorów, indeksy w tablicy R. x, y ∈ C.

Wyjście:

W tablicy R zostają połączone w jeden zbiór zbiory zawierające elementy x i y.

Elementy pomocnicze

rx, ry	–	reprezentanci podzbiorów, w których znajdują się elementy x i y. rx, ry ∈ C.
i	–	indeks, i ∈ C.

Lista kroków

K01:	rx ← R [ x ]	znajdujemy reprezentanta zbioru, który zawiera element x
K02:	ry ← R [ y ]	znajdujemy reprezentanta zbioru, który zawiera element y
K03:	Jeśli rx = ry, to zakończ	elementy x i y muszą być w rozłącznych zbiorach
K04:	Dla i = 0, 1, ..., n - 1: wykonuj: Jeśli R [ i ] = ry, to R [ i ] ← rx	zastępujemy reprezentanta ry przez rx dla wszystkich elementów
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 tablicę R 10-cio elementową, inicjuje ją, a następnie losuje 10 razy pary elementów. Dla wylosowanych elementów wykonywana jest operacja Union, co powoduje połączenie zbiorów, które te elementy zawierają. 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: 25.03.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program DSStruct;

const N = 10;                     // Liczba elementów

var
  R : array [ 0..N-1 ] of integer;

// Łączy dwa podzbiory w jeden
//----------------------------
procedure Union ( x, y : integer );
var
  rx, ry, i : integer;
begin
  rx := R [ x ];                  // Wyznaczamy reprezentanta zbioru zawierającego x
  ry := R [ y ];                  // i reprezentanta zbioru zawierającego y
  if rx <> ry then                // Łączenie wymaga różnych zbiorów
    for i := 0 to N-1 do          // Przeglądamy kolejne elementy tablicy R
      if R [ i ] = ry then R [ i ] := rx; // i zastępujemy w nich reprezentanta ry przez rx
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************
var
  i, j, x, y, c : integer;
begin
  Randomize;                      // Inicjujemy generator pseudolosowy
  for i := 0 to N - 1 do
    R [ i ] := i;                 // Ustawiamy tablicę R
  for i := 1 to N do
  begin
    x := random ( N );            // Generujemy losowe x i y
    y := random ( N );
    Union ( x, y );               // Łączymy zbiory
  end;

  c := 0;                         // Licznik podzbiorów w R

  // Wyświetlamy wyniki

  for i := 0 to N - 1 do
  begin
    if R [ i ] = i then inc (c);  // Zliczamy reprezentantów
    writeln ( i, ' is in set ', R [ i ] );
  end;
  writeln;
  writeln ( 'Number of sets = ', c );
  writeln;
  for i := 0 to N - 1 do
    if R [ i ] = i then
    begin
      write ( 'Set ', i, ' : ' );
      for j := 0 to N - 1 do
        if R [ j ] = i then write ( j, ' ' );
      writeln;
    end;
  writeln;
end.

C++

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

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

using namespace std;

const int N = 10;                 // Liczba elementów

int R [ N ];

// Łączy dwa podzbiory w jeden
//----------------------------
void Union ( int x, int y )
{
  int rx, ry, i;

  rx = R [ x ];                   // Wyznaczamy reprezentanta zbioru zawierającego x
  ry = R [ y ];                   // i reprezentanta zbioru zawierającego y
  if( rx != ry )                  // Łączenie wymaga różnych zbiorów
    for( i = 0; i < N; i++ )      // Przeglądamy kolejne elementy tablicy R
      if( R [ i ] == ry ) R [ i ] = rx; // i zastępujemy w nich reprezentanta ry przez rx
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************
int main( )
{
  int i, j, x, y, c;

  srand ( time ( NULL ) );        // Inicjujemy generator pseudolosowy
  for( i = 0; i < N; i++ )
    R [ i ] = i;                  // Ustawiamy tablicę R
  for( i = 0; i < N; i++ )
  {
    x = rand( ) % N;              // Generujemy losowe x i y
    y = rand( ) % N;
    Union ( x, y );               // Łączymy zbiory
  }

  c = 0;                          // Licznik podzbiorów w R

  // Wyświetlamy wyniki

  for( i = 0; i < N; i++ )
  {
    if( R [ i ] == i ) c++;         // Zliczamy reprezentantów
    cout << i << " is in set " << R [ i ] << endl;
  }

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

  for( i = 0; i < N; i++ )
    if( R [ i ] == i )
    {
      cout << "Set " << i << ": ";
      for( j = 0; j < N; j++ )
        if( R [ j ] == i ) cout << j << " ";
      cout << endl;
    }
  cout << endl;

  return 0;

}

Basic

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

const N = 10                      ' Liczba elementów

Dim Shared As Integer R ( 0 To N - 1 )

' Łączy dwa podzbiory w jeden
'----------------------------
sub UnionSets ( ByVal x As Integer, ByVal y As Integer )

  Dim As integer rx, ry, i

  rx = R ( x )                    ' Wyznaczamy reprezentanta zbioru zawierającego x
  ry = R ( y )                    ' i reprezentanta zbioru zawierającego y
  If rx <> ry Then                ' Łączenie wymaga różnych zbiorów
    For i = 0 To N - 1            ' Przeglądamy kolejne elementy tablicy R
      If R ( i ) = ry Then R ( i ) = rx ' i zastępujemy w nich reprezentanta ry przez rx
    Next
  End If
End Sub

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

dim As Integer i, j, x, y, c

Randomize                         ' Inicjujemy generator pseudolosowy

For i = 0 To N - 1
  R ( i ) = i                     ' Ustawiamy tablicę R
Next

For i = 0 To N - 1
  x = Int ( Rnd * N )             ' Generujemy losowe x i y
  y = Int ( Rnd * N )
  UnionSets ( x, y )              ' Łączymy zbiory
Next

c = 0                             ' Licznik podzbiorów w R

' Wyświetlamy wyniki

For i = 0 To N - 1
  If R ( i ) = i Then c += 1      ' Zliczamy reprezentantów
  Print i;" is in set ";R ( i )
Next

Print
Print "Number of sets =";c
Print

For i = 0 To N - 1
  If R ( i ) = i Then
    Print "Set";i;":";
    For j = 0 To N - 1
      if R ( j ) = i Then Print j;
    Next
    Print
  End If
Next

Print

End

Wynik:

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

Number of sets = 4

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

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 w tablicy

Problem

Rozwiązanie

Algorytmy obsługi struktury zbiorów rozłącznych w zrealizowanej w tablicy

Find ( R, x )

Wejście:

Wyjście:

Lista kroków

Algorytm Union ( R, n, x, y )

Wejście:

Wyjście:

Elementy pomocnicze

Lista kroków

Przykładowe programy