Algorytmy i Struktury Danych - Zbiory rozłączne

SPIS TREŚCI W KONSERWACJI

Tematy pomocnicze

Podrozdziały

Rozwiązanie nr 1
Rozwiązanie nr 2
Rozwiązanie nr 3

Problem

Należy zaprojektować strukturę danych dla zbiorów rozłącznych.

Struktura zbiorów rozłącznych (ang. disjoint sets structure) pozwala przechowywać informację o przynależności elementów do różnych zbiorów. Dwa zbiory są rozłączne, jeśli nie posiadają wspólnych elementów. Problem identyfikacji podzbioru rozwiązujemy w ten sposób, iż w każdym rozłącznym zbiorze wybieramy jeden z elementów i traktujemy go jako reprezentanta tego podzbioru.

Wyobraźmy sobie, że mamy trzy rozłączne zbiory, które zawierają elementy:

{1, 2, 7} {6, 8, 10} {3, 4} {0, 5, 9, 11}

W zbiorach tych wybieramy po jednym elemencie. W ten sposób określamy ich reprezentantów:

7 reprezentuje {1, 2, 7}
10 reprezentuje {6, 8, 10}
4 reprezentuje {3, 4}
11 reprezentuje {0, 5, 9, 11}

Określmy teraz trzy podstawowe operacje:

MakeSet (x)

Tworzy nowy, rozłączny zbiór, umieszcza w nim element x i czyni go reprezentantem tego zbioru. Element x nie może należeć do żadnego innego zbioru w tej kolekcji.

FindSet (x)

Zwraca reprezentanta zbioru, do którego należy element x. W naszym przykładzie Find-Set (9) = 11.

UnionSets (x, y)

Łączy w jeden zbiór zbiory, do których należą elementy x i y. Reprezentantem nowego zbioru staje się jeden z reprezentantów łączonych zbiorów. Zwykle przyjmuje się, że będzie to reprezentant zbioru bardziej licznego.

Strukturę zbiorów rozłącznych można w dosyć prosty sposób zrealizować za pomocą odpowiednio zmodyfikowanych list.

Pierwsze rozwiązanie jest bardzo prymitywne, lecz łatwe do zrozumienia. Poszczególne zbiory będziemy realizować za pomocą list dwukierunkowych. Elementy zbiorów będą jednocześnie elementami list. Dostęp do tych list będzie się odbywał za pomocą ich elementów, a nie przy pomocy dodatkowych wskaźników head i tail, zatem adresy tych elementów muszą być w jakiś sposób pamiętane przez aplikację.

obrazek

MakeSet (x)

Tworzy jednoelementową listę zawierającą x.

FindSet (x)

Przebiega listę z elementem x w kierunku jej początku i zwraca adres pierwszego elementu, czyli reprezentanta zbioru

UnionSets (x, y)

Łączy w jedną listę listy zawierające element x i y.

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

MakeSet (x)

Wejście:

wskazanie elementu listy dwukierunkowej

Wyjście:

Utworzenie jednoelementowej listy z elementem x.

Lista kroków:

K01:	(x→next) ← nil	;zerujemy pola następnika i poprzednika
K02:	(x→prev) ← nil
K03:	Zakończ

FindSet (x)

Wejście:

wskazanie elementu listy dwukierunkowej

Wyjście:

Wskazanie reprezentanta zbioru, do którego należy element x.

Zmienne pomocnicze:

wskaźnik elementów listy dwukierunkowej

Lista kroków:

K01:	p ← x
K02:	Dopóki (p→prev) ≠ nil, wykonuj p ← (p→prev)	idziemy w kierunku początku listy
K03:	Zakończ z wynikiem p	zwracamy adres początku listy, czyli adres reprezentanta

UnionSets (x, y)

Wejście:

x, y

wskazanie elementów listy dwukierunkowej

Wyjście:

Łączy w jedną listę listy zawierające element x i y.

Zmienne pomocnicze:

rx, ry, p

wskaźniki elementów listy dwukierunkowej

Lista kroków:

K01:	rx ← FindSet (x)	odnajdujemy reprezentanta zbioru z elementem x
K02:	ry ← FindSet (y)	odnajdujemy reprezentanta zbioru z elementem y
K03:	Jeśli rx = ry, to zakończ	kończymy, jeśli zbiory nie są rozłączne
K04:	p ← x
K05:	Dopóki (p→next) ≠ nil, wykonuj p ← (p→next)	szukamy ostatniego elementu listy zawierającej x
K06:	(p→next) ← ry	początek listy z y dołączamy na koniec listy z x
K07:	(ry→prev) ← p
K08:	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 elementów, umieszcza je w zbiorach jednoelementowych, a następnie losuje 10 razy pary elementów. Dla wylosowanych elementów wykonywana jest operacja UnionSets, 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 : 28.03.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------

const N = 10;                     // Liczba elementów

// Element listy dwukierunkowej
type
  PdlistEl = ^dlistEl;
  dlistEl =  record
    next  : PdlistEl;
    prev  : PdlistEl;
    data  : integer;
  end;

// Tworzy jednoelementową listę
//-----------------------------
procedure MakeSet (x : PdlistEl);
begin
  x^.next := nil;
  x^.prev := nil;
end;

// Zwraca pierwszy element listy
//------------------------------
function FindSet (x : PdlistEl) : PdlistEl;
var
  p : PdlistEl;
begin
  p := x;
  while p^.prev <> nil do p := p^.prev;
  FindSet := p;
end;

// Łączy dwie listy w jedną
//-------------------------
procedure UnionSets (x, y : PdlistEl);
var
  rx, ry, p : PdlistEl;
begin
  rx := FindSet (x);
  ry := FindSet (y);
  if rx <> ry then
  begin
    p := x;
    while p^.next <> nil do p := p^.next;
    p^.next  := ry;
    ry^.prev := p;
  end;
end;

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

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

  for i := 0 to N - 1 do
  begin
    Z [i].data := i;          // Elementy numerujemy kolejno
    MakeSet (addr (Z [i]));     // i tworzymy z nich zbiory
  end;

  for i := 1 to N do
  begin
    x := random (N);          // Losujemy dwa elementy
    y := random (N);
    UnionSets (addr (Z [x]), addr (Z [y]));
  end;

  // Wypisujemy wyniki

  c := 0;
  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, ' : ');
      while p <> nil do
      begin
        write (p^.data, ' ');
        p := p^.next;
      end;
      writeln;
    end;
  end;
end.

C++

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

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

using namespace std;

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

// Element listy dwukierunkowej

struct dlistEl
{
  dlistEl *next, *prev;
  int data;
};

// Tworzy jednoelementową listę
//-----------------------------
void MakeSet (dlistEl *x)
{
  x->next = x->prev = NULL;
}

// Zwraca pierwszy element listy
//------------------------------
dlistEl * FindSet (dlistEl *x)
{
  dlistEl * p;

  for(p = x; p->prev; p = p->prev);

  return p;
}

// Łączy dwie listy w jedną
//-------------------------
void UnionSets (dlistEl *x, dlistEl *y)
{
  dlistEl *rx, *ry, *p;

  rx = FindSet (x);
  ry = FindSet (y);
  if(rx != ry)
  {
    for(p = x; p->next; p = p->next);
    p->next  = ry;
    ry->prev = p;
  }
}

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

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

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

  for(i = 0; i < N; i++)
  {
    Z [i].data = i;             // Elementy numerujemy kolejno
    MakeSet (&Z [i]);            // i tworzymy z nich zbiory
  }

  for(i = 0; i < N; i++)
  {
    x = rand() % N;               // Losujemy dwa elementy
    y = rand() % N;
    UnionSets (&Z [x], &Z [y]);
  }

  // Wypisujemy wyniki

  c = 0;
  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 << ": ";
      while(p)
      {
        cout << p->data << " ";
        p = p->next;
      }
      cout << endl;
    }
  }

  return 0;
}

Basic

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

const N = 10                      ' Liczba elementów

' Element listy dwukierunkowej

Type dlistEl
  Next As dlistEl Ptr
  prev As dlistEl Ptr
  Data As Integer
End Type

' Tworzy jednoelementową listę
'-----------------------------
Sub MakeSet (ByVal x As dlistEl Ptr)
  x->next = 0
  x->prev = 0
End Sub

' Zwraca pierwszy element listy
'------------------------------
Function FindSet (ByVal x As dlistEl Ptr) As dlistEl Ptr
 
  Dim As dlistEl Ptr p

  p = x
  While p->prev
    p = p->prev
  Wend

  Return p
 
End Function

' Łączy dwie listy w jedną
'-------------------------
Sub UnionSets (ByVal x As dlistEl Ptr, ByVal y As dlistEl Ptr)
 
  Dim As dlistEl Ptr rx, ry, p

  rx = FindSet (x)
  ry = FindSet (y)
  If rx <> ry Then
    p = x
    While p->Next
    	p = p->Next
    Wend
    p->next  = ry
    ry->prev = p
  End If
End Sub

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

Dim As dlistEl Z (0 To N-1)
Dim As dlistEl Ptr p
Dim As Integer i, x, y, c

Randomize                       ' Inicjujemy generator pseudolosowy

For i = 0 To N - 1
  Z (i).data = i                 ' Elementy numerujemy kolejno
  MakeSet (VarPtr (Z (i)))         ' i tworzymy z nich zbiory
Next

For i = 0 To N - 1
  x = Int (Rnd * N)              ' Losujemy dwa elementy
  y = Int (Rnd * N)
  UnionSets (VarPtr (Z (x)), VarPtr (Z (y)))
Next

' Wypisujemy wyniki

c = 0
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;":";
    While p
      Print p->Data;
      p = p->Next
    Wend
    Print
  End If
Next

End

Wynik:

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

Numeber of sets = 3

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

Na początek: podrozdziału strony

Zmieniając nieznacznie budowę list, możemy znacząco przyspieszyć niektóre operacje wykonywane na strukturze zbiorów rozłącznych. Opisana wcześniej operacja FindSet ma złożoność klasy O (n), ponieważ musi przechodzić przez kolejne elementy listy aż do jej początku. Wadę tę możemy prosto wyeliminować, umieszczając w polu prev nie adres poprzedniego elementu, lecz adres początku listy. Teraz znalezienie reprezentanta będzie miało klasę złożoności O (1). Jednakże komplikuje to operację UnionSets, ponieważ w dołączanej na końcu liście należy zastąpić w każdym elemencie adres w polu prev nowym adresem reprezentanta zbioru.

obrazek

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

MakeSet (x)

Wejście:

wskazanie elementu listy dwukierunkowej

Wyjście:

Utworzenie jednoelementowej listy z elementem x.

Lista kroków:

K01:	(x→next) ← nil	pole następnika zerujemy
K02:	(x→prev) ← x	pole poprzednika wskazuje reprezentanta, czyli x
K03:	Zakończ

FindSet (x)

Wejście:

wskazanie elementu listy dwukierunkowej

Wyjście:

Wskazanie reprezentanta zbioru, do którego należy element x.

Lista kroków:

K01:

Zakończ z wynikiem (x→prev)

zwracamy adres początku listy, czyli adres reprezentanta

UnionSets (x, y)

Wejście:

x, y

wskazanie elementów listy dwukierunkowej

Wyjście:

Łączy w jedną listę listy zawierające element x i y.

Zmienne pomocnicze:

rx, ry, p

wskaźniki elementów listy dwukierunkowej

Lista kroków:

K01:	rx ← (x→prev)	odnajdujemy reprezentanta zbioru z elementem x
K02:	ry ← (y→prev)	odnajdujemy reprezentanta zbioru z elementem y
K03:	Jeśli rx = ry, to zakończ	kończymy, jeśli zbiory nie są rozłączne
K04:	p ← x
K05:	Dopóki (p→next) ≠ nil, wykonuj p ← (p→next)	szukamy ostatniego elementu listy zawierającej x
K06:	(p→next) ← ry	początek listy z y dołączamy na koniec listy z x
K07:	(ry→prev) ← p
K08:	p ← (p→next)	przechodzimy do następnego elementu listy
K09:	Jeśli p = nil, to zakończ	koniec listy?
K10:	(p→prev) ← rx	w dołączonej liście zastępujemy reprezentanta adresem rx
K11:	Idź do K08

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.

Pascal

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

const N = 10;                     // Liczba elementów

// Element listy dwukierunkowej
type
  PdlistEl = ^dlistEl;
  dlistEl =  record
    next  : PdlistEl;
    prev  : PdlistEl;
    data  : integer;
  end;

// Tworzy jednoelementową listę
//-----------------------------
procedure MakeSet (x : PdlistEl);
begin
  x^.next := nil;
  x^.prev := x;
end;

// Zwraca pierwszy element listy
//------------------------------
function FindSet (x : PdlistEl) : PdlistEl;
begin
  FindSet := x^.prev;
end;

// Łączy dwie listy w jedną
//-------------------------
procedure UnionSets (x, y : PdlistEl);
var
  rx, ry, p : PdlistEl;
begin
  rx := x^.prev;
  ry := y^.prev;
  if rx <> ry then
  begin
    p := x;
    while p^.next <> nil do p := p^.next;
    p^.next  := ry;
    ry^.prev := p;
    while true do
    begin
      p := p^.next;
      if p = nil then break;
      p^.prev := rx;
    end;
  end;
end;

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

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

  for i := 0 to N - 1 do
  begin
    Z [i].data := i;          // Elementy numerujemy kolejno
    MakeSet (addr (Z [i]));     // i tworzymy z nich zbiory
  end;

  for i := 1 to 10 do
  begin
    x := random (N);          // Losujemy dwa elementy
    y := random (N);
    UnionSets (addr (Z [x]), addr (Z [y]));
  end;

  // Wypisujemy wyniki

  c := 0;
  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, ' : ');
      while p <> nil do
      begin
        write (p^.data, ' ');
        p := p^.next;
      end;
      writeln;
    end;
  end;
end.

C++

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

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

using namespace std;

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

// Element listy dwukierunkowej

struct dlistEl
{
  dlistEl *next, *prev;
  int data;
};

// Tworzy jednoelementową listę
//-----------------------------
void MakeSet (dlistEl *x)
{
  x->next = NULL;
  x->prev = x;
}

// Zwraca pierwszy element listy
//------------------------------
dlistEl * FindSet (dlistEl *x)
{
  return x->prev;
}

// Łączy dwie listy w jedną
//-------------------------
void UnionSets (dlistEl *x, dlistEl *y)
{
  dlistEl *rx, *ry, *p;

  rx = x->prev;
  ry = y->prev;
  if(rx != ry)
  {
    for(p = x; p->next; p = p->next);
    p->next  = ry;
    ry->prev = p;
    while((p = p->next)) p->prev = rx;
  }
}

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

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

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

  for(i = 0; i < N; i++)
  {
    Z [i].data = i;               // Elementy numerujemy kolejno
    MakeSet (&Z [i]);              // i tworzymy z nich zbiory
  }

  for(i = 0; i < N; i++)
  {
    x = rand() % N;             // Losujemy dwa elementy
    y = rand() % N;
    UnionSets (&Z [x], &Z [y]);
  }

  // Wypisujemy wyniki

  c = 0;
  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 << ": ";
      while(p)
      {
        cout << p->data << " ";
        p = p->next;
      }
      cout << endl;
    }
  }

  return 0;
}

Basic

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

const N = 10                      ' Liczba elementów

' Element listy dwukierunkowej

Type dlistEl
  Next As dlistEl Ptr
  prev As dlistEl Ptr
  Data As Integer
End Type

' Tworzy jednoelementową listę
'-----------------------------
Sub MakeSet (ByVal x As dlistEl Ptr)
  x->next = 0
  x->prev = x
End Sub

' Zwraca pierwszy element listy
'------------------------------
Function FindSet (ByVal x As dlistEl Ptr) As dlistEl Ptr
 
  Return x->prev
 
End Function

' Łączy dwie listy w jedną
'-------------------------
Sub UnionSets (ByVal x As dlistEl Ptr, ByVal y As dlistEl Ptr)
 
  Dim As dlistEl Ptr rx, ry, p

  rx = x->prev
  ry = y->prev
  If rx <> ry Then
    p = x
    While p->Next
    	p = p->Next
    Wend
    p->next  = ry
    ry->prev = p
    While 1
    	p = p->Next
    	If p = 0 Then Exit While
    	p->prev = rx
    Wend
  End If
End Sub

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

Dim As dlistEl Z (0 To N-1)
Dim As dlistEl Ptr p
Dim As Integer i, x, y, c

Randomize                        ' Inicjujemy generator pseudolosowy

For i = 0 To N - 1
  Z (i).data = i               ' Elementy numerujemy kolejno
  MakeSet (VarPtr (Z (i))) ' i tworzymy z nich zbiory
Next

For i = 0 To N - 1
  x = Int (Rnd * N)              ' Losujemy dwa elementy
  y = Int (Rnd * N)
  UnionSets (VarPtr (Z (x)), VarPtr (Z (y)))
Next

' Wypisujemy wyniki

c = 0
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;":";
    While p
      Print p->Data;
      p = p->Next
    Wend
    Print
  End If
Next

End

Wynik:

Na początek: podrozdziału strony

Kolejne ulepszenie ma na celu przyspieszenie operacji UnionSets. W tym celu zmieniamy budowę użytych list, tak aby każdy element wskazywał poprzez pole prev na strukturę dlistVar, w której przechowujemy adres początku listy (reprezentant zbioru), adres ostatniego elementu na liście oraz liczbę elementów listy. Operacja UnionSets korzysta z tych pól przy łączeniu list. Zawsze dołączana jest lista krótsza do dłuższej. Dzięki temu minimalizujemy liczbę uaktualnień elementów w dołączanej liście.

obrazek

Algorytmy dla struktury zbiorów rozłącznych zrealizowanej za pomocą list dwukierunkowych – wersja 3

MakeSet (x)

Wejście:

wskazanie elementu listy dwukierunkowej

Wyjście:

Utworzenie jednoelementowej listy z elementem x. Tworzona jest również struktura dlistVar.

Zmienne pomocnicze:

wskaźnik struktury dlistVar

Lista kroków:

K01:	Utwórz nową strukturę dlistVar i umieść jej adres w p
K02:	(p→head) ← x	początkiem listy jest x
K03:	(p→tail) ← x	końcem listy jest też x
K04:	(p→count) ← 1	lista zawiera 1 element
K05:	(x→next) ← nil
K06:	(x→prev) ← p	pole prev wskazuje na strukturę dlistVar
K07:	Zakończ

FindSet (x)

Wejście:

wskazanie elementu listy dwukierunkowej

Wyjście:

Wskazanie struktury dlistVar zbioru, do którego należy element x.

Lista kroków:

K01:

Zakończ z wynikiem (x→prev→head)

zwracamy adres początku listy, czyli adres reprezentanta

UnionSets (x, y)

Wejście:

x, y

wskazanie elementów listy dwukierunkowej

Wyjście:

Łączy w jedną listę listy zawierające element x i y.

Zmienne pomocnicze:

rx, ry	:	wskaźniki struktur dlistVar
p	:	wskaźnik elementów listy dwukierunkowej

Lista kroków:

K01:	rx ← (x→prev)	odnajdujemy struktury dlistVar dla listy z x
K02:	ry ← (y→prev)	odnajdujemy struktury dlistVar dla listy z y
K03:	Jeśli rx = ry, to zakończ	kończymy, jeśli jest to ta sama lista
K04:	Jeśli (rx→count) < (ry→count), to rx ↔ ry	rx - lista główna, ry - lista dodawana
K05:	(rx→tail→next) ← (ry→head)	listę ry dołączamy na koniec rx
K06:	(rx→tail) ← ( ry→tail)	koniec listy rx jest końcem listy ry
K07:	(rx→count) ← ( rx→count) + (ry→count)	obliczamy nową długość
K08:	p ← (ry→head)	przechodzimy przez listę ry i modyfikujemy pola prev
K09:	Dopóki p <> nil, wykonuj kroki K10…K11
K10:	(p→prev) ← rx	modyfikujemy pole prev elementów ry
K11:	p ← ( p→next)	idziemy do następnego elementu
K12:	Usuń z pamięci ry	usuwamy zbędną już strukturę dlistVar
K13:	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.

Pascal

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

const N = 10;                     // Liczba elementów

// Elementy listy dwukierunkowej
type
  PdlistVar = ^dlistVar;
  PdlistEl = ^dlistEl;
  dlistEl =  record
    next  : PdlistEl;
    prev  : PdlistVar;
    data  : integer;
  end;

  dlistVar = record
    head  : PdlistEl;
    tail  : PdlistEl;
    count : cardinal;
  end;

// Tworzy jednoelementową listę
//-----------------------------
procedure MakeSet (x : PdlistEl);
var
  p : PdlistVar;
begin
  new (p);      // Tworzymy nową strukturę dlistVar
  p^.head  := x;  // Inicjujemy jej pola
  p^.tail  := x;
  p^.count := 1;
  x^.next := nil;
  x^.prev := p;   // Adres struktury dlistVar zapamiętujemy w x
end;

// Zwraca pierwszy element listy
//------------------------------
function FindSet (x : PdlistEl) : PdlistEl;
begin
  FindSet := x^.prev^.head; // Zwracamy adres reprezentanta
end;

// Łączy dwie listy w jedną
//-------------------------
procedure UnionSets (x, y : PdlistEl);
var
  rx, ry : PdlistVar;
  p     : PdlistEl;
begin
  rx := x^.prev;            // Zapamiętujemy adresy struktur dlistVar
  ry := y^.prev;
  if rx <> ry then          // Struktury muszą być różne
  begin
    if rx^.count < ry^.count then // Ustawiamy rx - lista dłuższa, ry - krótsza
    begin
      rx := ry;
      ry := x^.prev;
    end;
    rx^.tail^.next := ry^.head;   // Listę ry dołączamy na koniec listy rx
    rx^.tail := ry^.tail;         // Koniec listy rx będzie końcem listy ry
    inc (rx^.count, ry^.count);     // Modyfikujemy licznik elementów
    p := ry^.head;                // Na liście ry modyfikujemy pola prev
    while p <> nil do
    begin
      p^.prev := rx;              // Teraz będą wskazywały strukturę listy rx
      p := p^.next;               // Następny element na liście
    end;
    dispose (ry);               // Usuwamy z pamięci zbędną strukturę dlistVar
  end;
end;

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

var
  Z : array [0..N-1] of dlistEl;
  i, x, y, c : integer;
  p : PdlistEl;
  r : PdlistVar;
begin
  Randomize; // Inicjujemy generator pseudolosowy

  for i := 0 to N - 1 do
  begin
    Z [i].data := i;            // Elementy numerujemy kolejno
    MakeSet (addr (Z [i])); // i tworzymy z nich zbiory
  end;

  for i := 1 to 10 do
  begin
    x := random (N);   // Losujemy dwa elementy
    y := random (N);
    UnionSets (addr (Z [x]), addr (Z [y]));
  end;

  // Wypisujemy wyniki

  c := 0;
  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, ' count = ', p^.prev^.count, ' : ');
      while p <> nil do
      begin
        write (p^.data, ' ');
        p := p^.next;
      end;
      writeln;
    end;
  end;

  // Usuwamy struktury dlistVar

  for i := 0 to N - 1 do
  begin
    r := Z [i].prev;               // Zapamiętujemy adres struktury dlistVar
    if r <> nil then              // Jeśli ta struktura istnieje,
    begin
      p := r^.head;               // to z listy usuwamy jej adres
      while p <> nil do
      begin
        p^.prev := nil;
        p := p^.next;
      end;
      dispose (r);                 // Usuwamy strukturę z pamięci
    end;
  end;
end.

C++

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

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

using namespace std;

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

// Elementy listy dwukierunkowej

struct dlistEl
{
  struct dlistEl  *next;
  struct dlistVar *prev;
  int data;
};

struct dlistVar
{
  struct dlistEl *head;
  struct dlistEl *tail;
  unsigned count;
};

// Tworzy jednoelementową listę
//-----------------------------
void MakeSet (dlistEl *x)
{
  dlistVar *p;

  p = new dlistVar;             // Tworzymy nową strukturę dlistVar
  p->head  = x;                 // Inicjujemy jej pola
  p->tail  = x;
  p->count = 1;
  x->next  = NULL;
  x->prev  = p;                 // Adres struktury dlistVar zapamiętujemy w x
}

// Zwraca pierwszy element listy
//------------------------------
dlistEl * FindSet (dlistEl *x)
{
  return x->prev->head;         // Zwracamy adres reprezentanta
}

// Łączy dwie listy w jedną
//-------------------------
void UnionSets (dlistEl *x, dlistEl *y)
{
  dlistVar *rx, *ry;
  dlistEl *p;

  rx = x->prev;                 // Zapamiętujemy adresy struktur dlistVar
  ry = y->prev;
  if(rx != ry)                // Struktury muszą być różne
  {
    if(rx->count < ry->count) // Ustawiamy rx - lista dłuższa, ry - krótsza
    {
      rx = ry;
      ry = x->prev;
    }
    rx->tail->next = ry->head;  // Listę ry dołączamy na koniec listy rx
    rx->tail = ry->tail;        // Koniec listy rx będzie końcem listy ry
    rx->count += ry->count;     // Modyfikujemy licznik elementów

    for(p = ry->head; p; p = p->next) // Na liście ry modyfikujemy pola prev
      p->prev = rx;             // Teraz będą wskazywały strukturę listy rx

    delete ry;                  // Usuwamy z pamięci zbędną strukturę dlistVar
  }
}

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

int main()
{
  dlistEl Z [N], *p;
  int i, x, y, c;
  dlistVar *r;

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

  for(i = 0; i < N; i++)
  {
    Z [i].data = i;                // Elementy numerujemy kolejno
    MakeSet (&Z [i]);               // i tworzymy z nich zbiory
  }

  for(i = 0; i < N; i++)
  {
    x = rand() % N;               // Losujemy dwa elementy
    y = rand() % N;
    UnionSets (&Z [x], &Z [y]);
  }

  // Wypisujemy wyniki

  c = 0;
  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 << " count = " << p->prev->count << ": ";
      while(p)
      {
        cout << p->data << " ";
        p = p->next;
      }
      cout << endl;
    }
  }

  // Usuwamy struktury dlistVar

  for(i = 0; i < N; i++)
  {
    r = Z [i].prev;   // Zapamiętujemy adres struktury dlistVar
    if(r)             // Jeśli ta struktura istnieje,
    {
      for(p = r->head; p; p = p->next)
        p->prev = NULL; // to z listy usuwamy jej adres
      delete r;         // Usuwamy strukturę z pamięci
    }
  }

  return 0;
}

Basic

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

const N = 10                 ' Liczba elementów

' Elementy listy dwukierunkowej

Type dlistVarFwd As dlistVar ' Typ tymczasowy do rozwiązania referencji krzyżowej
Type dlistEl
  Next As dlistEl Ptr
  prev As dlistVarFwd Ptr    ' Referencja krzyżowa
  Data As Integer
End Type

Type dlistVar
  head As dlistEl Ptr
  tail  As dlistEl Ptr
  count As UInteger
End Type

' Tworzy jednoelementową listę
'-----------------------------
Sub MakeSet (ByVal x As dlistEl Ptr)

  Dim As dlistVar Ptr p

  p = new dlistVar ' Tworzymy nową strukturę dlistVar
  p->head  = x     ' Inicjujemy jej pola
  p->tail  = x
  p->count = 1
  x->next  = 0
  x->prev  = p     ' Adres struktury dlistVar zapamiętujemy w x

