Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Znajdowanie klik w grafie

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

W danym grafie nieskierowanym należy 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.

obrazek

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  ∈ 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
Zmienne pomocnicze:
u, v  –  numery wierzchołków grafu, u, v  ∈ C.
P', R', X', N  –  pomocnicze zbiory wierzchołków.

Lista kroków:

K01: Jeśli ( P  jest pusty ) obrazek ( X  jest pusty ),
to Pisz R
    i zakończ
znaleziona klika maksymalna
K02: Dla każdego wierzchołka v  w P :
wykonuj
kroki K03...K10
 
K03:     Zeruj zbiór N  
K04:     Dla każdego sąsiada u  wierzchołka v :
    wykonuj: N  ← N  + 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:     P  ← P  - v ze zbioru P usuwamy wierzchołek v
K10:     R  ← R  + v do zbioru R dodajemy wierzchołek v
K11: Zakończ  

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program 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.
Dane przykładowe ( przekopiuj do schowka i wklej do okna konsoli ):
obrazek   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
Pascal
// 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.
C++
// 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;
}
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
 obrazek
Na początek:  podrozdziału   strony 

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  ∈ 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
Zmienne pomocnicze:
u, v, w  –  numery wierzchołków grafu, u, v, w  ∈ C.
P', P", R', X', N  –  pomocnicze zbiory wierzchołków.
ncmax, nc  –  liczniki wierzchołków, ncmax, nc  ∈ C.

Lista kroków:

K01: Jeśli ( P  jest pusty ) obrazek ( 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
kroki 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 nc  ← nc  + 1
jeśli sąsiad jest w P, to zwiększamy bieżący licznik sąsiadów
K07:     Jeśli ncncmax,
    to: v  ← u
        i ncmax  ← nc
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
kroki K11...K18
 
K11:     Zeruj zbiór N  
K12:     Dla każdego sąsiada u  wierzchołka v :
    wykonuj: N  ← N  + 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:     P  ← P  - v ze zbioru P usuwamy wierzchołek v
K18:     R  ← R  + v do zbioru R dodajemy wierzchołek v
K19: Zakończ  

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program 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.
 
Dane przykładowe ( przekopiuj do schowka i wklej do okna konsoli ):
obrazek   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
Pascal
// 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.
C++
// 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;
}
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
 obrazek

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

Na początek:  podrozdziału   strony 

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

Wyjście:

Zbiór RM  zawiera klikę największą. W zmiennej rmsize  zostaje umieszczony rozmiar tej kliki.
Zmienne pomocnicze:
u, v, w  –  numery wierzchołków grafu, u, v, w  ∈ C.
P', P", R', X', N  –  pomocnicze zbiory wierzchołków.
ncmax, nc  –  liczniki wierzchołków, ncmax, nc  ∈ C.
rms  –  liczba wierzchołków w zbiorze R, rms  ∈ C.

Lista kroków:

K01: Jeśli ( P  nie jest pusty ) obrazek ( X  nie jest pusty ),
to idź do kroku K05
znaleziona klika maksymalna
K02: rms  ← rozmiar R wyznaczamy liczbę wierzchołków w klice maksymalnej
K03: Jeśli rms  > rmsize, to
    RM  ← R
    rmsize  ← rms
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
kroki 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 nc  ← nc  + 1
jeśli sąsiad jest w P, to zwiększamy bieżący licznik sąsiadów
K10:     Jeśli ncncmax, to
        v  ← u
        ncmax  ← nc
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:
        N  ← N  + 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:     P  ← P  - v ze zbioru P usuwamy wierzchołek v
K21:     R  ← R  + v do zbioru R dodajemy wierzchołek v
K22: Zakończ  

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program 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.
Dane przykładowe ( przekopiuj do schowka i wklej do okna konsoli ):
obrazek   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
Pascal
// 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.
C++
// 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;
}
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
 obrazek
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

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

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.