Znajdowanie spójnych składowych w grafie


Tematy pokrewne   Podrozdziały
Grafy
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Transpozycja grafu
Kwadrat grafu
Graf krawędziowy
Stopień grafu
Znajdowanie ścieżki w grafie
Znajdowanie drogi w labiryncie
Spójność grafu
Znajdowanie spójnych składowych w grafie
Znajdowanie silnie spójnych składowych w grafie
Drzewa rozpinające grafu
Znajdowanie mostów w grafie
Znajdowanie punktów artykulacji w grafie
Grafy dwudzielne
Kojarzenie małżeństw
Cykliczność grafu
Znajdowanie cykli w grafie
Istnienie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Hamiltona
Sortowanie topologiczne grafu skierowanego
Najkrótsza ścieżka w grafie ważonym – algorytm Dijkstry
Najkrótsza ścieżka w grafie ważonym – algorytm Bellmana-Forda
Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Problem chińskiego listonosza
Problem komiwojażera
Minimalne drzewo rozpinające
Kolorowanie grafu
Znajdowanie klik w grafie

Zbiory rozłączne – implementacja w tablicy
Zbiory rozłączne – implementacja listowa
Zbiory rozłączne – implementacja za pomocą drzew

  Rozwiązanie dla grafu nieskierowanego
Rozwiązanie z wykorzystaniem zbiorów rozłącznych

Problem

Dla danego grafu nieskierowanego wyznaczyć wszystkie spójne składowe.



Graf jest spójny (ang. connected graph), jeśli dla każdych dwóch jego wierzchołków istnieje łącząca je ścieżka. Spójna składowa (ang. connected component), to największa grupa wierzchołków, które są wzajemnie połączone ze sobą ścieżkami. Graf spójny posiada tylko jedną spójną składową obejmującą wszystkie jego wierzchołki. Jeśli składowych takich jest więcej, to graf nazywamy niespójnym (ang. disconnected graph).

 

        
Graf spójny   Graf niespójny

 

Rozwiązanie dla grafu nieskierowanego

Co to znaczy: wyznaczyć spójną składową? To nic innego, jak zidentyfikować wierzchołki grafu, które należą do tej spójnej składowej. W tym celu z każdym z wierzchołków w grafie możemy skojarzyć dodatkową daną, którą nazwiemy c i która ma tę samą wartość dla wszystkich wierzchołków należących do tej samej spójnej składowej. Dane c mogą tworzyć tablicę, której elementy odpowiadają wartości c dla wierzchołka o numerze równym indeksowi – w ten sposób realizowaliśmy tablicę visited z informacjami o odwiedzonych wierzchołkach.

Znalezienie wartości c dla wszystkich wierzchołków grafu uzyskamy przy pomocy algorytmu DFS w sposób następujący:

 

Tworzymy tablicę C o tylu elementach, ile jest wierzchołków w grafie. Element C[i] odpowiada wartości c wierzchołka i-tego. Wszystkie elementy tablicy C zerujemy. Ustawiamy numer bieżącej składowej na 0. Przeglądamy kolejne elementy tablicy C. Jeśli napotkamy na element C[i] równy zero, to zwiększamy numer bieżącej składowej o 1 i od wierzchołka i-tego uruchamiamy przejście DFS grafu. W trakcie przejścia DFS we wszystkich odwiedzonych wierzchołkach ustawiamy wartość c na numer bieżącej składowej. Algorytm DFS gwarantuje nam odwiedzenie wszystkich wierzchołków, do których prowadzą ścieżki z wierzchołka startowego. Zatem w tablicy C zostaną ustawione na wartość bieżącej składowej wszystkie komórki, które odpowiadają odwiedzonym przez DFS wierzchołkom. W ten sposób znajdziemy spójną składową. Kontynuujemy przeglądanie tablicy C do jej końca.

Gdy przeglądniemy całą tablicę C, numer bieżącej składowej będzie nas informował o liczbie spójnych składowych w grafie. Jeśli wyniesie on 1, to graf jest spójny. W przeciwnym razie graf zawiera kilka spójnych składowych. Składowe te zidentyfikujemy przez kilkakrotne przeglądnięcie tablicy C. Najpierw wyszukujemy w niej elementy o wartości 1. Indeksy tych elementów są numerami wierzchołków grafu, które należą do spójnej składowej nr 1. Następnie wyszukujemy elementy o wartościach 2, 3..., aż do wartości, którą miała bieżąca składowa przy zakończeniu przeglądania tablicy C.

 

Algorytm wyszukiwania spójnych składowych w grafie nieskierowanym

Wejście
n  –  liczba wierzchołków w grafie, n C
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
Wyjście:
Informacja o liczbie spójnych składowych.
Dla każdej spójnej składowej grafu: numer składowej oraz lista wierzchołków, które do niej należą
Elementy pomocnicze:
C  –  tablica z numerami spójnych składowych
cn  –  liczba spójnych składowych, cn C
i,j  –  indeksy, i,j C
S  –  stos
v,u  –  numery wierzchołków w grafie, v,u C
Lista kroków:
K01: Utwórz tablicę C o n elementach  
K02: Wyzeruj elementy tablicy C  
K03: cn ← 0 ; zerujemy licznik spójnych składowych
K04: Dla i = 0,1,...,n-1: wykonuj K05..K15  
K05:     Jeśli C[i] > 0, to następny obieg pętli K04 : szukamy nieodwiedzonego jeszcze wierzchołka
K06:     cncn + 1 ; zwiększamy o 1 liczbę składowych
K07:     S.push(i) ; na stosie umieszczamy wierzchołek startowy
K08:     C[i] ← cn ; numerując wierzchołek, oznaczamy go jako odwiedzony
K09:     Dopóki S.empty() = false: wykonuj K10...K15 ; uruchamiamy przejście DFS
K10:         vS.top() ; odczytujemy wierzchołek ze stosu
K11:         S.pop() ; odczytany wierzchołek usuwamy ze stosu
K12:         Dla każdego sąsiada u wierzchołka v wykonuj K13...K15 ; część zależna od reprezentacji grafu
K13:             Jeśli C[u] > 0, to następny obieg pętli K12 ; szukamy nieodwiedzonego sąsiada
K14:             S.push(u) ; sąsiada umieszczamy na stosie
K15:             C[u] ← cn ; i oznaczamy go jako odwiedzony i ponumerowany
K16: Pisz cn ; wyprowadzamy liczbę spójnych składowych
K17: Dla i = 1,2,...,cn: wykonuj K18...K20  
K18:     Pisz i ; wypisujemy kolejne numery składowych
K19:     Dla j = 0,1,...,n-1: wykonuj K20  
K20:         Jeśli C[j] = i, to Pisz j ; oraz numery należących do nich wierzchołków
K21: 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 odczytuje definicję grafu nieskierowanego, wyszukuje w nim wszystkie spójne składowe, a następnie podaje należące do nich numery wierzchołków w grafie.

Przykładowe dane (spójne składowe zostały pokolorowane w celach testowych):

       17 17
0 1 0 2 0 3
1 2 1 14
4 11 4 12
5 6 5 9
6 7 6 8
10 15
11 15
12 15
13 14 13 16
14 16

 

Lazarus
// Znajdowanie spójnych składowych
// Data: 27.08.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------

program spojsklad;

// Typy dla dynamicznej tablicy list sąsiedztwa oraz stosu
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

TList = array of PslistEl;

// Definicja typu obiektowego stack
//---------------------------------
stack = object
  private
    S : PslistEl;  // lista przechowująca stos

  public
    constructor init;
    destructor destroy;
    function   empty : boolean;
    function   top : integer;
    procedure  push(v : integer);
    procedure  pop;
end;

// Konstruktor
//------------
constructor stack.init;
begin
  S := nil;
end;

// Destruktor
//-----------

destructor stack.destroy;
begin
  while S <> nil do pop;
end;

// Sprawdza, czy stos jest pusty
//------------------------------
function stack.empty : boolean;
begin
  if S = nil then empty := true else empty := false;
end;

// Zwraca liczbę ze szczytu stosu
//----------------------------------
function stack.top : integer;
begin
  top := S^.v;
end;

// Umieszcza dane na stosie
//-------------------------
procedure stack.push(v : integer);
var
  e : PslistEl;
begin
  new(e);
  e^.v := v;
  e^.next := S;
  S := e;
end;

// Usuwa dane ze stosu
//--------------------
procedure stack.pop;
var
  e :PslistEl;
begin
  if S <> NIL then
  begin
    e := S;
    S := S^.next;
    dispose(e);
  end;
end;

// **********************
// *** Program główny ***
// **********************

var
  n,m : integer;             // Liczba wierzchołków i krawędzi
  A   : TList;               // Tablica list sąsiedztwa
  C   : array of integer;    // Tablica z numerami spójnych składowych
  S   : stack;               // Stos
  cn,i,j,v,u : integer;
  p,r : PslistEl;

begin
  S.init;

  read(n,m);                 // Odczytujemy liczbę wierzchołków i krawędzi

  SetLength(A,n);            // Tworzymy tablice dynamiczne
  SetLength(C,n);

  // Tablicę A wypełniamy pustymi listami, a tablicę C wypełniamy zerami

  for i := 0 to n - 1 do
  begin
    A[i] := nil;
    C[i] := 0;
  end;

  // Odczytujemy kolejne definicje krawędzi.

  for i := 0 to m - 1 do
  begin
    read(v,u);               // Wierzchołki tworzące krawędź
    new(p);                  // Tworzymy nowy element
    p^.v := u;               // Numerujemy go jako w
    p^.next := A[v];         // Dodajemy go na początek listy A[v]
    A[v] := p;
    new(p);                  // To samo dla krawędzi w drugą stronę
    p^.v := v;
    p^.next := A[u];
    A[u] := p;
  end;

  cn := 0;                   // Zerujemy licznik spójnych składowych

  for i := 0 to n-1 do
    if C[i] = 0 then         // Szukamy nieodwiedzonego jeszcze wierzchołka
    begin
      inc(cn);               // Zwiększamy licznik składowych
      S.push(i);             // Na stosie umieszczamy numer bieżącego wierzchołka
      C[i] := cn;            // Wierzchołek numerujemy i oznaczamy jako odwiedzony
      while not S.empty do   // Przechodzimy graf algorytmem DFS
      begin
        v := S.top;          // Pobieramy wierzchołek
        S.pop;               // Usuwamy go ze stosu
        p := A[v];           // Przeglądamy sąsiadów wierzchołka v
        while p <> nil do
        begin
          u := p^.v;         // Numer sąsiada do u
          if C[u] = 0 then
          begin
            S.push(u);       // Na stos idą sąsiedzi nieodwiedzeni
            C[u] := cn;      // i ponumerowani
          end;
          p := p^.next;
        end;
      end;
    end;

  writeln;

  for i := 1 to cn do
  begin
    write('SCC ',i,' : '); // Numer spójnej składowej
    for j := 0 to n-1 do
      if C[j] = i then write(j:2,' '); // Wierzchołki tej składowej
    writeln;
  end;

  writeln;

    // Usuwamy tablicę list sąsiedztwa

  for i := 0 to n - 1 do
  begin
    p := A[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;

  SetLength(A,0);
  SetLength(C,0);
  S.destroy;
end.
Code::Blocks
// Znajdowanie spójnych składowych
// Data: 27.08.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa i stosu

struct slistEl
{
  slistEl * next;
  int v;
};

class stack
{
  private:
    slistEl * S;   // lista przechowująca stos

  public:
    stack();       // konstruktor
    ~stack();      // destruktor
    bool empty(void);
    int  top(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu stack
//---------------------

// Konstruktor
//------------
stack::stack()
{
  S = NULL;
}

// Destruktor - zwalnia tablicę dynamiczną
//----------------------------------------
stack::~stack()
{
  while(S) pop();
}

// Sprawdza, czy stos jest pusty
//------------------------------
bool stack::empty(void)
{
  return !S;
}

// Zwraca szczyt stosu
//--------------------
int stack::top(void)
{
  return S->v;
}

// Zapisuje na stos
//-----------------
void stack::push(int v)
{
  slistEl * e = new slistEl;
  e->v    = v;
  e->next = S;
  S = e;
}

// Usuwa ze stosu
//---------------
void stack::pop(void)
{
  if(S)
  {
    slistEl * e = S;
    S = S->next;
    delete e;
  }
}

// **********************
// *** Program główny ***
// **********************

int main()
{
  int n,m;                   // Liczba wierzchołków i krawędzi
  slistEl ** A;              // Tablica list sąsiedztwa
  int * C;                   // Tablica z numerami spójnych składowych
  stack S;                   // Stos
  int cn,i,j,v,u;
  slistEl *p,*r;

  cin >> n >> m;             // Odczytujemy liczbę wierzchołków i krawędzi

  A = new slistEl * [n];     // Tworzymy tablice dynamiczne
  C = new int [n];

  // Tablicę A wypełniamy pustymi listami, a tablicę C wypełniamy zerami

  for(i = 0; i < n; i++)
  {
    A[i] = NULL;
    C[i] = 0;
  }

  // Odczytujemy kolejne definicje krawędzi.

  for(i = 0; i < m; i++)
  {
    cin >> v >> u;           // Wierzchołki tworzące krawędź
    p = new slistEl;         // Tworzymy nowy element
    p->v = u;                // Numerujemy go jako w
    p->next = A[v];          // Dodajemy go na początek listy A[v]
    A[v] = p;
    p = new slistEl;         // To samo dla krawędzi w drugą stronę
    p->v = v;
    p->next = A[u];
    A[u] = p;
  }

  cn = 0;                    // Zerujemy licznik spójnych składowych

  for(i = 0; i < n; i++)
    if(!C[i])                // Szukamy nieodwiedzonego jeszcze wierzchołka
    {
      cn++;                  // Zwiększamy licznik składowych
      S.push(i);             // Na stosie umieszczamy numer bieżącego wierzchołka
      C[i] = cn;             // i oznaczamy go jako odwiedzonego i ponumerowanego
      while(!S.empty())      // Przechodzimy graf algorytmem DFS
      {
        v = S.top();         // Pobieramy wierzchołek
        S.pop();             // Usuwamy go ze stosu

        // Przeglądamy sąsiadów wierzchołka v

        for(p = A[v]; p; p = p->next)
        {
          u = p->v;          // Numer sąsiada do u
          if(!C[u])
          {
            S.push(u);       // Na stos idą sąsiedzi nieodwiedzeni
            C[u] = cn;       // i ponumerowani
          }
        }
      }
    }

  for(i = 1; i <= cn; i++)
  {
    cout << "SCC : " << i << " : "; // Numer spójnej składowej
    for(j = 0; j < n; j++)
      if(C[j] == i) cout << setw(2) << j << " "; // Wierzchołki tej składowej
    cout << endl;
  }

  cout << endl;

  // Usuwamy tablicę list sąsiedztwa

  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [] A;
  delete [] C;

  return 0;
}
Free Basic
' Znajdowanie spójnych składowych
' Data: 27.08.2013
' (C)2013 mgr Jerzy Wałaszek
'--------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa i stosu

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

Type stack
  Private:
    S As slistEl Ptr  ' lista zawierająca stos
  Public:
    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function top As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop()
End Type

'---------------------
' Metody obiektu stack
'---------------------

' Konstruktor
'------------
Constructor stack()
  S = 0
End Constructor

' Destruktor
'-----------
Destructor stack()
  While S
    pop()
  Wend
End Destructor

' Sprawdza, czy stos jest pusty
'------------------------------
Function stack.empty() As Integer
  If S = 0 Then Return 1
  Return 0
End Function

' Zwraca szczyt stosu.
'------------------------------
Function stack.top() As Integer
  top = S->v
End Function

' Zapisuje na stos
'-----------------
Sub stack.push(ByVal v As Integer)
  Dim e As slistEl Ptr
  e = New slistEl
  e->v    = v
  e->Next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub stack.pop()
  Dim e As slistEl Ptr
  If S Then
    e = S
    S = S->Next
    Delete e
  End If
End Sub

' **********************
' *** Program główny ***
' **********************

Dim As Integer n,m           ' Liczba wierzchołków i krawędzi
Dim As slistEl Ptr Ptr A     ' Tablica list sąsiedztwa
Dim As Integer Ptr C         ' Tablica z numerami spójnych składowych
Dim As stack S               ' Stos
Dim As Integer cn,i,j,v,u
Dim As slistEl Ptr p,r

Open Cons For Input As #1

Input #1,n,m                 ' Odczytujemy liczbę wierzchołków i krawędzi

A = New slistEl Ptr [n]      ' Tworzymy tablice dynamiczne
C = New Integer [n]

' Tablicę A wypełniamy pustymi listami, a tablicę C wypełniamy zerami

For i = 0 To n - 1
  A[i] = 0
  C[i] = 0
Next

' Odczytujemy kolejne definicje krawędzi.

For i = 0 To m - 1
  Input #1,v,u               ' Wierzchołki tworzące krawędź
  p = new slistEl            ' Tworzymy nowy element
  p->v = u                   ' Numerujemy go jako w
  p->next = A[v]             ' Dodajemy go na początek listy A[v]
  A[v] = p
  p = new slistEl            ' To samo dla krawędzi w drugą stronę
  p->v = v
  p->next = A[u]
  A[u] = p
Next

cn = 0                       ' Zerujemy licznik spójnych składowych

For i = 0 To n - 1
  If C[i]= 0 Then            ' Szukamy nieodwiedzonego jeszcze wierzchołka
    cn += 1                  ' Zwiększamy licznik składowych
    S.push(i)                ' Na stosie umieszczamy numer bieżącego wierzchołka,
    C[i] = cn                ' oznaczając go jako odwiedzonego i ponumerowanego
    While S.empty() = 0      ' Przechodzimy graf algorytmem DFS
      v = S.top()            ' Pobieramy wierzchołek
      S.pop()                ' Usuwamy go ze stosu
      p = A[v]               ' Przeglądamy sąsiadów wierzchołka v
      While p
        u = p->v             ' Numer sąsiada do u
        If C[u] = 0 Then
          S.push(u)          ' Na stos idą sąsiedzi nieodwiedzeni
          C[u] = cn          ' i ponumerowani 
        End If
        p = p->next
      Wend
    Wend
  End If
Next

Print

For i = 1 To cn
  Print "SCC";i;" :"; ' Numer spójnej składowej
  For j = 0 To n - 1
    If C[j] = i Then Print Using "###";j; ' Wierzchołki tej składowej
  Next
  Print
Next

Print

' Usuwamy tablicę list sąsiedztwa

For i = 0 To n - 1
  p = A[i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [] A
Delete [] C

End
Wynik
17 17
0 1 0 2 0 3
1 2 1 14
4 11 4 12
5 6 5 9
6 7 6 8
10 15
11 15
12 15
13 14 13 16
14 16

SCC 1 :  0  1  2  3 13 14 16
SCC 2 :  4 10 11 12 15
SCC 3 :  5  6  7  8  9

 

Rozwiązanie z wykorzystaniem zbiorów rozłącznych

Wierzchołki grafu należą do tej samej spójnej składowej, jeśli łączy je krawędź. Wykorzystując strukturę zbiorów rozłącznych, można w prosty sposób rozwiązać problem znajdowania spójnych składowych w grafie. W tym celu dla każdego wierzchołka grafu tworzymy osobny zbiór rozłączny. Następnie przechodzimy przez wszystkie krawędzie grafu, wykonując operację UnionSets dla wierzchołków tworzących te krawędzie. Algorytm staje się banalnie prosty:

 

Algorytm wyszukiwania spójnych składowych w grafie nieskierowanym za pomocą zbiorów rozłącznych

Wejście
n  –  liczba wierzchołków w grafie, n C
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
Wyjście:
T  –  tablica elementów struktury zbiorów rozłącznych reprezentujących wierzchołki grafu, w której zawarta jest informacja o przynależności poszczególnych wierzchołków do określonych spójnych składowych.
Elementy pomocnicze:
i,u,v  –  indeks i numery wierzchołków, i,u,v C
MakeSet(x)  –  tworzy jednoelementowy zbiór z wierzchołkiem x
UnionSets(x,y)  –  łączy ze sobą zbiory zawierające wierzchołki x i y.
Lista kroków:
K01: Twórz tablicę T n elementową
i zainicjuj ją kolejnymi numerami wierzchołków grafu
 
K02: Dla i = 0,1,...,n-1 wykonuj: MakeSet(i) ; tworzymy zbiory jednoelementowe
K03: Dla każdej krawędzi uv grafu wykonaj
    UnionSets(u,v)
; łączymy zbiory zawierające wierzchołki tworzące krawędź
K05: Zakończ z wynikiem T  

 

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 odczytuje definicję grafu nieskierowanego, wyszukuje w nim wszystkie spójne składowe, a następnie podaje należące do nich numery wierzchołków w grafie.

Przykładowe dane (spójne składowe zostały pokolorowane w celach testowych):

       17 17
0 1 0 2 0 3
1 2 1 14
4 11 4 12
5 6 5 9
6 7 6 8
10 15
11 15
12 15
13 14 13 16
14 16

 

Lazarus
// Znajdowanie spójnych składowych
// za pomocą zbiorów rozłącznych
// Data: 1.04.2014
// (C)2014 mgr Jerzy Wałaszek
//--------------------------------

// Typy danych dla drzew struktury zbiorów rozłącznych
type
  PTNode = ^TNode;
  TNode =  record
    up   : PTNode;                // Rodzic węzła
    rank : integer;               // Ranga
    data : integer;               // Zawartość węzła
  end;

// Tworzy drzewo jednowęzłowe
//---------------------------
procedure MakeSet(x : PTNode);
begin
  x^.up := x;                     // x staje się korzeniem drzewa
  x^.rank := 0;                   // Rangę zerujemy
end;

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

// Łączy ze sobą drzewa z x i z y
//-------------------------------
procedure UnionSets(x,y : PTNode);
var
  rx,ry : PTNode;
begin
  rx := FindSet(x);               // Wyznaczamy korzeń drzewa z węzłem x
  ry := FindSet(y);               // Wyznaczamy korzeń drzewa z węzłem y
  if rx <> ry then                // Korzenie muszą być różne
  begin
    if rx^.rank > ry^.rank then   // Porównujemy rangi drzew
       ry^.up := rx               // rx większe, dołączamy ry
    else
    begin
      rx^.up := ry;               // równe lub ry większe, dołączamy rx
      if rx^.rank = ry^.rank then inc(ry^.rank);
    end;
  end;
end;

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

var
  n,m : integer;                  // Liczba wierzchołków i krawędzi
  T   : array of TNode;
  i,j,v,u : integer;
begin
  read(n,m);                      // Odczytujemy liczbę wierzchołków i krawędzi
  SetLength(T,n);                 // Ustalamy rozmiar tablicy zbiorów rozłącznych

  // Tablicę T inicjujemy

  for i := 0 to n - 1 do
  begin
    T[i].data := i;               // Numer węzła
    MakeSet(addr(T[i]));          // Tworzymy zbiór jednoelementowy
  end;

  // Odczytujemy kolejne definicje krawędzi.

  for i := 0 to m - 1 do
  begin
    read(v,u);                    // Wierzchołki tworzące krawędź
    UnionSets(addr(T[v]),addr(T[u])); // Łączymy zbiory z u i v
  end;

  // Wypisujemy wyniki

  writeln;

  for i := 0 to n - 1 do
    if i = FindSet(addr(T[i]))^.data then
    begin
      write('SCC id =',i:3,' : ');
      for j := 0 to n - 1 do
        if i = FindSet(addr(T[j]))^.data then write(j:3);
      writeln;
    end;

  // Usuwamy tablicę zbiorów rozłącznych

  SetLength(T,0);

end.
Code::Blocks
// Znajdowanie spójnych składowych
// za pomocą zbiorów rozłącznych
// Data: 1.04.2014
// (C)2014 mgr Jerzy Wałaszek
//--------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy danych dla drzew struktury zbiorów rozłącznych

struct TNode
{
  TNode *up;                      // Rodzic węzła
  int rank;                       // Ranga
  int data;                       // Zawartość węzła
};

// Tworzy drzewo jednowęzłowe
//---------------------------
void MakeSet(TNode * x)
{
  x->up = x;                      // x staje się korzeniem drzewa
  x->rank = 0;                    // Rangę zerujemy
}

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

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

  rx = FindSet(x);                // Wyznaczamy korzeń drzewa z węzłem x
  ry = FindSet(y);                // Wyznaczamy korzeń drzewa z węzłem y
  if(rx != ry)                    // Korzenie muszą być różne
  {
    if(rx->rank > ry->rank)       // Porównujemy rangi drzew
       ry->up = rx;               // rx większe, dołączamy ry
    else
    {
      rx->up = ry;                // równe lub ry większe, dołączamy rx
      if(rx->rank == ry->rank) ry->rank++;
    }
  }
}

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

int main()
{
  int n,m;                        // Liczba wierzchołków i krawędzi
  TNode * T;
  int i,j,v,u;

  cin >> n >> m;                  // Odczytujemy liczbę wierzchołków i krawędzi
  T = new TNode [n];              // Tworzymy tablicę zbiorów rozłącznych

  // Tablicę T inicjujemy

  for(i = 0; i < n; i++)
  {
    T[i].data = i;                // Numer węzła
    MakeSet(&T[i]);               // Tworzymy zbiór jednoelementowy
  }

  // Odczytujemy kolejne definicje krawędzi.

  for(i = 0; i < m; i++)
  {
    cin >> v >> u;                // Wierzchołki tworzące krawędź
    UnionSets(&T[v],&T[u]);       // Łączymy zbiory z u i v
  }

  // Wypisujemy wyniki

  cout << endl;

  for(i = 0; i < n; i++)
    if(i == FindSet(&T[i])->data)
    {
      cout << "SCC id =" << setw(3) << i << " :";
      for(j = 0; j < n; j++)
        if(i == FindSet(&T[j])->data) cout << setw(3) << j;
      cout << endl;
    }

  // Usuwamy tablicę zbiorów rozłącznych

  delete [] T;

  return 0;
}
Free Basic
' Znajdowanie spójnych składowych
' za pomocą zbiorów rozłącznych
' Data: 1.04.2014
' (C)2014 mgr Jerzy Wałaszek
'--------------------------------

' Typy danych dla drzew struktury zbiorów rozłącznych

Type TNode
  up As TNode Ptr                 ' Rodzic węzła
  rank As Integer                 ' Ranga
  Data As Integer                 ' Zawartość węzła
End Type

' Tworzy drzewo jednowęzłowe
'---------------------------
Sub MakeSet(ByVal x As TNode Ptr)
  x->up = x                       ' x staje się korzeniem drzewa
  x->rank = 0                     ' Rangę zerujemy  
End Sub

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

' Łączy ze sobą drzewa z x i z y
'--------------------------------
Sub UnionSets(ByVal x As TNode Ptr, ByVal y As TNode Ptr)

  Dim As TNode Ptr rx,ry

  rx = FindSet(x)                 ' Wyznaczamy korzeń drzewa z węzłem x
  ry = FindSet(y)                 ' Wyznaczamy korzeń drzewa z węzłem y
  If rx <> ry Then                ' Korzenie muszą być różne
    If rx->rank > ry->rank Then   ' Porównujemy rangi drzew
      ry->up = rx                 ' rx większe, dołączamy ry
    Else
      rx->up = ry                 ' równe lub ry większe, dołączamy rx
      If rx->rank = ry->rank Then ry->rank += 1
    End If
  End If
End Sub

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

Dim As Integer n,m                ' Liczba wierzchołków i krawędzi
Dim As TNode Ptr T
Dim As integer i,j,v,u

Open Cons For Input As #1

Input #1,n,m                      ' Odczytujemy liczbę wierzchołków i krawędzi
T = New TNode [n]                 ' Tworzymy tablicę zbiorów rozłącznych

' Tablicę T inicjujemy

For i = 0 To n - 1
  T[i].data = i                   ' Numer węzła
  MakeSet(VarPtr(T[i]))           ' Tworzymy zbiór jednoelementowy
Next

' Odczytujemy kolejne definicje krawędzi.

For i = 0 To m - 1
  Input #1,v,u                    ' Wierzchołki tworzące krawędź
  UnionSets(VarPtr(T[v]),VarPtr(T[u])) ' Łączymy zbiory z u i v
Next

Close #1

' Wypisujemy wyniki

Print

For i = 0 To n - 1
  If i = FindSet(VarPtr(T[i]))->Data Then
    Print Using "SCC id =### :";i;
    For j = 0 To n - 1
      If i = FindSet(VarPtr(T[j]))->Data Then Print Using "###";j;
    Next
    Print
  End If
Next

' Usuwamy tablicę zbiorów rozłącznych

Delete [] T

End
Wynik
17 17
0 1 0 2 0 3
1 2 1 14
4 11 4 12
5 6 5 9
6 7 6 8
10 15
11 15
12 15
13 14 13 16
14 16

SCC id =  1 :  0  1  2  3 13 14 16
SCC id =  6 :  5  6  7  8  9
SCC id = 15 :  4 10 11 12 15

 



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.