Znajdowanie klik 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

Podstawowe pojęcia dotyczące zbiorów
Reprezentacja zbiorów na listach
Reprezentacja zbiorów w tablicach
Reprezentacja zbiorów w mapach bitowych
Reprezentacja zbiorów w drzewach binarnych

  Rozwiązanie nr 1
Rozwiązanie nr 2
Klika największa

Problem

W danym grafie nieskierowanym znaleźć wszystkie kliki maksymalne.

 

 

Kliką (ang. clique) w grafie nazwiemy jego podgraf, którego wszystkie wierzchołki są ze sobą nawzajem połączone krawędziami. Innymi słowy, klika jest podgrafem pełnym danego grafu.

 

 

Klika maksymalna (ang. maximal clique) jest taką kliką grafu, że nie można do niej już dodać żadnego nowego wierzchołka z grafu.

Klika największa (ang. maximum clique) jest największym podgrafem pełnym. Problem znajdowania największej kliki jest problemem trudnym obliczeniowo.

 

Rozwiązanie nr 1

Do znajdowania maksymalnych klik w grafie nieskierowanym można zastosować prosty algorytm rekurencyjny Brona-Kerboscha. Algorytm otrzymuje na wejściu trzy zbiory P, R i X o następującym znaczeniu:

 

P  –  zbiór wierzchołków, które są kandydatami do rozważenia
R  –  zbiór wierzchołków, które są częściowym wynikiem znajdowania kliki
X  –  zbiór wierzchołków pominiętych

 

Przy pierwszym wywołaniu algorytmu zbiory R i X są puste, a zbiór P zawiera wszystkie wierzchołki grafu. Zasada działania algorytmu jest następująca:

 

Najpierw sprawdzamy w algorytmie, czy zbiory P i X są puste. Jeśli tak, to zbiór R zawiera maksymalną klikę. Wypisujemy zawartość zbioru R i kończymy.

Jeśli zbiór P nie jest pusty, to wybieramy z niego kolejne wierzchołki v. Dla każdego z tych wierzchołków tworzymy następujące zbiory tymczasowe:

  • N – zbiór wszystkich sąsiadów wierzchołka v

  • R'  – zbiór R z dodanym wierzchołkiem v

  • P' – iloczyn zbiorów P i N (z P' zostaną usunięte wszystkie wierzchołki, które nie są sąsiadami wierzchołka v)

  • X' – iloczyn zbiorów X i N (z X' zostaną usunięte wszystkie wierzchołki, które nie są sąsiadami wierzchołka v)

Wywołujemy rekurencyjnie algorytm ze zbiorami P', R' i X'.

Następnie ze zbioru P usuwamy wierzchołek v, a dodajemy go do zbioru X i kontynuujemy pętlę.

 

Algorytm Brona-Kerboscha znajdowania wszystkich klik maksymalnych w grafie nieskierowanym - wersja nr 1

BronKerbosch(n,graf,R,P,X)
Wejście
n  –  liczba wierzchołków w grafie, n symbol C
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
R  –  zbiór wierzchołków, które są częściowym wynikiem znajdowania kliki
P  –  zbiór wierzchołków, które są kandydatami do rozważenia
X  –  zbiór wierzchołków pominiętych
Wyjście:
Wszystkie kliki maksymalne w grafie
Elementy pomocnicze:
u,v  –  numery wierzchołków grafu, u,v symbol C
P',R',X',N  –  pomocnicze zbiory wierzchołków
Lista kroków:
K01: Jeśli (P jest pusty) (X jest pusty), to
    Pisz R i zakończ

; znaleziona klika maksymalna
K02: Dla każdego wierzchołka v w P wykonuj K03...K10  
K03:     Zeruj zbiór N  
K04:     Dla każdego sąsiada u wierzchołka v wykonuj:
        NN + u
