Zbiory rozłączne – implementacja w tablicy


Tematy pokrewne
Tablice – wektory
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem
Zliczanie wg kryterium
Wyszukiwanie max lub min
Jednoczesne wyszukiwanie max i min
Zastosowania wyszukiwania – sortowanie przez wybór
Wyszukiwanie najczęstszej wartości w zbiorze – dominanta
Wyszukiwanie lidera
Wyszukiwanie binarne
Wyszukiwanie interpolacyjne
Wyszukiwanie k-tego największego elementu
Wyszukiwanie szybkie k-tego największego elementu
Wyszukiwanie mediany zbioru
Zbiory rozłączne – implementacja w tablicy
Sumy prefiksowe
Wbudowane generatory liczb pseudolosowych
Zbiory rozłączne – implementacja listowa
Zbiory rozłączne – implementacja za pomocą drzew

Problem

Zaprojektować strukturę zbiorów rozłącznych opartą na tablicy.

 

 

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.

 

 

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 jest reprezentowany przez element H, zbiór K reprezentuje element K, itd.

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

  1. 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.
  2. 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:

 

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]  

 

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: rxR[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  

 

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

 

Lazarus
// 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.
Code::Blocks
// 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;

}
Free 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

 



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.