End Sub

' Zwraca pierwszy element listy
'------------------------------
Function FindSet (byval x As dlistEl Ptr) As dlistEl Ptr
  return x->prev->head ' Zwracamy adres reprezentanta
End Function

' Łączy dwie listy w jedną
'-------------------------
Sub UnionSets (ByVal x As dlistEl Ptr, ByVal y As dlistEl Ptr)
	
  Dim As dlistVar Ptr rx, ry
  Dim As dlistEl Ptr p

  rx = x->prev                    ' Zapamiętujemy adresy struktur dlistVar
  ry = y->prev
  If rx <> ry Then                ' Struktury muszą być różne
    If rx->count < ry->count Then ' Ustawiamy rx - lista dłuższa, ry - krótsza
      rx = ry
      ry = x->prev
    End If
    rx->tail->next = ry->head     ' Listę ry dołączamy na koniec listy rx
    rx->tail = ry->tail           ' Koniec listy rx będzie końcem listy ry
    rx->count += ry->count        ' Modyfikujemy licznik elementów

    p = ry->head                  ' Na liście ry modyfikujemy pola prev
    While p
      p->prev = rx                ' Teraz będą wskazywały strukturę listy rx
      p = p->Next
    Wend
    Delete ry                     ' Usuwamy z pamięci zbędną strukturę dlistVar
  End If
End Sub

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

Dim as dlistEl Z (0 To N - 1)
Dim As dlistEl Ptr p
Dim As Integer i, x, y, c
Dim As dlistVar Ptr r

Randomize                        ' Inicjujemy generator pseudolosowy

For i = 0 To N - 1
  Z (i).data = i               ' Elementy numerujemy kolejno
  MakeSet (VarPtr (Z (i))) ' i tworzymy z nich zbiory
Next

For i = 0 To N - 1
  x = Int (Rnd * N)                ' Losujemy dwa elementy
  y = Int (Rnd * N)
  UnionSets (VarPtr (Z (x)), VarPtr (Z (y)))
Next

' Wypisujemy wyniki

c = 0
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;" count = ";p->prev->count;":";
    While p
      Print p->data;
      p = p->Next
    Wend
    Print
  End If
Next

' Usuwamy struktury dlistVar

For i = 0 To N - 1
  r = Z (i).prev                   ' Zapamiętujemy adres struktury dlistVar
  If r Then                       ' Jeśli ta struktura istnieje,
    p = r->head
    While p
      p->prev = 0                 ' to z listy usuwamy jej adres
      p = p->Next                 ' Następny element listy
    Wend
    delete r                      ' Usuwamy strukturę z pamięci
  End If
Next

End

Wynik:

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

Numeber of sets = 4

Set 1 count = 2 : 1 4
Set 2 count = 1 : 2
Set 7 count = 1 : 7
Set 9 count = 6 : 9 8 0 3 5 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 listowa

Problem

Rozwiązanie nr 1

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

MakeSet (x)

Wejście:

Wyjście:

FindSet (x)

Wejście:

Wyjście:

Zmienne pomocnicze:

UnionSets (x, y)

Wejście:

Wyjście:

Zmienne pomocnicze:

Przykładowe programy

Rozwiązanie nr 2

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

MakeSet (x)

Wejście:

Wyjście:

FindSet (x)

Wejście:

Wyjście:

UnionSets (x, y)

Wejście:

Wyjście:

Zmienne pomocnicze:

Przykładowe programy

Rozwiązanie nr 3

Algorytmy dla struktury zbiorów rozłącznych zrealizowanej za pomocą list dwukierunkowych – wersja 3

MakeSet (x)

Wejście:

Wyjście:

Zmienne pomocnicze:

FindSet (x)

Wejście:

Wyjście:

UnionSets (x, y)

Wejście:

Wyjście:

Zmienne pomocnicze:

Przykładowe programy