Algorytmy i Struktury Danych - Zbiory rozłączne

SPIS TREŚCI

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 cztery 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:

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

find_set(x)

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

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

make_set(x)

Tworzy jednoelementową listę zawierającą x.

find_set(x)

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

union_sets(x, y)

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

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

make_set(x)

Wejście:

x : wskazanie elementu listy dwukierunkowej.

Wyjście:

Utworzenie jednoelementowej listy z elementem x.

Lista kroków:

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

find_set (x)

Wejście:

x : wskazanie elementu listy dwukierunkowej.

Wyjście:

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

Elementy pomocnicze:

p : wskaźnik elementów listy dwukierunkowej.

Lista kroków:

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

union_sets(x, y)

Wejście:

x, y : wskazanie elementów listy dwukierunkowej.

Wyjście:

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

Elementy pomocnicze:

rx, ry, p : wskaźniki elementów listy dwukierunkowej.

Lista kroków:

K01: rx ← find_set(x) ; odnajdujemy reprezentanta zbioru z elementem x
K02: ry ← find_set(y) ; odnajdujemy reprezentanta zbioru z elementem y
K03: Jeśli rx = ry, ; kończymy, jeśli zbiory nie są rozłączne
     to zakończ
K04: p ← x
K05: Dopóki p→next ≠ nil, ; szukamy ostatniego elementu listy zawierającej x
     wykonuj p ← p→next
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 union_sets, 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
  PDLel = ^DLel;
  DLel =  record
    next  : PDLel;
    prev  : PDLel;
    Data: integer;
  end;

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

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

// Łączy dwie listy w jedną
//-------------------------
procedure union_sets(x, y : PDLel);
var
  rx, ry, p : PDLel;
begin
  rx := find_set(x);
  ry := find_set(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 DLel;
  i, x, y, c : integer;
  p : PDLel;
begin
  Randomize;

  for i := 0 to N-1 do
  begin
    Z[i].Data:= i; // Elementy numerujemy kolejno
    make_set(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);
    union_sets(addr(Z[x]), addr(Z[y]));
  end;

  // Wypisujemy wyniki
  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, ' : ');
      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 DLel
{
  DLel *next, *prev;
  int data;
};

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

// Zwraca pierwszy element listy
//------------------------------
DLel * find_set(DLel *x)
{
  DLel * p;

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

  return p;
}

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

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

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

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

  srand(time(NULL));

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

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

  // Wypisujemy wyniki
  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 << ": ";
      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 DLel
  Next As DLel Ptr
  prev As DLel Ptr
  Data As Integer
End Type

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

' Zwraca pierwszy element listy
'------------------------------
Function find_set(ByVal x As DLel Ptr)_
                 As DLel Ptr
  
  Dim As DLel Ptr p

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

  Return p
  
End Function

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

  rx = find_set(x)
  ry = find_set(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 DLel Z(0 To N-1)
Dim As DLel Ptr p
Dim As Integer i, x, y, c

Randomize

For i = 0 To N-1
  Z(i).data = i ' Elementy numerujemy kolejno
  make_set(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)
  union_sets(VarPtr(Z(x)), VarPtr(Z(y)))
Next

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

Python (dodatek)

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

import random

N = 10 # Liczba elementów


# Klasa elementu listy dwukierunkowej
class DLel:


    def __init__(self, data):
        self.next = None
        self.prev = None
        self.data = data


# Tworzy jednoelementową listę
def make_set(x):
    x.next = None
    x.prev = None


# Zwraca pierwszy element listy
def find_set(x):
    p = x
    while p.prev: p = p.prev
    return p


# Łączy dwie listy w jedną
def union_sets(x, y):
    rx = find_set(x)
    ry = find_set(y)
    if rx is not ry:
        p = x
        while p.next: p = p.next
        p.next = ry
        ry.prev = p


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

z = [DLel(i) for i in range(N)]
for i in range(N):
    x = random.randrange(N)
    y = random.randrange(N)
    union_sets(z[x], z[y])
# Wypisujemy wyniki
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, ": ", sep="", end="")
        while p:
            print(p.data, end=" ")
            p = p.next
        print()

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

do podrozdziału do 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 find_set( ) ma klasę złożoności obliczeniowej 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ę union_sets( ), 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.

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

make_set(x)

Wejście:

x : wskazanie elementu listy dwukierunkowej, który będzie jej reprezentantem.

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

find_set(x)

Wejście:

x : 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

union_sets(x, y)

Wejście:

x, y : wskazanie elementów listy dwukierunkowej.

Wyjście:

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

Elementy 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, ; kończymy, jeśli zbiory nie są rozłączne
     to zakończ
K04: p ← x
K05: Dopóki p→next ≠ nil, ; szukamy ostatniego elementu listy
     wykonuj p ← p→next   ; zawierającej x
K06: p→next ← ry ; początek listy z y dołączamy na koniec listy z x
K07: p ← p→next ; przechodzimy do następnego elementu listy
K08: Jeśli p = nil, ; koniec listy?
     to zakończ
K09: p→prev ← rx ; w dołączonej liście zastępujemy reprezentanta
     ; adresem rx
K10: Idź do K07 ; i kontynuujemy pętlę

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 tablicy zbiorów jednoelementowych, a następnie losuje 10 razy pary elementów. Dla wylosowanych elementów wykonywana jest operacja union_sets( ), 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
  PDLel = ^DLel;
  DLel =  record
    next  : PDLel;
    prev  : PDLel;
    Data: integer;
  end;

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

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

// Łączy dwie listy w jedną
//-------------------------
procedure union_sets(x, y : PDLel);
var
  rx, ry, p : PDLel;
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;
    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 DLel;
  i, x, y, c : integer;
  p : PDLel;
begin
  Randomize;

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

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

  // Wypisujemy wyniki
  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, ' : ');
      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 DLel
{
  DLel *next, *prev;
  int data;
};

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

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

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

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

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

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

  srand (time(NULL));

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

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

  // Wypisujemy wyniki
  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 << ": ";
      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 DLel
  Next As DLel Ptr
  prev As DLel Ptr
  Data As Integer
End Type

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

' Zwraca pierwszy element listy
'------------------------------
Function find_set(ByVal x As DLel Ptr)_
                  As DLel Ptr
  Return x->prev
End Function

' Łączy dwie listy w jedną
'-------------------------
Sub union_sets(ByVal x As DLel Ptr, _
               ByVal y As DLel Ptr)
  Dim As DLel 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
    While 1
    	p = p->Next
    	If p = 0 Then Exit While
    	p->prev = rx
    Wend
  End If
End Sub

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

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

Randomize

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

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

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

Python (dodatek)

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

import random

N = 10 # Liczba elementów


# Klasa elementu listy dwukierunkowej
class DLel:


    # Konstruktor
    def __init__(self, data):
        self.next = None
        self.prev = self
        self.data = data


# Zwraca pierwszy element listy
def find_set(x):
    return x.prev


# Łączy dwie listy w jedną
def union_sets(x, y):
    rx = x.prev
    ry = y.prev
    if rx is not ry:
        p = x
        while p.next:
            p = p.next
        p.next = ry
        while p.next:
            p = p.next
            p.prev = rx


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

z = [DLel(i) for i in range(N)]
for i in range(N):
    x = random.randrange(N)
    y = random.randrange(N)
    union_sets(z[x], z[y])
# Wypisujemy wyniki
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, ": ", sep="", end="")
        while p:
            print(p.data, end=" ")
            p = p.next
        print()

Wynik:

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

Numeber of sets = 5

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

do podrozdziału do strony

Kolejne ulepszenie ma na celu przyspieszenie operacji union_sets( ). W tym celu zmieniamy budowę użytych list, tak aby każdy element wskazywał poprzez pole prev na strukturę DLvar, w której przechowujemy adres początku listy (reprezentant zbioru), adres ostatniego elementu na liście oraz liczbę elementów listy. Operacja union_sets( ) 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.

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

make_set(x)

Wejście:

x : wskazanie elementu listy dwukierunkowej.

Wyjście:

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

Elementy pomocnicze:

p : wskaźnik struktury DLvar.

Lista kroków:

K01: Utwórz nową strukturę DLvar
     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ę DLvar
K07: Zakończ

find_set(x)

Wejście:

x : wskazanie elementu listy dwukierunkowej.

Wyjście:

Wskazanie struktury DLvar 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

union_sets(x, y)

Wejście:

x, y : wskazanie elementów listy dwukierunkowej.

Wyjście:

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

Elementy pomocnicze:

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

Lista kroków:

K01: rx ← x→prev ; odnajdujemy struktury DLvar dla listy z x
K02: ry ← y→prev ; odnajdujemy struktury DLvar dla listy z y
K03: Jeśli rx = ry, ; kończymy, jeśli jest to ta sama lista
     to zakończ
K04: Jeśli rx→count < ry→count, ; rx-lista główna, 
     to rx ↔ ry ; 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ę DLvar
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.

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 union_sets( ), 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 wraz z liczbą ich elementów.

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
  PDLvar = ^DLvar;
  PDLel = ^DLel;
  DLel =  record
    next  : PDLel;
    prev  : PDLvar;
    Data: integer;
  end;

  DLvar = record
    head  : PDLel;
    tail  : PDLel;
    count : cardinal;
  end;

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

// Zwraca pierwszy element listy
//------------------------------
function find_set(x : PDLel) : PDLel;
begin
  find_set := x^.prev^.head;
end;

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

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

var
  Z : array [0..N-1] of DLel;
  i, x, y, c : integer;
  p : PDLel;
  r : PDLvar;
begin
  Randomize;
  for i := 0 to N-1 do
  begin
    // Elementy numerujemy kolejno
    Z[i].Data:= i;
    // i tworzymy z nich zbiory
    make_set(addr(Z[i]));
  end;
  for i := 1 to 10 do
  begin
    // Losujemy dwa elementy
    x := random(N);
    y := random(N);
    union_sets(addr(Z[x]), addr(Z[y]));
  end;
  // Wypisujemy wyniki
  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, ' count = ',
            p^.prev^.count, ' : ');
      while p <> nil do
      begin
        write(p^.data, ' ');
        p := p^.next;
      end;
      writeln;
    end;
  end;
  // Usuwamy struktury DLvar
  for i := 0 to N-1 do
  begin
    // Zapamiętujemy adres
    // struktury DLvar
    r := Z[i].prev;
    // Jeśli ta struktura istnieje,
    if r <> nil then
    begin
      // to z listy usuwamy jej adres
      p := r^.head;
      while p <> nil do
      begin
        p^.prev := nil;
        p := p^.next;
      end;
      // Usuwamy strukturę z pamięci
      dispose(r);
    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;

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

// Elementy listy dwukierunkowej
struct DLel
{
  struct DLel  *next;
  struct DLvar *prev;
  int data;
};

struct DLvar
{
  struct DLel *head;
  struct DLel *tail;
  unsigned count;
};

// Tworzy jednoelementową listę
//-----------------------------
void make_set(DLel *x)
{
  DLvar *p;

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

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

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

  // Zapamiętujemy adresy struktur DLvar
  rx = x->prev;
  ry = y->prev;
  // Struktury muszą być różne
  if(rx != ry)
  {
    // Ustawiamy rx-lista dłuższa,
    // ry-krótsza
    if(rx->count < ry->count)
    {
      rx = ry;
      ry = x->prev;
    }
    // Listę ry na koniec listy rx
    rx->tail->next = ry->head;
    // Koniec listy rx będzie
    // końcem listy ry
    rx->tail = ry->tail;
    // Modyfikujemy licznik elementów
    rx->count += ry->count;
    // Na liście ry modyfikujemy pola prev
    for(p = ry->head; p; p = p->next)
      // Teraz będą wskazywały
      // strukturę listy rx
      p->prev = rx;
    // Usuwamy z pamięci
    // zbędną strukturę DLvar
    delete ry;
  }
}

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

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

  srand (time(NULL));

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

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

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

  // Usuwamy struktury DLvar
  for(i = 0; i < N; i++)
  {
    // Zapamiętujemy adres struktury DLvar
    r = Z[i].prev;
    // Jeśli ta struktura istnieje,
    if(r)
    {
      for(p = r->head; p; p = p->next)
        // to z listy usuwamy jej adres
        p->prev = NULL;
      // Usuwamy strukturę z pamięci
      delete r;
    }
  }
  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: 06.06.2024
# (C)2024 mgr Jerzy Wałaszek
#------------------------------

import random

N = 10 # Liczba elementów


# Elementy listy dwukierunkowej
class DLel:


    def __init__(self, data):
        self.next = None
        self.prev = None
        self.data = data


# Klasa listy
class DLvar:


    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0


# Tworzy jednoelementową listę
def make_set(x):
      # Tworzymy nową strukturę DLvar
      p = DLvar()
      # Inicjujemy jej pola
      p.head  = x
      p.tail  = x
      p.count = 1
      x.next  = None
      # Adres struktury DLvar
      # zapamiętujemy w x.prev
      x.prev  = p


# Zwraca pierwszy element listy
def find_set(x):
    # Zwracamy adres reprezentanta
    return x.prev.head


# Łączy dwie listy w jedną
def union_sets(x, y):
    # Zapamiętujemy adresy
    # struktur DLvar
    rx = x.prev
    ry = y.prev
    # Struktury muszą być różne
    if rx is not ry:
        # Ustawiamy rx-lista dłuższa,
        # ry-krótsza
        if rx.count < ry.count:
            rx, ry = ry, rx
        # Listę ry na koniec listy rx
        rx.tail.next = ry.head
        # Koniec listy rx będzie
        # końcem listy ry
        rx.tail = ry.tail
        # Modyfikujemy licznik
        # elementów
        rx.count += ry.count
        # Na liście ry modyfikujemy
        # pola prev
        p = ry.head
        while p:
            # Teraz będą wskazywały
            # strukturę listy rx
            p.prev = rx
            p = p.next


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

z = [DLel(i) for i in range(N)]
for i in range(N):
    make_set(z[i])
for i in range(N):
    # Losujemy dwa elementy
    x = random.randrange(N)
    y = random.randrange(N)
    union_sets(z[x], z[y])
# Wypisujemy wyniki
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, " count = ",
              p.prev.count, ": ",
              sep = "", end = "")
        while p:
            print(p.data, end = " ")
            p = p.next
        print()
# Usuwamy struktury DLvar
for i in range(N):
    # Zapamiętujemy adres
    # struktury DLvar
    r = z[i].prev
    # Jeśli ta struktura istnieje,
    if r:
        p = r.head
        while p:
            # to z listy usuwamy
            # jej adres
            p.prev = None
            p = p.next
        # Usuwamy strukturę z pamięci
        r = None

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

do podrozdziału do 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

make_set(x)

find_set(x)

union_sets(x, y)

Rozwiązanie nr 1

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

make_set(x)

Wejście:

Wyjście:

find_set (x)

Wejście:

Wyjście:

Elementy pomocnicze:

union_sets(x, y)

Wejście:

Wyjście:

Elementy pomocnicze:

Przykładowe programy

Rozwiązanie nr 2

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

make_set(x)

Wejście:

Wyjście:

find_set(x)

Wejście:

Wyjście:

union_sets(x, y)

Wejście:

Wyjście:

Elementy pomocnicze:

Przykładowe programy

Rozwiązanie nr 3

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

make_set(x)

Wejście:

Wyjście:

Elementy pomocnicze:

find_set(x)

Wejście:

Wyjście:

union_sets(x, y)

Wejście:

Wyjście:

Elementy pomocnicze:

Przykładowe programy