; tworzymy zbiór sąsiadów
K05:     R'R + v ; w R' tworzymy zbiór R z dodanym wierzchołkiem v
K06:     P' ← iloczyn zbiorów P i N ; z P' usuwamy wierzchołki, które nie są sąsiadami v
K07:     X' ← iloczyn zbiorów X i N ; z X' usuwamy wierzchołki, które nie są sąsiadami v
K08:     BronKerbosch(n,graf,R',P',X') ; wywołanie rekurencyjne
K09:     PP - v ; ze zbioru P usuwamy wierzchołek v
K10:     RR + v ; do zbioru R dodajemy wierzchołek v
K11: 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 i wyszukuje w nim wszystkie kliki maksymalne za pomocą algorytmu Brona-Kerboscha. Zbiory zostały zaimplementowane w mapach bitowych.

Program dodatkowo wypisuje liczbę wywołań rekurencyjnych algorytmu Brona-Kerboscha dla celów porównawczych.

Przykładowe dane dla programu:

  8 19
0 1 0 2 0 5 0 6
1 2 1 3 1 5 1 6
2 4 2 5 2 6 2 7
3 4 3 6 3 7
4 6
5 6 5 7
6 7

 

Lazarus
// Algorytm Brona-Kerboscha
// Data   : 10.07.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program cliques;

// Definicja elementu listy sąsiedztwa
type
  PslistEl = ^slistEl;
  slistEl = record
    next : PslistEl;              // Następny element listy
    v : integer;                  // Wierzchołek docelowy
  end;

// Definicja struktury zbioru
  s_set =  record
    vmin  : integer;
    nmax  : integer;
    T     : array of cardinal;
  end;

// Zmienne globalne
var
  n,m  : integer;                 // Liczba wierzchołków i krawędzi grafu
  graf : array of PslistEl;       // Tablica list sąsiedztwa
  SN   : s_set;                   // Zbiór sąsiadów
  rcnt : integer;                 // Licznik wywołań rekurencyjnych

// Obsługa zbiorów

// Procedura dodaje element x do zbioru A
//---------------------------------------
procedure s_add(var A : s_set; x : integer);
var
  b,i : integer;
begin
  b := x - A.vmin;                // Obliczamy numer bitu
  i := b shr 5;                   // Obliczamy indeks
  A.T[i] := A.T[i] or (1 shl (b and 31)); // Ustawiamy bit na 1
end;

// Procedura usuwa element x ze zbioru
//------------------------------------
procedure s_remove(var A : s_set; x : integer);
var
  b,i : integer;
begin
  b := x - A.vmin;                // Obliczamy numer bitu
  i := b shr 5;                   // Obliczamy indeks
  A.T[i] := A.T[i] and not (1 shl (b and 31)); // Ustawiamy bit na 0
end;

// Procedura usuwa wszystkie elementy ze zbioru
//---------------------------------------------
procedure s_clear(var A : s_set);
var
  i : integer;
begin
  for i := 0 to A.nmax do A.T[i] := 0; // Zerujemy tablicę
end;

// Procedura tworzy zbiór
//-----------------------
procedure s_create(var A : s_set; vmin,vmax : integer);
begin
  A.vmin := vmin;                 // Wypełniamy strukturę danymi
  A.nmax := (vmax - vmin) shr 5;  // Indeks ostatniego elementu tablicy
  SetLength(A.T,A.nmax + 1);      // Tworzymy dynamicznie tablicę mapy bitowej
  s_clear(A);                     // Tworzymy zbiór pusty
end;

// Procedura wyznacza część wspólną zbiorów A i B
//-----------------------------------------------
procedure s_intersection(var A,B,C : s_set);
var
  i : integer;
begin
  for i := 0 to A.nmax do  C.T[i] := A.T[i] and B.T[i];
end;

// Procedura kopiuje zbiór A do zbioru B
//--------------------------------------
procedure s_copy(var A,B : s_set);
var
  i : integer;
begin
  for i := 0 to A.nmax do B.T[i] := A.T[i];
end;

// Procedura ustawia zbiór pełny
procedure s_full(var A : s_set);
var
  i : integer;
begin
  for i := 0 to A.nmax do A.T[i] := $ffffffff;
end;

// Funkcja sprawdza, czy zbiór A jest pusty
// true  - tak, jest pusty
// false - nie, nie jest pusty
//-----------------------------------------
function s_empty(var A : s_set) : boolean;
var
  i : integer;
  m : cardinal;
begin
  m := A.T[0];                    // Pobieramy bity do m
  for i := 1 to A.nmax do
    m := m or A.T[i];             // Sumujemy logicznie bity
  s_empty := (m = 0);
end;

// Funkcja bada, czy element x należy do zbioru A
// true  - tak, należy
// false - nie, nie należy
//-----------------------------------------------
function s_isin(var A : s_set; x : integer) : boolean;
var
  b : integer;
begin
  b := x - A.vmin;                // Obliczamy numer bitu w mapie bitowej
  if A.T[b shr 5] and (1 shl (b and 31)) > 0 then Exit(true);
  s_isin := false;
end;

// Procedura wyświetla elementy zbioru A
//--------------------------------------
procedure s_print(var A : s_set);
var
  i,nb : integer;
  m : cardinal;
begin
  for i := 0 to A.nmax do
  begin
    nb := 0;
    m  := A.T[i];
    while m > 0 do
    begin
      if (m and 1) = 1 then write((i shl 5) + nb + A.vmin,' ');
      m := m shr 1;
      inc(nb);
    end
  end;
end;

// Procedura wyszukuje kliki maksymalne
//-------------------------------------
procedure BronKerbosch(var SR,SP,SX : s_set);
var
  RP,PP,XP : s_set;
  p : PslistEl;
  v : integer;
begin

  inc(rcnt);                      // Zwiększamy licznik wywołań rekurencyjnych

  if s_empty(SP) and s_empty(SX) then // Jeśli zbiory SP i SX są puste,
  begin                           // to SR zawiera wierzchołki kliki maksymalnej
    write('MAXIMAL CLIQUE: ');
    s_print(SR);
    writeln;
  end
  else
  begin
    s_create(RP,0,n-1);           // Tworzymy puste zbiory pomocnicze
    s_create(PP,0,n-1);
    s_create(XP,0,n-1);
    for v := 0 to n - 1 do        // Przechodzimy przez kolejne wierzchołki grafu
      if s_isin(SP,v) then        // Jeśli wierzchołek v jest w zbiorze SP, to
      begin                       // go przetwarzamy
        s_clear(SN);              // Najpierw zerujemy zbiór sąsiadów
        p := graf[v];             // Przeglądamy listę sąsiedztwa wierzchołka v
        while p <> nil do
        begin
          s_add(SN,p^.v);         // Każdego sąsiada umieszczamy w SN
          p := p^.next;
        end;
        s_copy(SR,RP);            // W RP tworzymy zbiór SR z dodanym wierzchołkiem v
        s_add(RP,v);
        s_intersection(SP,SN,PP); // W PP tworzymy iloczyn SP i SN
        s_intersection(SX,SN,XP); // W XP tworzymy iloczyn SX i SN
        BronKerbosch(RP,PP,XP);   // Wywołanie rekurencyjne
        s_remove(SP,v);           // Z SP usuwamy wierzchołek v
        s_add(SX,v);              // i dodajemy go do SX
      end;
    SetLength(RP.T,0);            // Usuwamy zbiory pomocnicze
    SetLength(PP.T,0);
    SetLength(XP.T,0);
  end;
end;

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

var
  SR,SP,SX : s_set;
  i,u,v : integer;
  p,r : PslistEl;
begin

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

  s_create(SR,0,n-1);             // Tworzymy puste zbiory
  s_create(SP,0,n-1);
  s_create(SX,0,n-1);
  s_create(SN,0,n-1);

  SetLength(graf,n);              // Tworzymy tablicę list sąsiedztwa

  for i := 0 to n - 1 do graf[i] := nil; // Zerujemy listy sąsiedztwa

  for i := 1 to m do
  begin
    read(u,v);                    // Wierzchołki krawędzi
    new(p);                       // Tworzymy element listy
    p^.v := u;
    p^.next := graf[v];           // Element dołączamy do listy sąsiadów v
    graf[v] := p;

    new(p);                       // To samo dla krawędzi w drugą stronę
    p^.v := v;
    p^.next := graf[u];           // Element dołączamy do listy sąsiadów u
    graf[u] := p;
  end;

  s_full(SP);                     // W zbiorze SP ustawiamy wszystkie wierzchołki

  writeln;

  rcnt := 0;                      // Zerujemy licznik wywołań rekurencyjnych

  BronKerbosch(SR,SP,SX);         // Szukamy rekurencyjnie klik maksymalnych

  writeln;
  writeln('RECURSIVE CALLS = ',rcnt);
  writeln;

  SetLength(SR.T,0);              // Usuwamy zbiory
  SetLength(SP.T,0);
  SetLength(SX.T,0);
  SetLength(SN.T,0);

  for v := 0 to n - 1 do          // Usuwamy tablicę list sąsiedztwa
  begin
    p := graf[v];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;

  SetLength(graf,0);

end.
Code::Blocks
// Algorytm Brona-Kerboscha
// Data   : 10.07.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Definicja elementu listy sąsiedztwa

struct slistEl
{
  slistEl *next;                  // Następny element listy
  int v;                          // Wierzchołek docelowy
};

// Definicja struktury zbioru

struct s_set
{
  int vmin,nmax;
  unsigned int *T;
};

// Zmienne globalne

int n,m;                          // Liczba wierzchołków i krawędzi grafu
slistEl ** graf;                  // Tablica list sąsiedztwa
s_set SN;                         // Zbiór sąsiadów
int rcnt = 0;                     // Licznik wywołań rekurencyjnych

// Obsługa zbiorów

// Procedura dodaje element x do zbioru A
//---------------------------------------
void s_add(s_set & A, int x)
{
  int b = x - A.vmin;             // Obliczamy numer bitu
  int i = b >> 5;                 // Obliczamy indeks
  A.T[i] |= 1 << (b & 31);        // Ustawiamy bit na 1
}

// Procedura usuwa element x ze zbioru
//------------------------------------
void s_remove(s_set & A, int x)
{
  int b = x - A.vmin;             // Obliczamy numer bitu
  int i = b >> 5;                 // Obliczamy indeks
  A.T[i] &= ~(1 << (b & 31));     // Ustawiamy bit na 0
}

// Procedura usuwa wszystkie elementy ze zbioru
//---------------------------------------------
void s_clear(s_set & A)
{
  for(int i = 0; i <= A.nmax; i++) A.T[i] = 0; // Zerujemy mapę bitową
}

// Procedura tworzy zbiór
//-----------------------
void s_create(s_set & A, int vmin, int vmax)
{
  A.vmin = vmin;                  // Wypełniamy strukturę danymi
  A.nmax = (vmax - vmin) >> 5;    // Indeks ostatniego elementu tablicy
  A.T = new unsigned int [A.nmax + 1];  // Tworzymy dynamicznie tablicę mapy bitowej
  s_clear(A);                     // Tworzymy zbiór pusty
}

// Procedura wyznacza część wspólną zbiorów A i B
//-----------------------------------------------
void s_intersection(s_set & A, s_set & B, s_set & C)
{
  for(int i = 0; i <= A.nmax; i++) C.T[i] = A.T[i] & B.T[i];
}

// Procedura kopiuje zbiór A do zbioru B
//--------------------------------------
void s_copy(s_set & A, s_set & B)
{
  for(int i = 0; i <= A.nmax; i++) B.T[i] = A.T[i];
}

// Procedura ustawia zbiór pełny
//------------------------------
void s_full(s_set & A)
{
  for(int i = 0; i <= A.nmax; i++) A.T[i] = 0xffffffff;
}

// Funkcja sprawdza, czy zbiór A jest pusty
// true  - tak, jest pusty
// false - nie, nie jest pusty
//-----------------------------------------
bool s_empty(s_set A)
{
  unsigned int m = A.T[0];        // Pobieramy bity do m
  for(int i = 1; i <= A.nmax; i++) m |= A.T[i]; // Sumujemy logicznie bity
  return (m == 0);
}

// Funkcja bada, czy element x należy do zbioru A
// true  - tak, należy
// false - nie, nie należy
//-----------------------------------------------
bool s_isin(s_set & A, int x)
{
  int b = x - A.vmin;             // Obliczamy numer bitu w mapie bitowej
  if(A.T[b >> 5] & (1 << (b & 31))) return true;
  return false;
}

// Procedura wyświetla elementy zbioru A
//--------------------------------------
void s_print(s_set A)
{
  int nb;
  unsigned int m;

  for(int i = 0; i <= A.nmax; i++)
    for(nb = 0,m = A.T[i]; m; m >>= 1,nb++)
      if(m & 1) cout << (i << 5) + nb + A.vmin << " ";
}

// Procedura wyszukuje kliki maksymalne
//-------------------------------------
void BronKerbosch(s_set & SR, s_set & SP, s_set & SX)
{
  s_set RP,PP,XP;
  slistEl * p;
  int v;

  rcnt++;                         // Zwiększamy licznik wywołań rekurencyjnych

  if(s_empty(SP) && s_empty(SX))  // Jeśli zbiory SP i SX są puste,
  {                               // to SR zawiera wierzchołki kliki maksymalnej
    cout << "MAXIMAL CLIQUE: ";
    s_print(SR);
    cout << endl;
  }
  else
  {
    s_create(RP,0,n-1);           // Tworzymy puste zbiory pomocnicze
    s_create(PP,0,n-1);
    s_create(XP,0,n-1);
    for(v = 0; v < n; v++)        // Przechodzimy przez kolejne wierzchołki grafu
      if(s_isin(SP,v))            // Jeśli wierzchołek v jest w zbiorze SP, to
      {                           // go przetwarzamy
        s_clear(SN);              // Najpierw zerujemy zbiór sąsiadów
        for(p = graf[v];p;p = p->next) // Przeglądamy listę sąsiedztwa wierzchołka v
          s_add(SN,p->v);         // Każdego sąsiada umieszczamy w SN
        s_copy(SR,RP);            // W RP tworzymy zbiór SR z dodanym wierzchołkiem v
        s_add(RP,v);
        s_intersection(SP,SN,PP); // W PP tworzymy iloczyn SP i SN
        s_intersection(SX,SN,XP); // W XP tworzymy iloczyn SX i SN
        BronKerbosch(RP,PP,XP);   // Wywołanie rekurencyjne
        s_remove(SP,v);           // Z SP usuwamy wierzchołek v
        s_add(SX,v);              // i dodajemy go do SX
      }
    delete [] RP.T;              // Usuwamy zbiory pomocnicze
    delete [] PP.T;
    delete [] XP.T;
  }
}

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

int main()
{
  s_set SR,SP,SX;
  int i,u,v;
  slistEl *p,*r;

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

  s_create(SR,0,n-1);             // Tworzymy puste zbiory
  s_create(SP,0,n-1);
  s_create(SX,0,n-1);
  s_create(SN,0,n-1);

  graf = new slistEl * [n];       // Tworzymy tablicę list sąsiedztwa

  for(i = 0; i < n; i++) graf[i] = NULL; // Zerujemy listy sąsiedztwa

  for(i = 0; i < m; i++)
  {
    cin >> u >> v;                // Wierzchołki krawędzi
    p = new slistEl;              // Tworzymy element listy
    p->v = u;
    p->next = graf[v];            // Element dołączamy do listy sąsiadów v
    graf[v] = p;

    p = new slistEl;              // To samo dla krawędzi w drugą stronę
    p->v = v;
    p->next = graf[u];            // Element dołączamy do listy sąsiadów u
    graf[u] = p;
  }

  s_full(SP);                     // W zbiorze SP ustawiamy wszystkie wierzchołki

  cout << endl;

  BronKerbosch(SR,SP,SX);         // Szukamy rekurencyjnie klik maksymalnych

  cout << endl << "RECURSIVE CALLS = " << rcnt << endl << endl;

  delete [] SR.T;                 // Usuwamy zbiory
  delete [] SP.T;
  delete [] SX.T;
  delete [] SN.T;

  for(v = 0; v < n; v++)          // Usuwamy tablicę list sąsiedztwa
  {
    p = graf[v];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }

  delete [] graf;

  return 0;
}
Free Basic
' Algorytm Brona-Kerboscha
' Data   : 10.07.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Definicja elementu listy sąsiedztwa

Type slistEl
  next As slistEl Ptr             ' Następny element listy
  v As Integer                    ' Wierzchołek docelowy
End Type

' Definicja struktury zbioru

Type s_set
  vmin As Integer
  nmax As Integer
  T As UInteger Ptr
End Type

' Zmienne globalne

Dim Shared As Integer n,m         ' Liczba wierzchołków i krawędzi grafu
Dim Shared As slistEl Ptr Ptr graf ' Tablica list sąsiedztwa
Dim Shared As s_set SN            ' Zbiór sąsiadów
Dim Shared As Integer rcnt = 0    ' Licznik wywołań rekurencyjnych

' Obsługa zbiorów

' Procedura dodaje element x do zbioru A
'---------------------------------------
Sub s_add(ByRef A As s_set, ByVal x As Integer)
  Dim As Integer b,i

  b = x - A.vmin                  ' Obliczamy numer bitu
  i = b Shr 5                     ' Obliczamy indeks
  A.T[i] = A.T[i] or (1 Shl (b and 31)) ' Ustawiamy bit na 1
End Sub

' Procedura usuwa element x ze zbioru
'------------------------------------
Sub s_remove(ByRef A As s_set, ByVal x As Integer)
  Dim As Integer b,i

  b = x - A.vmin                  ' Obliczamy numer bitu
  i = b Shr 5                     ' Obliczamy indeks
  A.T[i] = A.T[i] And Not (1 Shl (b and 31)) ' Ustawiamy bit na 0
End Sub

' Procedura usuwa wszystkie elementy ze zbioru
'---------------------------------------------
Sub s_clear(ByRef A As s_set)
  Dim As Integer i
  For i = 0 To A.nmax
  	 A.T[i] = 0                    ' Zerujemy mapę bitową
  Next
End Sub

' Procedura tworzy zbiór
'-----------------------
Sub s_create(ByRef A As s_set, ByVal vmin As Integer, ByVal vmax As Integer)
  A.vmin = vmin                   ' Wypełniamy strukturę danymi
  A.nmax = (vmax - vmin) shr 5    ' Indeks ostatniego elementu tablicy
  A.T = New UInteger [A.nmax + 1] ' Tworzymy dynamicznie tablicę mapy bitowej
  s_clear(A)                      ' Tworzymy zbiór pusty
End Sub

' Procedura wyznacza część wspólną zbiorów A i B
'-----------------------------------------------
Sub s_intersection(ByRef A As s_set, ByRef B As s_set, ByRef C As s_set)
  Dim As Integer i

  For i = 0 To A.nmax
  	 C.T[i] = A.T[i] And B.T[i]
  Next
End Sub

' Procedura kopiuje zbiór A do zbioru B
'--------------------------------------
Sub s_copy(ByRef A As s_set, ByRef B As s_set)
  Dim As Integer i
  For i= 0 To A.nmax
  	 B.T[i] = A.T[i]
  Next
End Sub

' Procedura ustawia zbiór pełny
'------------------------------
Sub s_full(ByRef A As s_set)
  Dim As Integer i
  For i = 0 To A.nmax
  	 A.T[i] = &Hffffffff
  Next
End Sub

' Funkcja sprawdza, czy zbiór A jest pusty
' true  - tak, jest pusty
' false - nie, nie jest pusty
'-----------------------------------------
Function s_empty(ByRef A As s_set) As Integer
  Dim As Integer i
  Dim As UInteger m = A.T[0]      ' Pobieramy bity do m
  For i = 1 To A.nmax
  	 m Or= A.T[i]                  ' Sumujemy logicznie bity
  Next
  If m = 0 Then Return 1
  Return 0
End Function

' Funkcja bada, czy element x należy do zbioru A
' true  - tak, należy
' false - nie, nie należy
'-----------------------------------------------
Function s_isin(ByRef  A As s_set, ByVal x As Integer) As Integer
  Dim As Integer b = x - A.vmin   ' Obliczamy numer bitu w mapie bitowej
  If A.T[b Shr 5] And (1 Shl (b And 31)) Then Return 1
  Return 0
End Function

' Procedura wyświetla elementy zbioru A
'--------------------------------------
Sub s_print(ByRef A As s_set)
  Dim As Integer nb,i
  Dim As UInteger m

  For i = 0 To A.nmax
    nb = 0
    m = A.T[i]
    While m
      If (m And 1) = 1 Then Print Using "& ";(i Shl 5) + nb + A.vmin;
      m shr= 1
      nb += 1
    Wend
  Next
End Sub

' Procedura wyszukuje kliki maksymalne
'-------------------------------------
Sub BronKerbosch(ByRef SR As s_set, ByRef SP As s_set, ByRef SX As s_set)
  Dim As s_set RP,PP,XP
  Dim As slistEl Ptr p
  Dim As Integer v

  rcnt += 1                       ' Zwiększamy licznik wywołań rekurencyjnych

  If s_empty(SP) AndAlso s_empty(SX) Then  ' Jeśli zbiory SP i SX są puste,
                                  ' to SR zawiera wierzchołki kliki maksymalnej
    Print "MAXIMAL CLIQUE: ";
    s_print(SR)
    Print
  Else
    s_create(RP,0,n-1)            ' Tworzymy puste zbiory pomocnicze
    s_create(PP,0,n-1)
    s_create(XP,0,n-1)
    For v = 0 To n - 1            ' Przechodzimy przez kolejne wierzchołki grafu
      If s_isin(SP,v) Then        ' Jeśli wierzchołek v jest w zbiorze SP, to
                                  ' go przetwarzamy
        s_clear(SN)               ' Najpierw zerujemy zbiór sąsiadów
        p = graf[v]               ' Przeglądamy listę sąsiedztwa wierzchołka v
        While p
          s_add(SN,p->v)          ' Każdego sąsiada umieszczamy w SN
          p = p->Next
        Wend
        s_copy(SR,RP)             ' W RP tworzymy zbiór SR z dodanym wierzchołkiem v
        s_add(RP,v)
        s_intersection(SP,SN,PP)  ' W PP tworzymy iloczyn SP i SN
        s_intersection(SX,SN,XP)  ' W XP tworzymy iloczyn SX i SN
        BronKerbosch(RP,PP,XP)    ' Wywołanie rekurencyjne
        s_remove(SP,v)            ' Z SP usuwamy wierzchołek v
        s_add(SX,v)               ' i dodajemy go do SX
      End If
    Next
    Delete [] RP.T                ' Usuwamy zbiory pomocnicze
    Delete [] PP.T
    Delete [] XP.T
  End If
End Sub

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

Dim As s_set SR,SP,SX
Dim As integer i,u,v
Dim As slistEl Ptr p,r

Open Cons For Input As #1

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

s_create(SR,0,n-1)                ' Tworzymy puste zbiory
s_create(SP,0,n-1)
s_create(SX,0,n-1)
s_create(SN,0,n-1)

graf = New slistEl Ptr [n]        ' Tworzymy tablicę list sąsiedztwa

For i = 0 To n - 1
  graf[i] = 0                     ' Zerujemy listy sąsiedztwa
Next

For i = 1 To m
  Input #1,u,v                    ' Wierzchołki krawędzi
  p = New slistEl                 ' Tworzymy element listy
  p->v = u
  p->next = graf[v]               ' Element dołączamy do listy sąsiadów v
  graf[v] = p

  p = New slistEl                 ' To samo dla krawędzi w drugą stronę
  p->v = v
  p->next = graf[u]               ' Element dołączamy do listy sąsiadów u
  graf[u] = p
Next

Close #1

s_full(SP)                        ' W zbiorze SP ustawiamy wszystkie wierzchołki

Print

BronKerbosch(SR,SP,SX)            ' Szukamy rekurencyjnie klik maksymalnych

Print
Print "RECURSIVE CALLS =";rcnt
Print

Delete [] SR.T                    ' Usuwamy zbiory
Delete [] SP.T
Delete [] SX.T
Delete [] SN.T

For v = 0 To n - 1                ' Usuwamy tablicę list sąsiedztwa
  p = graf[v]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [] graf

End
Wynik
8 19
0 1 0 2 0 5 0 6
1 2 1 3 1 5 1 6
2 4 2 5 2 6 2 7
3 4 3 6 3 7
4 6
5 6 5 7
6 7

MAXIMAL CLIQUE: 0 1 2 5 6
MAXIMAL CLIQUE: 1 3 6
MAXIMAL CLIQUE: 2 4 6
MAXIMAL CLIQUE: 2 5 6 7
MAXIMAL CLIQUE: 3 4 6
MAXIMAL CLIQUE: 3 6 7

RECURSIVE CALLS = 52

 

Rozwiązanie nr 2

Algorytm Brona-Kerboscha da się ulepszyć tak, aby wykonywał mniej wywołań rekurencyjnych. W tym celu przed wejściem do pętli rozwijającej zbiór P tworzymy sumę zbiorów P i X i znajdujemy w niej taki wierzchołek u, który posiada najwięcej sąsiadów w zbiorze P. Następnie zamiast iterować przez wierzchołki w P iterujemy przez kolejne wierzchołki różnicy zbiorów P i N(u), gdzie N(u) oznacza zbiór sąsiadów wierzchołka u, który nazywamy piwotem. Zbiór P \ N(u) zawiera mniej wierzchołków, zatem liczba wywołań rekurencyjnych spadnie.

 

Algorytm Brona-Kerboscha znajdowania wszystkich klik maksymalnych w grafie nieskierowanym - wersja nr 2

BronKerbosch(n,graf,R,P,X)
Wejście
n  –  liczba wierzchołków w grafie, n symbol C
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
R  –  zbiór wierzchołków, które są częściowym wynikiem znajdowania kliki
P  –  zbiór wierzchołków, które są kandydatami do rozważenia
X  –  zbiór wierzchołków pominiętych
Wyjście:
Wszystkie kliki maksymalne w grafie
Elementy pomocnicze:
u,v,w  –  numery wierzchołków grafu, u,v,w symbol C
P',P",R',X',N  –  pomocnicze zbiory wierzchołków
ncmax,nc  –  liczniki wierzchołków, ncmax,nc symbol C
Lista kroków:
K01: Jeśli (P jest pusty) (X jest pusty), to
    Pisz R i zakończ

; znaleziona klika maksymalna
K02: P" ← suma zbiorów P i X ; będziemy szukać piwota w sumie zbiorów P i X
K03: ncmax ← 0 ; zerujemy globalny licznik sąsiadów
K04: Dla każdego wierzchołka u w P" wykonuj K05...K07 ; przeglądamy graf, biorąc pod uwagę tylko wierzchołki w P
K05:     nc ← 0 ; zerujemy bieżący licznik sąsiadów
K06:     Dla każdego sąsiada w wierzchołka u wykonuj:
        Jeśli w należy do P, to ncnc + 1
; jeśli sąsiad jest w P, to zwiększamy bieżący licznik sąsiadów
K07:     Jeśli nc ncmax, to
        vu
        ncmaxnc
; jeśli wierzchołek u ma nie mniej sąsiadów niż jest w ncmax, to
; zapamiętujemy ten wierzchołek
; i zapamiętujemy liczbę jego sąsiadów
K08: P"P  
K09: Dla każdego sąsiada u wierzchołka v wykonuj:
    P"P" - u
; tworzymy zbiór P bez sąsiadów piwota
K10: Dla każdego wierzchołka v w P" wykonuj K11...K18  
K11:     Zeruj zbiór N  
K12:     Dla każdego sąsiada u wierzchołka v wykonuj:
        NN + u
; tworzymy zbiór sąsiadów
K13:     R'R + v ; w R' tworzymy zbiór R z dodanym wierzchołkiem v
K14:     P' ← iloczyn zbiorów P i N ; z P' usuwamy wierzchołki, które nie są sąsiadami v
K15:     X' ← iloczyn zbiorów X i N ; z X' usuwamy wierzchołki, które nie są sąsiadami v
K16:     BronKerbosch(n,graf,R',P',X') ; wywołanie rekurencyjne
K17:     PP - v ; ze zbioru P usuwamy wierzchołek v
K18:     RR + v ; do zbioru R dodajemy wierzchołek v
K19: 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 i wyszukuje w nim wszystkie kliki maksymalne za pomocą algorytmu Brona-Kerboscha. Zbiory zostały zaimplementowane w mapach bitowych.

Program dodatkowo wypisuje liczbę wywołań rekurencyjnych algorytmu Brona-Kerboscha dla celów porównawczych.

Przykładowe dane dla programu:

  8 19
0 1 0 2 0 5 0 6
1 2 1 3 1 5 1 6
2 4 2 5 2 6 2 7
3 4 3 6 3 7
4 6
5 6 5 7
6 7

 

Lazarus
// Algorytm Brona-Kerboscha z piwotem
// Data   : 15.07.2014
// (C)2014 mgr Jerzy Wałaszek
//-----------------------------------

program cliques;

// Definicja elementu listy sąsiedztwa
type
  PslistEl = ^slistEl;
  slistEl = record
    next : PslistEl;              // Następny element listy
    v : integer;                  // Wierzchołek docelowy
  end;

// Definicja struktury zbioru
  s_set =  record
    vmin  : integer;
    nmax  : integer;
    T     : array of cardinal;
  end;

// Zmienne globalne
var
  n,m  : integer;                 // Liczba wierzchołków i krawędzi grafu
  graf : array of PslistEl;       // Tablica list sąsiedztwa
  SN   : s_set;                   // Zbiór sąsiadów
  rcnt : integer;                 // Licznik wywołań rekurencyjnych

// Obsługa zbiorów

// Procedura dodaje element x do zbioru A
//---------------------------------------
procedure s_add(var A : s_set; x : integer);
var
  b,i : integer;
begin
  b := x - A.vmin;                // Obliczamy numer bitu
  i := b shr 5;                   // Obliczamy indeks
  A.T[i] := A.T[i] or (1 shl (b and 31)); // Ustawiamy bit na 1
end;

// Procedura usuwa element x ze zbioru
//------------------------------------
procedure s_remove(var A : s_set; x : integer);
var
  b,i : integer;
begin
  b := x - A.vmin;                // Obliczamy numer bitu
  i := b shr 5;                   // Obliczamy indeks
  A.T[i] := A.T[i] and not (1 shl (b and 31)); // Ustawiamy bit na 0
end;

// Procedura usuwa wszystkie elementy ze zbioru
//---------------------------------------------
procedure s_clear(var A : s_set);
var
  i : integer;
begin
  for i := 0 to A.nmax do A.T[i] := 0; // Zerujemy tablicę
end;

// Procedura tworzy zbiór
//-----------------------
procedure s_create(var A : s_set; vmin,vmax : integer);
begin
  A.vmin := vmin;                 // Wypełniamy strukturę danymi
  A.nmax := (vmax - vmin) shr 5;  // Indeks ostatniego elementu tablicy
  SetLength(A.T,A.nmax + 1);      // Tworzymy dynamicznie tablicę mapy bitowej
  s_clear(A);                     // Tworzymy zbiór pusty
end;

// Procedura wyznacza sumę zbiorów A i B
//--------------------------------------
procedure s_union(var A,B,C : s_set);
var
  i : integer;
begin
  for i := 0 to A.nmax do  C.T[i] := A.T[i] or B.T[i];
end;

// Procedura wyznacza część wspólną zbiorów A i B
//-----------------------------------------------
procedure s_intersection(var A,B,C : s_set);
var
  i : integer;
begin
  for i := 0 to A.nmax do  C.T[i] := A.T[i] and B.T[i];
end;

// Procedura kopiuje zbiór A do zbioru B
//--------------------------------------
procedure s_copy(var A,B : s_set);
var
  i : integer;
begin
  for i := 0 to A.nmax do B.T[i] := A.T[i];
end;

// Procedura ustawia zbiór pełny
procedure s_full(var A : s_set);
var
  i : integer;
begin
  for i := 0 to A.nmax do A.T[i] := $ffffffff;
end;

// Funkcja sprawdza, czy zbiór A jest pusty
// true  - tak, jest pusty
// false - nie, nie jest pusty
//-----------------------------------------
function s_empty(var A : s_set) : boolean;
var
  i : integer;
  m : cardinal;
begin
  m := A.T[0];                    // Pobieramy bity do m
  for i := 1 to A.nmax do
    m := m or A.T[i];             // Sumujemy logicznie bity
  s_empty := (m = 0);
end;

// Funkcja bada, czy element x należy do zbioru A
// true  - tak, należy
// false - nie, nie należy
//-----------------------------------------------
function s_isin(var A : s_set; x : integer) : boolean;
var
  b : integer;
begin
  b := x - A.vmin;                // Obliczamy numer bitu w mapie bitowej
  if A.T[b shr 5] and (1 shl (b and 31)) > 0 then Exit(true);
  s_isin := false;
end;

// Procedura wyświetla elementy zbioru A
//--------------------------------------
procedure s_print(var A : s_set);
var
  i,nb : integer;
  m : cardinal;
begin
  for i := 0 to A.nmax do
  begin
    nb := 0;
    m  := A.T[i];
    while m > 0 do
    begin
      if (m and 1) = 1 then write((i shl 5) + nb + A.vmin,' ');
      m := m shr 1;
      inc(nb);
    end
  end;
end;

// Procedura wyszukuje kliki maksymalne
//-------------------------------------
procedure BronKerbosch(var SR,SP,SX : s_set);
var
  RP,PP,XP,PPP : s_set;
  p : PslistEl;
  v,u,ncmax,nc : integer;
begin

  inc(rcnt);                      // Zwiększamy licznik wywołań rekurencyjnych

  if s_empty(SP) and s_empty(SX) then // Jeśli zbiory SP i SX są puste,
  begin                           // to SR zawiera wierzchołki kliki maksymalnej
    write('MAXIMAL CLIQUE: ');
    s_print(SR);
    writeln;
  end
  else
  begin
    s_create(PPP,0,n-1);          // Tworzymy zbiór pomocniczy PPP
    s_union(SP,SX,PPP);           // W PPP tworzymy sumę zbiorów SP i SX
    ncmax := 0;                   // Zerujemy licznik sąsiadów
    for u := 0 to n - 1 do        // Przechodzimy przez kolejne wierzchołki grafu
      if s_isin(PPP,u) then       // Jeśli wierzchołek jest w PPP, to przetwarzamy go
      begin
        nc := 0;                  // Zerujemy bieżący licznik sąsiadów
        p := graf[u];             // Badamy sąsiadów wierzchołka v
        while p <> nil do
        begin
          if s_isin(SP,p^.v) then inc(nc); // Jeśli sąsiad w SP, zwiększamy nc
          p := p^.next;           // Następny sąsiad
        end;
        if nc >= ncmax then       // Jeśli liczba sąsiadów w P jest większa od ncmax,
        begin
          v := u;                 // to zapamiętujemy wierzchołek
          ncmax := nc;            // oraz jego liczbę sąsiadów w P
        end;
      end;
    s_copy(SP,PPP);               // W PPP umieszczamy zbiór SP
    p := graf[v];
    while p <> nil do             // Przeglądamy listę sąsiadów piwota
    begin
      s_remove(PPP,p^.v);         // Z PPP usuwamy każdego sąsiada piwota
      p := p^.next;               // Następny sąsiad
    end;
    s_create(RP,0,n-1);           // Tworzymy puste zbiory pomocnicze
    s_create(PP,0,n-1);
    s_create(XP,0,n-1);
    for v := 0 to n - 1 do        // Przechodzimy przez kolejne wierzchołki grafu
      if s_isin(PPP,v) then       // Jeśli wierzchołek v jest w zbiorze PPP, to
      begin                       // go przetwarzamy
        s_clear(SN);              // Najpierw zerujemy zbiór sąsiadów
        p := graf[v];             // Przeglądamy listę sąsiedztwa wierzchołka v
        while p <> nil do
        begin
          s_add(SN,p^.v);         // Każdego sąsiada umieszczamy w SN
          p := p^.next;
        end;
        s_copy(SR,RP);            // W RP tworzymy zbiór SR z dodanym wierzchołkiem v
        s_add(RP,v);
        s_intersection(SP,SN,PP); // W PP tworzymy iloczyn SP i SN
        s_intersection(SX,SN,XP); // W XP tworzymy iloczyn SX i SN
        BronKerbosch(RP,PP,XP);   // Wywołanie rekurencyjne
        s_remove(SP,v);           // Z SP usuwamy wierzchołek v
        s_add(SX,v);              // i dodajemy go do SX
      end;
    SetLength(RP.T,0);            // Usuwamy zbiory pomocnicze
    SetLength(PP.T,0);
    SetLength(XP.T,0);
    SetLength(PPP.T,0);
  end;
end;

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

var
  SR,SP,SX : s_set;
  i,u,v : integer;
  p,r : PslistEl;
begin

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

  s_create(SR,0,n-1);             // Tworzymy puste zbiory
  s_create(SP,0,n-1);
  s_create(SX,0,n-1);
  s_create(SN,0,n-1);

  SetLength(graf,n);              // Tworzymy tablicę list sąsiedztwa

  for i := 0 to n - 1 do graf[i] := nil; // Zerujemy listy sąsiedztwa

  for i := 1 to m do
  begin
    read(u,v);                    // Wierzchołki krawędzi
    new(p);                       // Tworzymy element listy
    p^.v := u;
    p^.next := graf[v];           // Element dołączamy do listy sąsiadów v
    graf[v] := p;

    new(p);                       // To samo dla krawędzi w drugą stronę
    p^.v := v;
    p^.next := graf[u];           // Element dołączamy do listy sąsiadów u
    graf[u] := p;
  end;

  s_full(SP);                     // W zbiorze SP ustawiamy wszystkie wierzchołki

  writeln;

  rcnt := 0;                      // Zerujemy licznik wywołań rekurencyjnych

  BronKerbosch(SR,SP,SX);         // Szukamy rekurencyjnie klik maksymalnych

  writeln;
  writeln('RECURSIVE CALLS = ',rcnt);
  writeln;

  SetLength(SR.T,0);              // Usuwamy zbiory
  SetLength(SP.T,0);
  SetLength(SX.T,0);
  SetLength(SN.T,0);

  for v := 0 to n - 1 do          // Usuwamy tablicę list sąsiedztwa
  begin
    p := graf[v];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;

  SetLength(graf,0);

end.
Code::Blocks
// Algorytm Brona-Kerboscha z piwotem
// Data   : 15.07.2014
// (C)2014 mgr Jerzy Wałaszek
//-----------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Definicja elementu listy sąsiedztwa

struct slistEl
{
  slistEl *next;                  // Następny element listy
  int v;                          // Wierzchołek docelowy
};

// Definicja struktury zbioru

struct s_set
{
  int vmin,nmax;
  unsigned int *T;
};

// Zmienne globalne

int n,m;                          // Liczba wierzchołków i krawędzi grafu
slistEl ** graf;                  // Tablica list sąsiedztwa
s_set SN;                         // Zbiór sąsiadów
int rcnt = 0;                     // Licznik wywołań rekurencyjnych

// Procedura dodaje element x do zbioru A
//---------------------------------------
void s_add(s_set & A, int x)
{
  int b = x - A.vmin;             // Obliczamy numer bitu
  int i = b >> 5;                 // Obliczamy indeks
  A.T[i] |= 1 << (b & 31);        // Ustawiamy bit na 1
}

// Procedura usuwa element x ze zbioru
//------------------------------------
void s_remove(s_set & A, int x)
{
  int b = x - A.vmin;             // Obliczamy numer bitu
  int i = b >> 5;                 // Obliczamy indeks
  A.T[i] &= ~(1 << (b & 31));     // Ustawiamy bit na 0
}

// Procedura usuwa wszystkie elementy ze zbioru
//---------------------------------------------
void s_clear(s_set & A)
{
  for(int i = 0; i <= A.nmax; i++) A.T[i] = 0; // Zerujemy mapę bitową
}

// Procedura tworzy zbiór
//-----------------------
void s_create(s_set & A, int vmin, int vmax)
{
  A.vmin = vmin;                  // Wypełniamy strukturę danymi
  A.nmax = (vmax - vmin) >> 5;    // Indeks ostatniego elementu tablicy
  A.T = new unsigned int [A.nmax + 1]; // Tworzymy dynamicznie tablicę mapy bitowej
  s_clear(A);                     // Tworzymy zbiór pusty
}

// Procedura wyznacza sumę zbiorów A i B
//--------------------------------------
void s_union(s_set & A, s_set & B, s_set & C)
{
  for(int i = 0; i <= A.nmax; i++) C.T[i] = A.T[i] | B.T[i];
}

// Procedura wyznacza część wspólną zbiorów A i B
//-----------------------------------------------
void s_intersection(s_set & A, s_set & B, s_set & C)
{
  for(int i = 0; i <= A.nmax; i++) C.T[i] = A.T[i] & B.T[i];
}

// Procedura kopiuje zbiór A do zbioru B
//--------------------------------------
void s_copy(s_set & A, s_set & B)
{
  for(int i = 0; i <= A.nmax; i++) B.T[i] = A.T[i];
}

// Procedura ustawia zbiór pełny
void s_full(s_set & A)
{
  for(int i = 0; i <= A.nmax; i++) A.T[i] = 0xffffffff;
}

// Funkcja sprawdza, czy zbiór A jest pusty
// true  - tak, jest pusty
// false - nie, nie jest pusty
//-----------------------------------------
bool s_empty(s_set A)
{
  unsigned int m = A.T[0];        // Pobieramy bity do m
  for(int i = 1; i <= A.nmax; i++) m |= A.T[i]; // Sumujemy logicznie bity
  return (m == 0);
}

// Funkcja bada, czy element x należy do zbioru A
// true  - tak, należy
// false - nie, nie należy
//-----------------------------------------------
bool s_isin(s_set & A, int x)
{
  int b = x - A.vmin;             // Obliczamy numer bitu w mapie bitowej
  if(A.T[b >> 5] & (1 << (b & 31))) return true;
  return false;
}

// Procedura wyświetla elementy zbioru A
//--------------------------------------
void s_print(s_set A)
{
  int nb;
  unsigned int m;

  for(int i = 0; i <= A.nmax; i++)
    for(nb = 0,m = A.T[i]; m; m >>= 1,nb++)
      if(m & 1) cout << (i << 5) + nb + A.vmin << " ";
}

// Procedura wyszukuje kliki maksymalne
//-------------------------------------
void BronKerbosch(s_set & SR, s_set & SP, s_set & SX)
{
  s_set RP,PP,XP,PPP;
  slistEl * p;
  int v,u,ncmax,nc;

  rcnt++;                         // Zwiększamy licznik wywołań rekurencyjnych

  if(s_empty(SP) && s_empty(SX))  // Jeśli zbiory SP i SX są puste,
  {                               // to SR zawiera wierzchołki kliki maksymalnej
    cout << "MAXIMAL CLIQUE: ";
    s_print(SR);
    cout << endl;
  }
  else
  {
    s_create(PPP,0,n-1);          // Tworzymy zbiór pomocniczy PPP
    s_union(SP,SX,PPP);           // W PPP tworzymy sumę zbiorów SP i SX
    ncmax = 0;                    // Zerujemy licznik sąsiadów
    for(u = 0; u < n; u++)        // Przechodzimy przez kolejne wierzchołki grafu
      if(s_isin(PPP,u))           // Jeśli wierzchołek jest w PPP, to przetwarzamy go
      {
        nc = 0;                   // Zerujemy bieżący licznik sąsiadów
        for(p = graf[u]; p; p = p->next) // Badamy sąsiadów wierzchołka v
          if(s_isin(SP,p->v)) nc++; // Jeśli sąsiad w SP, zwiększamy nc
        if(nc >= ncmax)           // Jeśli liczba sąsiadów w P jest większa od ncmax,
        {
          v = u;                  // to zapamiętujemy wierzchołek
          ncmax = nc;             // oraz jego liczbę sąsiadów w P
        }
      }
    s_copy(SP,PPP);               // W PPP umieszczamy zbiór SP
    for(p = graf[v]; p; p = p->next) // Przeglądamy listę sąsiadów piwota
      s_remove(PPP,p->v);         // Z PPP usuwamy każdego sąsiada piwota
    s_create(RP,0,n-1);           // Tworzymy puste zbiory pomocnicze
    s_create(PP,0,n-1);
    s_create(XP,0,n-1);
    for(v = 0; v < n; v++)        // Przechodzimy przez kolejne wierzchołki grafu
      if(s_isin(PPP,v))           // Jeśli wierzchołek v jest w zbiorze PPP, to
      {                           // go przetwarzamy
        s_clear(SN);              // Najpierw zerujemy zbiór sąsiadów
        for(p = graf[v];p;p = p->next) // Przeglądamy listę sąsiedztwa wierzchołka v
          s_add(SN,p->v);         // Każdego sąsiada umieszczamy w SN
        s_copy(SR,RP);            // W RP tworzymy zbiór SR z dodanym wierzchołkiem v
        s_add(RP,v);
        s_intersection(SP,SN,PP); // W PP tworzymy iloczyn SP i SN
        s_intersection(SX,SN,XP); // W XP tworzymy iloczyn SX i SN
        BronKerbosch(RP,PP,XP);   // Wywołanie rekurencyjne
        s_remove(SP,v);           // Z SP usuwamy wierzchołek v
        s_add(SX,v);              // i dodajemy go do SX
      }
    delete [] RP.T;              // Usuwamy zbiory pomocnicze
    delete [] PP.T;
    delete [] XP.T;
    delete [] PPP.T;
  }
}

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

int main()
{
  s_set SR,SP,SX;
  int i,u,v;
  slistEl *p,*r;

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

  s_create(SR,0,n-1);             // Tworzymy puste zbiory
  s_create(SP,0,n-1);
  s_create(SX,0,n-1);
  s_create(SN,0,n-1);

  graf = new slistEl * [n];       // Tworzymy tablicę list sąsiedztwa

  for(i = 0; i < n; i++) graf[i] = NULL; // Zerujemy listy sąsiedztwa

  for(i = 0; i < m; i++)
  {
    cin >> u >> v;                // Wierzchołki krawędzi
    p = new slistEl;              // Tworzymy element listy
    p->v = u;
    p->next = graf[v];            // Element dołączamy do listy sąsiadów v
    graf[v] = p;

    p = new slistEl;              // To samo dla krawędzi w drugą stronę
    p->v = v;
    p->next = graf[u];            // Element dołączamy do listy sąsiadów u
    graf[u] = p;
  }

  s_full(SP);                     // W zbiorze SP ustawiamy wszystkie wierzchołki

  cout << endl;

  BronKerbosch(SR,SP,SX);         // Szukamy rekurencyjnie klik maksymalnych

  cout << endl << "RECURSIVE CALLS = " << rcnt << endl << endl;

  delete [] SR.T;                 // Usuwamy zbiory
  delete [] SP.T;
  delete [] SX.T;
  delete [] SN.T;

  for(v = 0; v < n; v++)          // Usuwamy tablicę list sąsiedztwa
  {
    p = graf[v];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }

  delete [] graf;

  return 0;
}
Free Basic
' Algorytm Brona-Kerboscha z piwotem
' Data   : 15.07.2014
' (C)2014 mgr Jerzy Wałaszek
'-----------------------------------

' Definicja elementu listy sąsiedztwa

Type slistEl
  next As slistEl Ptr             ' Następny element listy
  v As Integer                    ' Wierzchołek docelowy
End Type

' Definicja struktury zbioru

Type s_set
  vmin As Integer
  nmax As Integer
  T As UInteger Ptr
End Type

' Zmienne globalne

Dim Shared As Integer n,m         ' Liczba wierzchołków i krawędzi grafu
Dim Shared As slistEl Ptr Ptr graf ' Tablica list sąsiedztwa
Dim Shared As s_set SN            ' Zbiór sąsiadów
Dim Shared As Integer rcnt = 0    ' Licznik wywołań rekurencyjnych

' Obsługa zbiorów

' Procedura dodaje element x do zbioru A
'---------------------------------------
Sub s_add(ByRef A As s_set, ByVal x As Integer)
  Dim As Integer b,i

  b = x - A.vmin                  ' Obliczamy numer bitu
  i = b Shr 5                     ' Obliczamy indeks
  A.T[i] = A.T[i] or (1 Shl (b and 31)) ' Ustawiamy bit na 1
End Sub

' Procedura usuwa element x ze zbioru
'------------------------------------
Sub s_remove(ByRef A As s_set, ByVal x As Integer)
  Dim As Integer b,i

  b = x - A.vmin                  ' Obliczamy numer bitu
  i = b Shr 5                     ' Obliczamy indeks
  A.T[i] = A.T[i] And Not (1 Shl (b and 31)) ' Ustawiamy bit na 0
End Sub

' Procedura usuwa wszystkie elementy ze zbioru
'---------------------------------------------
Sub s_clear(ByRef A As s_set)
  Dim As Integer i
  For i = 0 To A.nmax
  	 A.T[i] = 0                    ' Zerujemy mapę bitową
  Next
End Sub

' Procedura tworzy zbiór
'-----------------------
Sub s_create(ByRef A As s_set, ByVal vmin As Integer, ByVal vmax As Integer)
  A.vmin = vmin                   ' Wypełniamy strukturę danymi
  A.nmax = (vmax - vmin) shr 5    ' Indeks ostatniego elementu tablicy
  A.T = New UInteger [A.nmax + 1] ' Tworzymy dynamicznie tablicę mapy bitowej
  s_clear(A)                      ' Tworzymy zbiór pusty
End Sub

' Procedura wyznacza sumę zbiorów A i B
'--------------------------------------
Sub s_union(ByRef A As s_set, ByRef B As s_set, ByRef C As s_set)
  Dim As Integer i

  For i = 0 To A.nmax
  	 C.T[i] = A.T[i] Or B.T[i]
  Next
End Sub

' Procedura wyznacza część wspólną zbiorów A i B
'-----------------------------------------------
Sub s_intersection(ByRef A As s_set, ByRef B As s_set, ByRef C As s_set)
  Dim As Integer i

  For i = 0 To A.nmax
  	 C.T[i] = A.T[i] And B.T[i]
  Next
End Sub

' Procedura kopiuje zbiór A do zbioru B
'--------------------------------------
Sub s_copy(ByRef A As s_set, ByRef B As s_set)
  Dim As Integer i
  For i= 0 To A.nmax
  	 B.T[i] = A.T[i]
  Next
End Sub

' Procedura ustawia zbiór pełny
'------------------------------
Sub s_full(ByRef A As s_set)
  Dim As Integer i
  For i = 0 To A.nmax
  	 A.T[i] = &Hffffffff
  Next
End Sub

' Funkcja sprawdza, czy zbiór A jest pusty
' true  - tak, jest pusty
' false - nie, nie jest pusty
'-----------------------------------------
Function s_empty(ByRef A As s_set) As Integer
  Dim As Integer i
  Dim As UInteger m = A.T[0]      ' Pobieramy bity do m
  For i = 1 To A.nmax
  	 m Or= A.T[i]                  ' Sumujemy logicznie bity
  Next
  If m = 0 Then Return 1
  Return 0
End Function

' Funkcja bada, czy element x należy do zbioru A
' true  - tak, należy
' false - nie, nie należy
'-----------------------------------------------
Function s_isin(ByRef  A As s_set, ByVal x As Integer) As Integer
  Dim As Integer b = x - A.vmin   ' Obliczamy numer bitu w mapie bitowej
  If A.T[b Shr 5] And (1 Shl (b And 31)) Then Return 1
  Return 0
End Function

' Procedura wyświetla elementy zbioru A
'--------------------------------------
Sub s_print(ByRef A As s_set)
  Dim As Integer nb,i
  Dim As UInteger m

  For i = 0 To A.nmax
    nb = 0
    m = A.T[i]
    While m
      If (m And 1) = 1 Then Print Using "& ";(i Shl 5) + nb + A.vmin;
      m shr= 1
      nb += 1
    Wend
  Next
End Sub

' Procedura wyszukuje kliki maksymalne
'-------------------------------------
Sub BronKerbosch(ByRef SR As s_set, ByRef SP As s_set, ByRef SX As s_set)
  Dim As s_set RP,PP,XP,PPP
  Dim As slistEl Ptr p
  Dim As Integer v,u,ncmax,nc

  rcnt += 1                       ' Zwiększamy licznik wywołań rekurencyjnych

  If s_empty(SP) AndAlso s_empty(SX) Then  ' Jeśli zbiory SP i SX są puste,
                                  ' to SR zawiera wierzchołki kliki maksymalnej
    Print "MAXIMAL CLIQUE: ";
    s_print(SR)
    Print
  Else
    s_create(PPP,0,n-1)           ' Tworzymy zbiór pomocniczy PPP
    s_union(SP,SX,PPP)            ' W PPP tworzymy sumę zbiorów SP i SX
    ncmax = 0                     ' Zerujemy licznik sąsiadów
    For u = 0 To n - 1            ' Przechodzimy przez kolejne wierzchołki grafu
      If s_isin(PPP,u) Then       ' Jeśli wierzchołek jest w PPP, to przetwarzamy go
        nc = 0                    ' Zerujemy bieżący licznik sąsiadów
        p = graf[u]
        While p                   ' Badamy sąsiadów wierzchołka v
          If s_isin(SP,p->v) Then nc += 1 ' Jeśli sąsiad w SP, zwiększamy nc
          p = p->Next             ' Następny sąsiad
        Wend
        If nc >= ncmax Then       ' Jeśli liczba sąsiadów w P jest większa od ncmax,
          v = u                   ' to zapamiętujemy wierzchołek
          ncmax = nc              ' oraz jego liczbę sąsiadów w P
        End If
      End If
    Next
    s_copy(SP,PPP)                ' W PPP umieszczamy zbiór SP
    p = graf[v]
    While p                       ' Przeglądamy listę sąsiadów piwota
      s_remove(PPP,p->v)          ' Z PPP usuwamy każdego sąsiada piwota
      p = p->Next                 ' Następny sąsiad
    Wend
    s_create(RP,0,n-1)            ' Tworzymy puste zbiory pomocnicze
    s_create(PP,0,n-1)
    s_create(XP,0,n-1)
    For v = 0 To n - 1            ' Przechodzimy przez kolejne wierzchołki grafu
      If s_isin(PPP,v) Then       ' Jeśli wierzchołek v jest w zbiorze PPP, to
                                  ' go przetwarzamy
        s_clear(SN)               ' Najpierw zerujemy zbiór sąsiadów
        p = graf[v]               ' Przeglądamy listę sąsiedztwa wierzchołka v
        While p
          s_add(SN,p->v)          ' Każdego sąsiada umieszczamy w SN
          p = p->Next
        Wend
        s_copy(SR,RP)             ' W RP tworzymy zbiór SR z dodanym wierzchołkiem v
        s_add(RP,v)
        s_intersection(SP,SN,PP)  ' W PP tworzymy iloczyn SP i SN
        s_intersection(SX,SN,XP)  ' W XP tworzymy iloczyn SX i SN
        BronKerbosch(RP,PP,XP)    ' Wywołanie rekurencyjne
        s_remove(SP,v)            ' Z SP usuwamy wierzchołek v
        s_add(SX,v)               ' i dodajemy go do SX
      End If
    Next
    Delete [] RP.T                ' Usuwamy zbiory pomocnicze
    Delete [] PP.T
    Delete [] XP.T
    Delete [] PPP.T
  End If
End Sub

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

Dim As s_set SR,SP,SX
Dim As integer i,u,v
Dim As slistEl Ptr p,r

Open Cons For Input As #1

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

s_create(SR,0,n-1)                ' Tworzymy puste zbiory
s_create(SP,0,n-1)
s_create(SX,0,n-1)
s_create(SN,0,n-1)

graf = New slistEl Ptr [n]        ' Tworzymy tablicę list sąsiedztwa

For i = 0 To n - 1
  graf[i] = 0                     ' Zerujemy listy sąsiedztwa
Next

For i = 1 To m
  Input #1,u,v                    ' Wierzchołki krawędzi
  p = New slistEl                 ' Tworzymy element listy
  p->v = u
  p->next = graf[v]               ' Element dołączamy do listy sąsiadów v
  graf[v] = p

  p = New slistEl                 ' To samo dla krawędzi w drugą stronę
  p->v = v
  p->next = graf[u]               ' Element dołączamy do listy sąsiadów u
  graf[u] = p
Next

Close #1

s_full(SP)                        ' W zbiorze SP ustawiamy wszystkie wierzchołki

Print

BronKerbosch(SR,SP,SX)            ' Szukamy rekurencyjnie klik maksymalnych

Print
Print "RECURSIVE CALLS =";rcnt
Print

Delete [] SR.T                    ' Usuwamy zbiory
Delete [] SP.T
Delete [] SX.T
Delete [] SN.T

For v = 0 To n - 1                ' Usuwamy tablicę list sąsiedztwa
  p = graf[v]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [] graf

End
Wynik
8 19
0 1 0 2 0 5 0 6
1 2 1 3 1 5 1 6
2 4 2 5 2 6 2 7
3 4 3 6 3 7
4 6
5 6 5 7
6 7

MAXIMAL CLIQUE: 2 4 6
MAXIMAL CLIQUE: 0 1 2 5 6
MAXIMAL CLIQUE: 2 5 6 7
MAXIMAL CLIQUE: 1 3 6
MAXIMAL CLIQUE: 3 4 6
MAXIMAL CLIQUE: 3 6 7

RECURSIVE CALLS = 12

 

W pierwszej wersji liczba wywołań rekurencyjnych wynosiła 52. Tutaj mamy 12.

 

Klika największa

Algorytm Brona-Kerboscha da się łatwo przystosować do wyszukiwania kliki największej. W tym celu w tworzymy pusty zbiór RM, który będzie zapamiętywał klikę największą. Następnie w pierwszej części algorytmu Brona-Kerbosha, gdy zbiory P i X są zerowe, nie wypisujemy zbioru R, lecz sprawdzamy, czy jego liczebność jest większa od liczebności zbioru RM. Jeśli tak, to zbiór R kopiujemy do RM. Aby nie zliczać ciągle elementów zbiorów, można w osobnej zmiennej zapamiętywać ich liczebność. Gdy algorytm Brona-Kerboscha zakończy działanie, w zbiorze RM będzie największa klika grafu.

 

Algorytm Brona-Kerboscha znajdowania kliki największej w grafie nieskierowanym

BronKerbosch(n,graf,R,P,X,RM,rmsize)

Przy pierwszym wywołaniu zbiór RM powinien być pusty, a rmsize powinno zawierać 0. Oba te elementy mogą być globalne, aby zaoszczędzić pamięć na przekazywanie parametrów.

Wejście
n  –  liczba wierzchołków w grafie, n symbol C
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
R  –  zbiór wierzchołków, które są częściowym wynikiem znajdowania kliki
P  –  zbiór wierzchołków, które są kandydatami do rozważenia
X  –  zbiór wierzchołków pominiętych
RM  –  zbiór dotychczasowej kliki największej
rmsize  –  rozmiar dotychczasowej kliki największej, rmsize symbol C
Wyjście:
Zbiór RM zawiera klikę największą. W zmiennej rmsize zostaje umieszczony rozmiar tej kliki.
Elementy pomocnicze:
u,v,w  –  numery wierzchołków grafu, u,v,w symbol C
P',P",R',X',N  –  pomocnicze zbiory wierzchołków
ncmax,nc  –  liczniki wierzchołków, ncmax,nc symbol C
rms  –  liczba wierzchołków w zbiorze R, rms symbol C
Lista kroków:
K01: Jeśli (P nie jest pusty) (X nie jest pusty), to idź do K05 ; znaleziona klika maksymalna
K02: rms ← rozmiar R ; wyznaczamy liczbę wierzchołków w klice maksymalnej
K03: Jeśli rms > rmsize, to
    RMR
    rmsizerms
; sprawdzamy, czy obecna klika jest większa od pamiętanej
; jeśli tak, to zapamiętaj klikę
; oraz jej nowy rozmiar
K04 Zakończ  
K05: P" ← suma zbiorów P i X ; będziemy szukać piwota w sumie zbiorów P i X
K06: ncmax ← 0 ; zerujemy globalny licznik sąsiadów
K07: Dla każdego wierzchołka u w P" wykonuj K08...K10 ; przeglądamy graf, biorąc pod uwagę tylko wierzchołki w P
K08:     nc ← 0 ; zerujemy bieżący licznik sąsiadów
K09:     Dla każdego sąsiada w wierzchołka u wykonuj:
        Jeśli w należy do P, to ncnc + 1
; jeśli sąsiad jest w P, to zwiększamy bieżący licznik sąsiadów
K10:     Jeśli nc ncmax, to
        vu
        ncmaxnc
; jeśli wierzchołek u ma nie mniej sąsiadów niż jest w ncmax, to
; zapamiętujemy ten wierzchołek
; i zapamiętujemy liczbę jego sąsiadów
K11: P"P  
K12: Dla każdego sąsiada u wierzchołka v wykonuj:
    P"P" - u
; tworzymy zbiór P bez sąsiadów piwota
K13: Dla każdego wierzchołka v w P" wykonuj K14...K21  
K14:     Zeruj zbiór N  
K15:     Dla każdego sąsiada u wierzchołka v wykonuj:
        NN + u
; tworzymy zbiór sąsiadów
K16:     R'R + v ; w R' tworzymy zbiór R z dodanym wierzchołkiem v
K17:     P' ← iloczyn zbiorów P i N ; z P' usuwamy wierzchołki, które nie są sąsiadami v
K18:     X' ← iloczyn zbiorów X i N ; z X' usuwamy wierzchołki, które nie są sąsiadami v
K19:     BronKerbosch(n,graf,R',P',X') ; wywołanie rekurencyjne
K20:     PP - v ; ze zbioru P usuwamy wierzchołek v
K21:     RR + v ; do zbioru R dodajemy wierzchołek v
K22: 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 i wyszukuje w nim wszystkie kliki maksymalne za pomocą algorytmu Brona-Kerboscha. Zbiory zostały zaimplementowane w mapach bitowych.

Program dodatkowo wypisuje liczbę wywołań rekurencyjnych algorytmu Brona-Kerboscha dla celów porównawczych.

Przykładowe dane dla programu:

  8 19
0 1 0 2 0 5 0 6
1 2 1 3 1 5 1 6
2 4 2 5 2 6 2 7
3 4 3 6 3 7
4 6
5 6 5 7
6 7

 

Lazarus
// Wyszukiwanie kliki największej
// Data   : 15.07.2014
// (C)2014 mgr Jerzy Wałaszek
//-------------------------------

program cliques;

// Definicja elementu listy sąsiedztwa
type
  PslistEl = ^slistEl;
  slistEl = record
    next : PslistEl;              // Następny element listy
    v : integer;                  // Wierzchołek docelowy
  end;

// Definicja struktury zbioru
  s_set =  record
    vmin  : integer;
    nmax  : integer;
    T     : array of cardinal;
  end;

// Zmienne globalne
var
  n,m   : integer;                // Liczba wierzchołków i krawędzi grafu
  graf  : array of PslistEl;      // Tablica list sąsiedztwa
  SN,RM : s_set;                  // Zbiór sąsiadów i zbiór kliki największej
  rmsize: integer;                // Liczba wierzchołków w klice największej

// Obsługa zbiorów

// Procedura dodaje element x do zbioru A
//---------------------------------------
procedure s_add(var A : s_set; x : integer);
var
  b,i : integer;
begin
  b := x - A.vmin;                // Obliczamy numer bitu
  i := b shr 5;                   // Obliczamy indeks
  A.T[i] := A.T[i] or (1 shl (b and 31)); // Ustawiamy bit na 1
end;

// Procedura usuwa element x ze zbioru
//------------------------------------
procedure s_remove(var A : s_set; x : integer);
var
  b,i : integer;
begin
  b := x - A.vmin;                // Obliczamy numer bitu
  i := b shr 5;                   // Obliczamy indeks
  A.T[i] := A.T[i] and not (1 shl (b and 31)); // Ustawiamy bit na 0
end;

// Procedura usuwa wszystkie elementy ze zbioru
//---------------------------------------------
procedure s_clear(var A : s_set);
var
  i : integer;
begin
  for i := 0 to A.nmax do A.T[i] := 0; // Zerujemy tablicę
end;

// Procedura tworzy zbiór
//-----------------------
procedure s_create(var A : s_set; vmin,vmax : integer);
begin
  A.vmin := vmin;                 // Wypełniamy strukturę danymi
  A.nmax := (vmax - vmin) shr 5;  // Indeks ostatniego elementu tablicy
  SetLength(A.T,A.nmax + 1);      // Tworzymy dynamicznie tablicę mapy bitowej
  s_clear(A);                     // Tworzymy zbiór pusty
end;

// Procedura wyznacza sumę zbiorów A i B
//--------------------------------------
procedure s_union(var A,B,C : s_set);
var
  i : integer;
begin
  for i := 0 to A.nmax do  C.T[i] := A.T[i] or B.T[i];
end;

// Procedura wyznacza część wspólną zbiorów A i B
//-----------------------------------------------
procedure s_intersection(var A,B,C : s_set);
var
  i : integer;
begin
  for i := 0 to A.nmax do  C.T[i] := A.T[i] and B.T[i];
end;

// Procedura kopiuje zbiór A do zbioru B
//--------------------------------------
procedure s_copy(var A,B : s_set);
var
  i : integer;
begin
  for i := 0 to A.nmax do B.T[i] := A.T[i];
end;

// Procedura ustawia zbiór pełny
procedure s_full(var A : s_set);
var
  i : integer;
begin
  for i := 0 to A.nmax do A.T[i] := $ffffffff;
end;

// Funkcja sprawdza, czy zbiór A jest pusty
// true  - tak, jest pusty
// false - nie, nie jest pusty
//-----------------------------------------
function s_empty(var A : s_set) : boolean;
var
  i : integer;
  m : cardinal;
begin
  m := A.T[0];                    // Pobieramy bity do m
  for i := 1 to A.nmax do
    m := m or A.T[i];             // Sumujemy logicznie bity
  s_empty := (m = 0);
end;

// Funkcja bada, czy element x należy do zbioru A
// true  - tak, należy
// false - nie, nie należy
//-----------------------------------------------
function s_isin(var A : s_set; x : integer) : boolean;
var
  b : integer;
begin
  b := x - A.vmin;                // Obliczamy numer bitu w mapie bitowej
  if A.T[b shr 5] and (1 shl (b and 31)) > 0 then Exit(true);
  s_isin := false;
end;

// Procedura wyświetla elementy zbioru A
//--------------------------------------
procedure s_print(var A : s_set);
var
  i,nb : integer;
  m : cardinal;
begin
  for i := 0 to A.nmax do
  begin
    nb := 0;
    m  := A.T[i];
    while m > 0 do
    begin
      if (m and 1) = 1 then write((i shl 5) + nb + A.vmin,' ');
      m := m shr 1;
      inc(nb);
    end
  end;
end;

// Funkcja oblicza liczbę elementów w A
//-------------------------------------
function s_size(var A : s_set) : integer;
var
  i,c : integer;
  m   : cardinal;
begin
  c := 0;                         // Zerujemy licznik
  for i := 0 to A.nmax do         // Przechodzimy przez kolejne komórki
  begin
    m := A.T[i];                  // Pobieramy bity do m
    while m > 0 do                // Zliczamy bity równe 1
    begin
      if (m and 1) = 1 then inc(c);
      m := m shr 1;
    end;
  end;
  s_size := c;
end;

// Procedura wyszukuje klikę największą
//-------------------------------------
procedure BronKerbosch(var SR,SP,SX : s_set);
var
  RP,PP,XP,PPP : s_set;
  p : PslistEl;
  v,u,ncmax,nc,rms : integer;
begin
  if s_empty(SP) and s_empty(SX) then // Jeśli zbiory SP i SX są puste,
  begin                           // to SR zawiera wierzchołki kliki maksymalnej
   rms := s_size(SR);             // Wyznaczamy liczbę wierzchołków w klice
   if rms > rmsize then           // Jeśli mamy większą klikę od dotychczas znalezionej,
   begin
     s_copy(SR,RM);               // to zapamiętujemy ją
     rmsize := rms;               // Zapamiętujemy również jej rozmiar
   end;
  end
  else
  begin
    s_create(PPP,0,n-1);          // Tworzymy zbiór pomocniczy PPP
    s_union(SP,SX,PPP);           // W PPP tworzymy sumę zbiorów SP i SX
    ncmax := 0;                   // Zerujemy licznik sąsiadów
    for u := 0 to n - 1 do        // Przechodzimy przez kolejne wierzchołki grafu
      if s_isin(PPP,u) then       // Jeśli wierzchołek jest w PPP, to przetwarzamy go
      begin
        nc := 0;                  // Zerujemy bieżący licznik sąsiadów
        p := graf[u];             // Badamy sąsiadów wierzchołka v
        while p <> nil do
        begin
          if s_isin(SP,p^.v) then inc(nc); // Jeśli sąsiad w SP, zwiększamy nc
          p := p^.next;           // Następny sąsiad
        end;
        if nc >= ncmax then       // Jeśli liczba sąsiadów w P jest większa od ncmax,
        begin
          v := u;                 // to zapamiętujemy wierzchołek
          ncmax := nc;            // oraz jego liczbę sąsiadów w P
        end;
      end;
    s_copy(SP,PPP);               // W PPP umieszczamy zbiór SP
    p := graf[v];
    while p <> nil do             // przeglądamy listę sąsiadów piwota
    begin
      s_remove(PPP,p^.v);         // Z PPP usuwamy każdego sąsiada piwota
      p := p^.next;               // Następny sąsiad
    end;
    s_create(RP,0,n-1);           // Tworzymy puste zbiory pomocnicze
    s_create(PP,0,n-1);
    s_create(XP,0,n-1);
    for v := 0 to n - 1 do        // Przechodzimy przez kolejne wierzchołki grafu
      if s_isin(PPP,v) then       // Jeśli wierzchołek v jest w zbiorze PPP, to
      begin                       // go przetwarzamy
        s_clear(SN);              // Najpierw zerujemy zbiór sąsiadów
        p := graf[v];             // Przeglądamy listę sąsiedztwa wierzchołka v
        while p <> nil do
        begin
          s_add(SN,p^.v);         // Każdego sąsiada umieszczamy w SN
          p := p^.next;
        end;
        s_copy(SR,RP);            // W RP tworzymy zbiór SR z dodanym wierzchołkiem v
        s_add(RP,v);
        s_intersection(SP,SN,PP); // W PP tworzymy iloczyn SP i SN
        s_intersection(SX,SN,XP); // W XP tworzymy iloczyn SX i SN
        BronKerbosch(RP,PP,XP);   // Wywołanie rekurencyjne
        s_remove(SP,v);           // Z SP usuwamy wierzchołek v
        s_add(SX,v);              // i dodajemy go do SX
      end;
    SetLength(RP.T,0);            // Usuwamy zbiory pomocnicze
    SetLength(PP.T,0);
    SetLength(XP.T,0);
    SetLength(PPP.T,0);
  end;
end;

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

var
  SR,SP,SX : s_set;
  i,u,v : integer;
  p,r : PslistEl;
begin

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

  s_create(SR,0,n-1);             // Tworzymy puste zbiory
  s_create(SP,0,n-1);
  s_create(SX,0,n-1);
  s_create(SN,0,n-1);
  s_create(RM,0,n-1);             // Pusty zbiór kliki największej

  rmsize := 0;                    // Liczba wierzchołków w klice największej

  SetLength(graf,n);              // Tworzymy tablicę list sąsiedztwa

  for i := 0 to n - 1 do graf[i] := nil; // Zerujemy listy sąsiedztwa

  for i := 1 to m do
  begin
    read(u,v);                    // Wierzchołki krawędzi
    new(p);                       // Tworzymy element listy
    p^.v := u;
    p^.next := graf[v];           // Element dołączamy do listy sąsiadów v
    graf[v] := p;

    new(p);                       // To samo dla krawędzi w drugą stronę
    p^.v := v;
    p^.next := graf[u];           // Element dołączamy do listy sąsiadów u
    graf[u] := p;
  end;

  s_full(SP);                     // W zbiorze SP ustawiamy wszystkie wierzchołki

  writeln;

  BronKerbosch(SR,SP,SX);         // Szukamy rekurencyjnie kliki największej

  write('MAXIMUM CLIQUE: ');
  s_print(RM); writeln;
  writeln('NUMBER OF VERTICES IN MAXIMUM CLIQUE = ',rmsize);
  writeln;

  SetLength(SR.T,0);              // Usuwamy zbiory
  SetLength(SP.T,0);
  SetLength(SX.T,0);
  SetLength(SN.T,0);
  SetLength(RM.T,0);

  for v := 0 to n - 1 do          // Usuwamy tablicę list sąsiedztwa
  begin
    p := graf[v];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;

  SetLength(graf,0);

end.
Code::Blocks
// Wyszukiwanie kliki największej
// Data   : 15.07.2014
// (C)2014 mgr Jerzy Wałaszek
//-------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Definicja elementu listy sąsiedztwa

struct slistEl
{
  slistEl *next;                  // Następny element listy
  int v;                          // Wierzchołek docelowy
};

// Definicja struktury zbioru

struct s_set
{
  int vmin,nmax;
  unsigned int *T;
};

// Zmienne globalne

int n,m;                          // Liczba wierzchołków i krawędzi grafu
slistEl ** graf;                  // Tablica list sąsiedztwa
s_set SN,RM;                      // Zbiór sąsiadów i zbiór kliki największej
int rmsize;                       // Liczba wierzchołków w klice największej

// Procedura dodaje element x do zbioru A
//---------------------------------------
void s_add(s_set & A, int x)
{
  int b = x - A.vmin;             // Obliczamy numer bitu
  int i = b >> 5;                 // Obliczamy indeks
  A.T[i] |= 1 << (b & 31);        // Ustawiamy bit na 1
}

// Procedura usuwa element x ze zbioru
//------------------------------------
void s_remove(s_set & A, int x)
{
  int b = x - A.vmin;             // Obliczamy numer bitu
  int i = b >> 5;                 // Obliczamy indeks
  A.T[i] &= ~(1 << (b & 31));     // Ustawiamy bit na 0
}

// Procedura usuwa wszystkie elementy ze zbioru
//---------------------------------------------
void s_clear(s_set & A)
{
  for(int i = 0; i <= A.nmax; i++) A.T[i] = 0; // Zerujemy mapę bitową
}

// Procedura tworzy zbiór
//-----------------------
void s_create(s_set & A, int vmin, int vmax)
{
  A.vmin = vmin;                  // Wypełniamy strukturę danymi
  A.nmax = (vmax - vmin) >> 5;    // Indeks ostatniego elementu tablicy
  A.T = new unsigned int [A.nmax + 1];  // Tworzymy dynamicznie tablicę mapy bitowej
  s_clear(A);                     // Tworzymy zbiór pusty
}

// Procedura wyznacza sumę zbiorów A i B
//--------------------------------------
void s_union(s_set & A, s_set & B, s_set & C)
{
  for(int i = 0; i <= A.nmax; i++) C.T[i] = A.T[i] | B.T[i];
}

// Procedura wyznacza część wspólną zbiorów A i B
//-----------------------------------------------
void s_intersection(s_set & A, s_set & B, s_set & C)
{
  for(int i = 0; i <= A.nmax; i++) C.T[i] = A.T[i] & B.T[i];
}

// Procedura kopiuje zbiór A do zbioru B
//--------------------------------------
void s_copy(s_set & A, s_set & B)
{
  for(int i = 0; i <= A.nmax; i++) B.T[i] = A.T[i];
}

// Procedura ustawia zbiór pełny
void s_full(s_set & A)
{
  for(int i = 0; i <= A.nmax; i++) A.T[i] = 0xffffffff;
}

// Funkcja sprawdza, czy zbiór A jest pusty
// true  - tak, jest pusty
// false - nie, nie jest pusty
//-----------------------------------------
bool s_empty(s_set A)
{
  unsigned int m = A.T[0];        // Pobieramy bity do m
  for(int i = 1; i <= A.nmax; i++) m |= A.T[i]; // Sumujemy logicznie bity
  return (m == 0);
}

// Funkcja bada, czy element x należy do zbioru A
// true  - tak, należy
// false - nie, nie należy
//-----------------------------------------------
bool s_isin(s_set & A, int x)
{
  int b = x - A.vmin;             // Obliczamy numer bitu w mapie bitowej
  if(A.T[b >> 5] & (1 << (b & 31))) return true;
  return false;
}

// Procedura wyświetla elementy zbioru A
//--------------------------------------
void s_print(s_set A)
{
  int nb;
  unsigned int m;

  for(int i = 0; i <= A.nmax; i++)
    for(nb = 0,m = A.T[i]; m; m >>= 1,nb++)
      if(m & 1) cout << (i << 5) + nb + A.vmin << " ";
}
// Funkcja oblicza liczbę elementów w A
//-------------------------------------
int s_size(s_set & A)
{
  int c = 0;                      // Zerujemy licznik
  for(int i = 0; i <= A.nmax; i++) // Przechodzimy przez kolejne komórki
    for(unsigned int m = A.T[i]; m; m >>= 1)
      if((m & 1) == 1) c++;       // Zliczamy bity równe 1
  return c;
}

// Procedura wyszukuje klikę największą
//-------------------------------------
void BronKerbosch(s_set & SR, s_set & SP, s_set & SX)
{
  s_set RP,PP,XP,PPP;
  slistEl * p;
  int v,u,ncmax,nc,rms;

  if(s_empty(SP) && s_empty(SX))  // Jeśli zbiory SP i SX są puste,
  {                               // to SR zawiera wierzchołki kliki maksymalnej
   rms = s_size(SR);              // Wyznaczamy liczbę wierzchołków w klice
   if(rms > rmsize)               // Jeśli mamy większą klikę od dotychczas znalezionej,
   {
     s_copy(SR,RM);               // to zapamiętujemy ją
     rmsize = rms;                // Zapamiętujemy również jej rozmiar
   }
  }
  else
  {
    s_create(PPP,0,n-1);          // Tworzymy zbiór pomocniczy PPP
    s_union(SP,SX,PPP);           // W PPP tworzymy sumę zbiorów SP i SX
    ncmax = 0;                    // Zerujemy licznik sąsiadów
    for(u = 0; u < n; u++)        // Przechodzimy przez kolejne wierzchołki grafu
      if(s_isin(PPP,u))           // Jeśli wierzchołek jest w PPP, to przetwarzamy go
      {
        nc = 0;                   // Zerujemy bieżący licznik sąsiadów
        for(p = graf[u]; p; p = p->next) // Badamy sąsiadów wierzchołka v
          if(s_isin(SP,p->v)) nc++; // Jeśli sąsiad w SP, zwiększamy nc
        if(nc >= ncmax)           // Jeśli liczba sąsiadów w P jest większa od ncmax,
        {
          v = u;                  // to zapamiętujemy wierzchołek
          ncmax = nc;             // oraz jego liczbę sąsiadów w P
        }
      }
    s_copy(SP,PPP);               // W PPP umieszczamy zbiór SP
    for(p = graf[v]; p; p = p->next) // przeglądamy listę sąsiadów piwota
      s_remove(PPP,p->v);         // Z PPP usuwamy każdego sąsiada piwota
    s_create(RP,0,n-1);           // Tworzymy puste zbiory pomocnicze
    s_create(PP,0,n-1);
    s_create(XP,0,n-1);
    for(v = 0; v < n; v++)        // Przechodzimy przez kolejne wierzchołki grafu
      if(s_isin(PPP,v))           // Jeśli wierzchołek v jest w zbiorze PPP, to
      {                           // go przetwarzamy
        s_clear(SN);              // Najpierw zerujemy zbiór sąsiadów
        for(p = graf[v];p;p = p->next) // Przeglądamy listę sąsiedztwa wierzchołka v
          s_add(SN,p->v);         // Każdego sąsiada umieszczamy w SN
        s_copy(SR,RP);            // W RP tworzymy zbiór SR z dodanym wierzchołkiem v
        s_add(RP,v);
        s_intersection(SP,SN,PP); // W PP tworzymy iloczyn SP i SN
        s_intersection(SX,SN,XP); // W XP tworzymy iloczyn SX i SN
        BronKerbosch(RP,PP,XP);   // Wywołanie rekurencyjne
        s_remove(SP,v);           // Z SP usuwamy wierzchołek v
        s_add(SX,v);              // i dodajemy go do SX
      }
    delete [] RP.T;              // Usuwamy zbiory pomocnicze
    delete [] PP.T;
    delete [] XP.T;
    delete [] PPP.T;
  }
}

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

int main()
{
  s_set SR,SP,SX;
  int i,u,v;
  slistEl *p,*r;

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

  s_create(SR,0,n-1);             // Tworzymy puste zbiory
  s_create(SP,0,n-1);
  s_create(SX,0,n-1);
  s_create(SN,0,n-1);
  s_create(RM,0,n-1);             // Pusty zbiór kliki największej

  rmsize = 0;                     // Liczba wierzchołków w klice największej

  graf = new slistEl * [n];       // Tworzymy tablicę list sąsiedztwa

  for(i = 0; i < n; i++) graf[i] = NULL; // Zerujemy listy sąsiedztwa

  for(i = 0; i < m; i++)
  {
    cin >> u >> v;                // Wierzchołki krawędzi
    p = new slistEl;              // Tworzymy element listy
    p->v = u;
    p->next = graf[v];            // Element dołączamy do listy sąsiadów v
    graf[v] = p;

    p = new slistEl;              // To samo dla krawędzi w drugą stronę
    p->v = v;
    p->next = graf[u];            // Element dołączamy do listy sąsiadów u
    graf[u] = p;
  }

  s_full(SP);                     // W zbiorze SP ustawiamy wszystkie wierzchołki

  cout << endl;

  BronKerbosch(SR,SP,SX);         // Szukamy rekurencyjnie kliki największej

  cout << "MAXIMUM CLIQUE: ";
  s_print(RM);
  cout << endl << "NUMBER OF VERTICES IN MAXIMUM CLIQUE = " << rmsize << endl << endl;

  delete [] SR.T;                 // Usuwamy zbiory
  delete [] SP.T;
  delete [] SX.T;
  delete [] SN.T;
  delete [] RM.T;

  for(v = 0; v < n; v++)          // Usuwamy tablicę list sąsiedztwa
  {
    p = graf[v];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }

  delete [] graf;

  return 0;
}
Free Basic
' Wyszukiwanie kliki największej
' Data   : 15.07.2014
' (C)2014 mgr Jerzy Wałaszek
'-------------------------------

' Definicja elementu listy sąsiedztwa

Type slistEl
  next As slistEl Ptr             ' Następny element listy
  v As Integer                    ' Wierzchołek docelowy
End Type

' Definicja struktury zbioru

Type s_set
  vmin As Integer
  nmax As Integer
  T As UInteger Ptr
End Type

' Zmienne globalne

Dim Shared As Integer n,m         ' Liczba wierzchołków i krawędzi grafu
Dim Shared As slistEl Ptr Ptr graf ' Tablica list sąsiedztwa
Dim Shared As s_set SN,RM         ' Zbiór sąsiadów i zbiór kliki największej
Dim Shared As Integer rmsize      ' Liczba wierzchołków w klice największej

' Obsługa zbiorów

' Procedura dodaje element x do zbioru A
'---------------------------------------
Sub s_add(ByRef A As s_set, ByVal x As Integer)
  Dim As Integer b,i

  b = x - A.vmin                  ' Obliczamy numer bitu
  i = b Shr 5                     ' Obliczamy indeks
  A.T[i] = A.T[i] or (1 Shl (b and 31)) ' Ustawiamy bit na 1
End Sub

' Procedura usuwa element x ze zbioru
'------------------------------------
Sub s_remove(ByRef A As s_set, ByVal x As Integer)
  Dim As Integer b,i

  b = x - A.vmin                  ' Obliczamy numer bitu
  i = b Shr 5                     ' Obliczamy indeks
  A.T[i] = A.T[i] And Not (1 Shl (b and 31)) ' Ustawiamy bit na 0
End Sub

' Procedura usuwa wszystkie elementy ze zbioru
'---------------------------------------------
Sub s_clear(ByRef A As s_set)
  Dim As Integer i
  For i = 0 To A.nmax
  	 A.T[i] = 0                    ' Zerujemy mapę bitową
  Next
End Sub

' Procedura tworzy zbiór
'-----------------------
Sub s_create(ByRef A As s_set, ByVal vmin As Integer, ByVal vmax As Integer)
  A.vmin = vmin                   ' Wypełniamy strukturę danymi
  A.nmax = (vmax - vmin) shr 5    ' Indeks ostatniego elementu tablicy
  A.T = New UInteger [A.nmax + 1] ' Tworzymy dynamicznie tablicę mapy bitowej
  s_clear(A)                      ' Tworzymy zbiór pusty
End Sub

' Procedura wyznacza sumę zbiorów A i B
'--------------------------------------
Sub s_union(ByRef A As s_set, ByRef B As s_set, ByRef C As s_set)
  Dim As Integer i

  For i = 0 To A.nmax
  	 C.T[i] = A.T[i] Or B.T[i]
  Next
End Sub

' Procedura wyznacza część wspólną zbiorów A i B
'-----------------------------------------------
Sub s_intersection(ByRef A As s_set, ByRef B As s_set, ByRef C As s_set)
  Dim As Integer i

  For i = 0 To A.nmax
  	 C.T[i] = A.T[i] And B.T[i]
  Next
End Sub

' Procedura kopiuje zbiór A do zbioru B
'--------------------------------------
Sub s_copy(ByRef A As s_set, ByRef B As s_set)
  Dim As Integer i
  For i= 0 To A.nmax
  	 B.T[i] = A.T[i]
  Next
End Sub

' Procedura ustawia zbiór pełny
'------------------------------
Sub s_full(ByRef A As s_set)
  Dim As Integer i
  For i = 0 To A.nmax
  	 A.T[i] = &Hffffffff
  Next
End Sub

' Funkcja sprawdza, czy zbiór A jest pusty
' true  - tak, jest pusty
' false - nie, nie jest pusty
'-----------------------------------------
Function s_empty(ByRef A As s_set) As Integer
  Dim As Integer i
  Dim As UInteger m = A.T[0]      ' Pobieramy bity do m
  For i = 1 To A.nmax
  	 m Or= A.T[i]                  ' Sumujemy logicznie bity
  Next
  If m = 0 Then Return 1
  Return 0
End Function

' Funkcja bada, czy element x należy do zbioru A
' true  - tak, należy
' false - nie, nie należy
'-----------------------------------------------
Function s_isin(ByRef  A As s_set, ByVal x As Integer) As Integer
  Dim As Integer b = x - A.vmin   ' Obliczamy numer bitu w mapie bitowej
  If A.T[b Shr 5] And (1 Shl (b And 31)) Then Return 1
  Return 0
End Function

' Procedura wyświetla elementy zbioru A
'--------------------------------------
Sub s_print(ByRef A As s_set)
  Dim As Integer nb,i
  Dim As UInteger m

  For i = 0 To A.nmax
    nb = 0
    m = A.T[i]
    While m
      If (m And 1) = 1 Then Print Using "& ";(i Shl 5) + nb + A.vmin;
      m shr= 1
      nb += 1
    Wend
  Next
End Sub

' Funkcja oblicza liczbę elementów w A
'-------------------------------------
Function s_size(ByRef A As s_set) As Integer
  Dim As Integer i,c = 0          ' Zerujemy licznik
  Dim As UInteger m
  For i = 0 To A.nmax
    m = A.T[i]
    While m
      If (m And 1) = 1 Then c += 1 ' Zliczamy bity równe 1
      m shr= 1
    Wend
  Next
  Return c
End Function

' Procedura wyszukuje klikę największą
'-------------------------------------
Sub BronKerbosch(ByRef SR As s_set, ByRef SP As s_set, ByRef SX As s_set)
  Dim As s_set RP,PP,XP,PPP
  Dim As slistEl Ptr p
  Dim As Integer v,u,ncmax,nc,rms

  If s_empty(SP) AndAlso s_empty(SX) Then  ' Jeśli zbiory SP i SX są puste,
                                  ' to SR zawiera wierzchołki kliki maksymalnej
    rms = s_size(SR)              ' Wyznaczamy liczbę wierzchołków w klice
    If rms > rmsize Then          ' Jeśli mamy większą klikę od dotychczas znalezionej,
      s_copy(SR,RM)               ' to zapamiętujemy ją
      rmsize = rms                ' Zapamiętujemy również jej rozmiar
    End If
  Else
    s_create(PPP,0,n-1)           ' Tworzymy zbiór pomocniczy PPP
    s_union(SP,SX,PPP)            ' W PPP tworzymy sumę zbiorów SP i SX
    ncmax = 0                     ' Zerujemy licznik sąsiadów
    For u = 0 To n - 1            ' Przechodzimy przez kolejne wierzchołki grafu
      If s_isin(PPP,u) Then       ' Jeśli wierzchołek jest w PPP, to przetwarzamy go
        nc = 0                    ' Zerujemy bieżący licznik sąsiadów
        p = graf[u]
        While p                   ' Badamy sąsiadów wierzchołka v
          If s_isin(SP,p->v) Then nc += 1 ' Jeśli sąsiad w SP, zwiększamy nc
          p = p->Next             ' Następny sąsiad
        Wend
        If nc >= ncmax Then       ' Jeśli liczba sąsiadów w P jest większa od ncmax,
          v = u                   ' to zapamiętujemy wierzchołek
          ncmax = nc              ' oraz jego liczbę sąsiadów w P
        End If
      End If
    Next
    s_copy(SP,PPP)                ' W PPP umieszczamy zbiór SP
    p = graf[v]
    While p                       ' Przeglądamy listę sąsiadów piwota
      s_remove(PPP,p->v)          ' Z PPP usuwamy każdego sąsiada piwota
      p = p->Next                 ' Następny sąsiad
    Wend
    s_create(RP,0,n-1)            ' Tworzymy puste zbiory pomocnicze
    s_create(PP,0,n-1)
    s_create(XP,0,n-1)
    For v = 0 To n - 1            ' Przechodzimy przez kolejne wierzchołki grafu
      If s_isin(PPP,v) Then       ' Jeśli wierzchołek v jest w zbiorze PPP, to
                                  ' go przetwarzamy
        s_clear(SN)               ' Najpierw zerujemy zbiór sąsiadów
        p = graf[v]               ' Przeglądamy listę sąsiedztwa wierzchołka v
        While p
          s_add(SN,p->v)          ' Każdego sąsiada umieszczamy w SN
          p = p->Next
        Wend
        s_copy(SR,RP)             ' W RP tworzymy zbiór SR z dodanym wierzchołkiem v
        s_add(RP,v)
        s_intersection(SP,SN,PP)  ' W PP tworzymy iloczyn SP i SN
        s_intersection(SX,SN,XP)  ' W XP tworzymy iloczyn SX i SN
        BronKerbosch(RP,PP,XP)    ' Wywołanie rekurencyjne
        s_remove(SP,v)            ' Z SP usuwamy wierzchołek v
        s_add(SX,v)               ' i dodajemy go do SX
      End If
    Next
    Delete [] RP.T                ' Usuwamy zbiory pomocnicze
    Delete [] PP.T
    Delete [] XP.T
    Delete [] PPP.T
  End If
End Sub

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

Dim As s_set SR,SP,SX
Dim As integer i,u,v
Dim As slistEl Ptr p,r

Open Cons For Input As #1

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

s_create(SR,0,n-1)                ' Tworzymy puste zbiory
s_create(SP,0,n-1)
s_create(SX,0,n-1)
s_create(SN,0,n-1)
s_create(RM,0,n-1)                ' Pusty zbiór kliki największej

rmsize = 0                        ' Liczba wierzchołków w klice największej

graf = New slistEl Ptr [n]        ' Tworzymy tablicę list sąsiedztwa

For i = 0 To n - 1
  graf[i] = 0                     ' Zerujemy listy sąsiedztwa
Next

For i = 1 To m
  Input #1,u,v                    ' Wierzchołki krawędzi
  p = New slistEl                 ' Tworzymy element listy
  p->v = u
  p->next = graf[v]               ' Element dołączamy do listy sąsiadów v
  graf[v] = p

  p = New slistEl                 ' To samo dla krawędzi w drugą stronę
  p->v = v
  p->next = graf[u]               ' Element dołączamy do listy sąsiadów u
  graf[u] = p
Next

Close #1

s_full(SP)                        ' W zbiorze SP ustawiamy wszystkie wierzchołki

Print

BronKerbosch(SR,SP,SX)            ' Szukamy rekurencyjnie kliki największej

Print "MAXIMUM CLIQUE: ";
s_print(RM)
Print
Print "NUMBER OF VERTICES IN MAXIMUM CLIQUE ="; rmsize
Print

Delete [] SR.T                    ' Usuwamy zbiory
Delete [] SP.T
Delete [] SX.T
Delete [] SN.T
Delete [] RM.T

For v = 0 To n - 1                ' Usuwamy tablicę list sąsiedztwa
  p = graf[v]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [] graf

End
Wynik
8 19
0 1 0 2 0 5 0 6
1 2 1 3 1 5 1 6
2 4 2 5 2 6 2 7
3 4 3 6 3 7
4 6
5 6 5 7
6 7

MAXIMUM CLIQUE: 0 1 2 5 6
NUMBER OF VERTICES IN MAXIMUM CLIQUE = 5

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2018 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe