Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Maksymalne skojarzenia w grafach dwudzielnych

SPIS TREŚCI
Tematy pomocnicze

Problem

Dla danego grafu dwudzielnego należy znaleźć maksymalne skojarzenie.

Rozwiązanie

Sieci przepływowe służą zwykle do rozwiązywania problemów związanymi z przepływami - komunikacja, transport, ruch w sieciach teleinformatycznych itp. Jednakże po przyjęciu pewnych założeń można je stosować do rozwiązywania zadziwiająco dużej klasy problemów, które na pierwszy rzut oka nie mają wiele wspólnego z przepływami. Jednym z takich problemów jest znajdowanie maksymalnego skojarzenia w grafie dwudzielnym

Przypomnijmy:

Graf dwudzielny ( ang. bipartite graph lub bigraph ) jest grafem, którego wierzchołki można pokolorować za pomocą dwóch kolorów tak, aby żadne dwa sąsiednie nie były tego samego koloru. Innymi słowy, graf dwudzielny zawiera wierzchołki należące do dwóch rozłącznych klas. Wierzchołki należące do tej samej klasy nie łączą się krawędzią.

obrazek

Skojarzeniem nazywamy znalezienie zbioru krawędzi grafu, które w grafie dwudzielnym łączą pary wierzchołków. Przy czym wierzchołki tworzące jedną parę nie mogą już należeć do innych par. Dwudzielność grafu gwarantuje, iż będą to zawsze wierzchołki należące do różnych klas.

obrazek

Skojarzenie nazywamy maksymalnym, jeśli zawiera maksymalną, możliwą liczbę krawędzi. Powyżej przedstawiamy skojarzenie w grafie dwudzielnym ( wierzchołki skojarzone są zielonymi krawędziami  ), jednakże nie jest to skojarzenie maksymalne, chociaż w tym układzie nie można już dodać żadnej krawędzi. Skojarzenie maksymalne uzyskamy reorganizując nieco krawędzie zielone. Wynik mamy poniżej:

obrazek

Algorytm znajdowania maksymalnych skojarzeń w grafach dwudzielnych opisaliśmy dokładnie przy okazji problemu kojarzenia małżeństw. Rozwiązanie wykorzystywało metodę BFS do znajdowania naprzemiennych ścieżek rozszerzających. Do tego samego wyniku możemy dojść stosując algorytm Forda-Fulkersona, który znajduje maksymalny przepływ w sieci. W tym celu musimy nieco zmodyfikować graf dwudzielny dodając węzeł źródła oraz węzeł ujścia:

obrazek

Węzeł źródła S łączymy ze wszystkimi węzłami jednej klasy, a węzły należące do drugiej klasy łączymy z ujściem T. Przepustowość wszystkich krawędzi ustalamy na 1. W efekcie otrzymujemy powyższą sieć przepływową. Wyznaczamy w niej maksymalny przepływ przy pomocy algorytmu Forda-Fulkersona. Ponieważ do węzłów niebieskich ( umowne oznaczenie węzłów w pierwszej klasie ) dochodzą ze źródła krawędzie o przepustowości 1, to przepływ wypływający z tych węzłów nie może przekroczyć 1. Jeśli przepływ będzie miał wartość 1, to popłynie tylko jedną krawędzią grafu - tą, która kojarzy wierzchołek niebieski z czerwonym. W efekcie wyznaczone przepływy w krawędziach grafu wskażą nam skojarzenia wierzchołków. Jeśli w danej krawędzi występuje przepływ o wartości 1, to krawędź ta kojarzy dwa wierzchołki w grafie dwudzielnym. Jeśli przepływ w krawędzi jest zerowy, to krawędź nie jest wykorzystywana do kojarzenia wierzchołków.

Dodatkową korzyścią jest wyznaczenie wierzchołków nieskojarzonych - wystarczy zbadać przepływ zerowy w krawędziach połączonych ze źródłem ( wierzchołki nieskojarzone w klasie pierwszej ) oraz w krawędziach połączonych z ujściem ( wierzchołki nieskojarzone w klasie drugiej ). Jeśli skojarzenie jest zupełne ( wszystkie wierzchołki klasy pierwszej skojarzone z wierzchołkami klasy drugiej ), to oczywiście we wszystkich tych krawędziach będzie przepływ o wartości 1.

Wartość wyznaczonego przez algorytm maksymalnego przepływu w sieci informuje nas o liczbie skojarzonych wierzchołków - pozwala od razu stwierdzić, czy w danym grafie możliwe jest skojarzenie zupełne.

Z rozważań tych wyłania się ogólny algorytm znajdowania maksymalnych skojarzeń w grafach dwudzielnych przy pomocy algorytmu wyznaczania maksymalnego przepływu w sieci przepływowej:

Krok 1: Pokoloruj wierzchołki grafu na czerwono i niebiesko tak, aby wierzchołki z tej samej klasy posiadały ten sam kolor.
Krok 2: Potraktuj graf jako graf skierowany - wszystkie krawędzie są skierowane od wierzchołka niebieskiego do czerwonego.
Krok 3: Na podstawie grafu zbuduj macierz przepustowości krawędzi C [ n + 2 ] × [ n + 2 ] ustawiając przepustowość krawędzi na 1 – macierz powinna zawierać dodatkowo dane dla źródła S i ujścia T. W wierszu C [ S ][ ] należy ustawić 1 w kolumnach odpowiadających wierzchołkom niebieskim, 0 dla pozostałych wierzchołków. W kolumnie C [ ][ T ] należy ustawić 1 dla wierszy odpowiadających wierzchołkom czerwonym i 0 dla pozostałych wierzchołków.
Krok 4: Zastosuj algorytm Karpa-Edmondsa do wyznaczenia maksymalnego przepływu w sieci.
Krok 5: Dla każdego niebieskiego wierzchołka grafu wyprowadź tę krawędź, której przepływ jest równy 1.
Krok 6: Koniec

Jest to algorytm zbudowany z kilku mniejszych algorytmów. Aby wykorzystać go do napisania programu, musimy rozwiązać kilka problemów:

Kolorowanie wierzchołków grafu rozwiązuje algorytm badający dwudzielność grafu. W wyniku jego działania otrzymujemy informację o tym, czy graf jest dwudzielny. Dodatkowo dostajemy wypełnioną n  elementową tablicę Color, która przechowuje kolory wierzchołków grafu.

Tworzenie grafu skierowanego można rozwiązać na etapie wprowadzania danych wymagając, aby krawędzie grafu dwudzielnego były zdefiniowane parami wierzchołków ( niebieski, czerwony ) – takie podejście uwalnia nas również od algorytmu kolorowania. Jeśli tak się nie stało i mamy na wejściu graf nieskierowany, to po prostu usuwamy z niego wszystkie krawędzie wychodzące z wierzchołków czerwonych, które znaleźliśmy w poprzednim kroku.

Macierz przepustowości C definiuje sieć przepływową. Ustawiamy przepustowość każdej krawędzi na 1. Musimy również uwzględnić węzeł źródła S oraz węzeł ujścia T. Dlatego wymiar macierzy jest o 2 większy od n, czyli liczby wierzchołków w grafie. Umawiamy się, iż źródło ma numer n + 1, a ujście ma numer n + 2. Wierzchołków tych wcale nie musimy dodawać do grafu - wystarczy, iż znajdą się w macierzy przepustowości.

Algorytm znajdowania maksymalnego skojarzenia w nieskierowanym grafie dwudzielnym - wersja z macierzą przepustowości

Wejście:

n  –  liczba wierzchołków w grafie, n  ∈ C.
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

Macierz przepływów F o wymiarze n = 2 × n + 2 lub informacja, że graf nie jest dwudzielny. Macierz zawiera informację o maksymalnym skojarzeniu. Wierzchołki i, j  są skojarzone ze sobą, jeśli C [ i, j  ] = 1 i F [ i, j  ] = 1. Źródło S jest wierzchołkiem o numerze n. Ujście jest wierzchołkiem o numerze n = 1.

fmax  – zawiera informację o liczbie skojarzonych par wierzchołków.

Zmienne pomocnicze:
Q  –  kolejka przechowująca wierzchołki grafu.
i, v, u  –  wierzchołki, i, v, u  ∈ C.
Color  –  n  elementowa tablica zawierająca kolory wierzchołków, w przypadku grafu dwudzielnego:
 0 - kolor szary,
 1 - kolor czerwony,
-1 - kolor niebieski.
fmax  –  wartość maksymalnego przepływu w sieci, fmax  ∈ C.
P  –  tablica n  elementowa przechowująca ścieżki ( poprzedniki ) wyszukiwane przez BFS.
CFP  –  tablica n  elementowa przechowująca wartości c f ( p  ) dla ścieżki kończącej się w danym węźle sieci.
cp  –  przechowuje wartość przepustowości rezydualnej, cp  ∈ C.

Lista kroków:

K01: Utwórz n  elementową
tablicę Color
 
K02: Ustaw wszystkie elementy
tablicy Color  na 0
0 oznacza kolor szary
K03: Utwórz pustą kolejkę Q  
K04: Dla i  = 0, 1, ..., n  - 1:
wykonuj kroki K05...K15
przechodzimy przez kolejne wierzchołki grafu
K05:     Jeśli Color [ i  ] ≠ 0,
    to następny obieg pętli K04
szukamy wierzchołka szarego, który będzie wierzchołkiem startowym
K06:     Color [ i  ] ← 1 wierzchołek startowy kolorujemy na czerwono
K07:     Q.push ( i  ) numer wierzchołka umieszczamy w kolejce
K08:     Dopóki Q.empty( ) = false:
    wykonuj kroki K09...K15
rozpoczynamy przejście BFS
K09:         v  ← Q.front( ) pobieramy element z początku kolejki
K10:         Q.pop( ) pobrany element usuwamy z kolejki
K11:         Dla każdego sąsiada u  wierzchołka v :
        wykonuj kroki K12...K15
przetwarzamy sąsiadów wierzchołka v
K12:             Jeśli Color [ u  ] = Color [ v  ],
            to zakończ z komunikatem o błędzie
sąsiad ma ten sam kolor, więc graf nie może być dwudzielny
K13:             Jeśli Color [ u  ] ≠ 0,
            to następny obieg pętli K11
szukamy wierzchołka niepokolorowanego, czyli jeszcze nieodwiedzonego
K14:             Color [ u  ] ← -Color [ v  ] kolorujemy sąsiada na kolor przeciwny
K15:             Q.push ( u  ) sąsiada umieszczamy w kolejce
K16: Utwórz macierz C
o rozmiarze n + 2 × n + 2
tworzymy macierz przepustowości
K17: Ustaw wszystkie elementy
macierzy C  na 0
 
K18: Dla i  = 0, 1, ..., n - 1:
wykonuj kroki K19...K23
przechodzimy przez kolejne wierzchołki grafu
K19:     Jeśli Color [ i  ] = 1,
    to idź do kroku K23
sprawdzamy kolor wierzchołka
K20:     Dla każdego sąsiada u  wierzchołka i :
    wykonuj: C [ i, u  ] ← 1
krawędzie wierzchołków niebieskich otrzymują przepustowość 1
K21     C [ n, i  ] ← 1 dodajemy krawędź od źródła do wierzchołka i
K22:     Następny obieg pętli K18  
K23:     C [ i, n + 1 ] ← 1 dla wierzchołków czerwonych dodajemy tylko krawędź do ujścia
K24: fmax  ← 0 zerujemy wartość przepływu sieciowego
K25 Utwórz macierz F
o wymiarze n = 2 × n + 2
i wyzeruj ją
zerujemy macierz przepływów
K26:     Dla i  = 0, 1, ..., n  + 1:
    wykonuj: P [ i  ] ← -1
 
K27:     P [ n  ] ← -2 to zapobiegnie wybieraniu źródła przez BFS
K28:     CFP [ n  ] ← ∞ w CFP przechowujemy przepustowość rezydualną ścieżki
K29:     Dopóki Q.empty( ) = false,
    wykonuj Q.pop( )
zerujemy kolejkę
K30:     Q.push ( s  ) w kolejce umieszczamy numer źródła
K31:     Dopóki Q.empty( ) = false,
    wykonuj kroki K32...K39
 
K32:         v  = Q.front( );  Q.pop( ) pobieramy numer wierzchołka z kolejki
K33:         Dla u  = 0, 1, ..., n  + 1:
        wykonuj kroki K34...K39
rozpoczynamy BFS
K34:             cp  ← C [ v  ][ u  ] - F [ v  ][ u  ] wyznaczamy przepustowość rezydualną kanału ( v, u )
K35:             Jeśli ( cp  = 0 ) obrazek ( P [ u  ] ≠ -1 ),
            to następny obieg pętli K33
omijamy przy braku krawędzi lub odwiedzonym sąsiedzie
K36:             P [ u  ] ← v zapamiętujemy poprzednik na ścieżce
K37:             CPF [ u  ] ← min ( CPF [ v  ], cp  ) obliczamy przepustowość rezydualną do węzła u
K38:             Jeśli u  = n + 1,
            to idź do kroku K41
ścieżka rozszerzająca znaleziona!
K39:             Q.push ( u  )  
K40:     Idź do kroku K48 brak ścieżki, idziemy do końcówki algorytmu
K41:     fmax  ← fmax  + CFP [ n+1 ] zwiększamy przepływ sieciowy
K42:     Dopóki u  ≠ n,
    wykonuj kroki K43...K46
cofamy się po ścieżce rozszerzającej od ujścia t do źródła s
K43:         v  ← P [ u  ] ( v, u ) jest krawędzią ścieżki rozszerzającej
K44:         F [ v, u  ] ← F [ v, u  ] + CFP [ n+1 ] w kierunku zgodnym ze ścieżką zwiększamy przepływ
K45:         F [ u, v  ] ← F [ u, v  ] - CFP [ n+1 ] w kierunku przeciwnym zmniejszamy przepływ
K46:         u  ← v przechodzimy do następnej krawędzi ścieżki
K47: Idź do kroku K26  
K48: Pisz fmax wypisujemy liczbę skojarzonych par wierzchołków
K49: Jeśli fmax  = 0,
to zakończ
 
K50: Dla v  = 0, 1, ..., n  - 1:
wykonuj
krok K51
przeglądamy macierz przepływów
K51:     Dla u  = 0, 1, ..., n  - 1:
    wykonuj:
        Jeśli ( C [ v, u  ] = 1 ) obrazek ( F [ v, u  ] = 1 ),
        to pisz v, u
wypisujemy pary skojarzonych wierzchołków
K52: 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. Jeśli graf jest grafem dwudzielnym, to wyznacza dla niego maksymalne skojarzenie.
Dane przykładowe ( przekopiuj do schowka i wklej do okna konsoli ):
obrazek  10 17
0 2 0 3 0 4 0 8
1 2 1 4 1 8
2 5 2 7
3 7 3 9
4 5 4 9
5 6
6 7 6 9
8 9
Pascal
// Maksymalne skojarzenia
// Data: 26.10.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program maxmatch;

// Definicja typu elementów listy
//-------------------------------
type
  PslistEl = ^slistEl;
  slistEl = record
    next  : PslistEl;
    data  : integer;
  end;

// Definicja typu obiektowego queue
//---------------------------------
  queue = object
    private
      head : PslistEl;
      tail : PslistEl;

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

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
constructor queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor queue.destroy;
begin
  while not empty do pop;
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  if head = nil then empty := true
  else               empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
begin
  if head = nil then front := -MAXINT
  else               front := head^.data;
end;

// Zapisuje do kolejki
//--------------------
procedure queue.push ( v : integer );
var
  p : PslistEl;
begin
  new ( p );
  p^.next := nil;
  p^.data := v;
  if tail = nil then head := p
  else tail^.next := p;
  tail := p;
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
var
  p : PslistEl;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then tail := nil;
    dispose ( p );
  end;
end;

//---------------
// Program główny
//---------------

var
  Q : queue;                      // Kolejka
  Color : array of integer;       // Tablica kolorów wierzchołków
  graf : array of PslistEl;       // Tablica list sąsiedztwa
  C : array of array of integer;  // Macierz przepustowości
  F : array of array of integer;  // Macierz przepływów netto
  P : array of integer;           // Tablica poprzedników
  CFP : array of integer;         // Tablica przepustowości rezydualnych
  n, m, fmax, cp, v, u, i, j : integer;  // Zmienne proste algorytmu
  esc : boolean;                  // Do wychodzenia z zagnieżdżonych pętli
  pr, rr : PslistEl;              // Wskaźniki elementów listy

// Funkcja zwraca true, jeśli graf jest dwudzielny.
// Ustala kolory wierzchołków w tablicy Color
//------------------------------------------------
function isBipartite : boolean;
begin
  for i := 0 to n - 1 do    // Przechodzimy przez kolejne wierzchołki
    if Color [ i ] = 0 then // Szukamy wierzchołka szarego
    begin
      Color [ i ] := 1;     // Wierzchołek startowy kolorujemy na czerwono
      Q.push ( i );         // i umieszczamy w kolejce

      while not Q.empty do // Przejście BFS
      begin
        v := Q.front;     // Pobieramy wierzchołek z kolejki
        Q.pop;            // Pobrany wierzchołek usuwamy z kolejki
        pr := graf [ v ]; // Przeglądamy sąsiadów wierzchołka v
        while pr <> nil do
        begin
          u := pr^.data; // pobieramy z listy sąsiedztwa numer sąsiada
          if Color [ u ] = Color [ v ] then Exit ( false );

          if Color [ u ] = 0 then  // Jeśli wierzchołek nie jest odwiedzony, 
          begin
            Color [ u ] := -Color [ v ]; // kolorujemy go na kolor przeciwny
            Q.push ( u ); // i umieszczamy w kolejce
          end;
          pr := pr^.next; // Następny sąsiad
        end;
      end;
    end;

  isBipartite := true;
end;

begin
  Q.init;                 // Inicjujemy kolejkę

  // Ze standardowego wejścia odczytujemy
  // n - liczbę wierzchołków w grafie sieci
  // m - liczbę krawędzi

  read ( n, m );

  // Tworzymy dane dynamiczne

  SetLength ( Color, n ); // Tablica kolorów wierzchołków
  SetLength ( graf, n );  // Tablica list sąsiedztwa
  for i := 0 to n - 1 do
  begin
    graf [ i ] := nil;
    Color [ i ] := 0;
  end;

  SetLength ( C, n+2 ); // Macierz przepustowości krawędzi
  SetLength ( F, n+2 ); // Macierz przepływów netto
  for i := 0 to n + 1 do
  begin
    SetLength ( C [ i ], n+2 );
    SetLength ( F [ i ], n+2 );
    for j := 0 to n + 1 do
    begin
      C [ i ][ j ] := 0;
      F [ i ][ j ] := 0;
    end;
  end;

  SetLength ( P, n+2 );   // Tablica poprzedników
  SetLength ( CFP, n+2 ); // Tablica przepustowości rezydualnych

  // Odczytujemy definicje krawędzi i dodajemy je do list sąsiedztwa

  for i := 1 to m do
  begin
    read ( v, u );
    new ( pr );
    pr^.data := u;
    pr^.next := graf [ v ];
    graf [ v ]  := pr;

    new ( pr );
    pr^.data := v;
    pr^.next := graf [ u ];
    graf [ u ]  := pr;
  end;

  if isBipartite then
  begin
    // Ustawiamy macierz przepustowości
    for i := 0 to n - 1 do
      if Color [ i ] = -1 then
      begin
        pr := graf [ i ];       // Przeglądamy listę sąsiadów wierzchołka niebieskiego
        while pr <> nil do
        begin
          C [ i ][ pr^.data ] := 1; // Przepustowość krawędzi do wierzchołka czerwonego
          pr := pr^.next;       // Następny sąsiad
        end;
        C [ n ][ i ] := 1;      // Przepustowość krawędzi od źródła
      end
      else C [ i ][ n+1 ] := 1; // Przepustowość krawędzi do ujścia

    //**************************************************
    //** Tutaj rozpoczyna się algorytm Edmondsa-Karpa **
    //**************************************************

    fmax := 0;

    while true do
    begin
      for i := 0 to n + 1 do P [ i ] := -1;

      P [ n ] := -2;
      CFP [ n ] := MAXINT;

      while not Q.empty do Q.pop;
      Q.push ( n );

      esc := false;

      while not Q.empty do
      begin
        v := Q.front; Q.pop;

        for u := 0 to n + 1 do
        begin
          cp := C [ v ][ u ] - F [ v ][ u ];
          if( cp <> 0 ) and ( P [ u ] = -1 ) then
          begin
            P [ u ] := v;
            if CFP [ v ] > cp then CFP [ u ] := cp else CFP [ u ] := CFP [ v ];
            if u = n + 1 then
            begin
              inc ( fmax, CFP [ n+1 ] );
              i := u;
              while i <> n do
              begin
                v := P [ i ];
                inc ( F [ v ][ i ], CFP [ n+1 ] );
                dec ( F [ i ][ v ], CFP [ n+1 ] );
                i := v;
              end;
              esc := true; break;
            end;
            Q.push ( u );
          end;
        end;
        if esc then break;
      end;
      if not esc then break;
    end;

    // Wyświetlamy wyniki

    writeln;
    writeln ( 'NUMBER OF MATCHES = ', fmax );
    writeln;
    if fmax > 0 then
      for v := 0 to n - 1 do
        for u := 0 to n - 1 do
          if( C [ v ][ u ] = 1 ) and ( F [ v ][ u ] = 1 ) then
            writeln ( v, ' - ', u );
  end
  else
  begin
    writeln;
    writeln ( 'NOT A BIBARTITE GRAPH' );
  end;

  writeln;

  // Usuwamy dane dynamiczne

  SetLength ( Color, 0 ); // Tablica kolorów wierzchołków

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

  SetLength ( graf, 0 ); // Tablica list sąsiedztwa

  for i := 0 to n + 1 do
  begin
    SetLength ( C [ i ], 0 );
    SetLength ( F [ i ], 0 );
  end;
  SetLength ( C, 0 );   // Macierz przepustowości krawędzi
  SetLength ( F, 0 );   // Macierz przepływów netto

  SetLength ( P, 0 );   // Tablica poprzedników
  SetLength ( CFP, 0 ); // Tablica przepustowości rezydualnych
end.
C++
// Maksymalne skojarzenia
// Data: 26.10.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

const int MAXINT = 2147483647;

// Definicja typu elementów listy
//-------------------------------
struct slistEl
{
  slistEl * next;
  int data;
};

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    slistEl * head;
    slistEl * tail;

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

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
queue::queue( )
{
  head = tail = NULL;
}

// Destruktor - usuwa listę z pamięci
//-----------------------------------
queue::~queue( )
{
  while( head ) pop( );
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool queue::empty ( void )
{
  return !head;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front ( void )
{
  if( head ) return head->data;
  else     return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push ( int v )
{
  slistEl * p = new slistEl;
  p->next = NULL;
  p->data = v;
  if( tail ) tail->next = p;
  else     head = p;
  tail = p;
}

// Usuwa z kolejki
//----------------
void queue::pop ( void )
{
  if( head )
  {
    slistEl * p = head;
    head = head->next;
    if( !head ) tail = NULL;
    delete p;
  }
}

//---------------
// Program główny
//---------------

queue Q;          // Kolejka
int *Color;       // Tablica kolorów wierzchołków
slistEl **graf;   // Tablica list sąsiedztwa
int **C;          // Macierz przepustowości
int **F;          // Macierz przepływów netto
int *P;           // Tablica poprzedników
int *CFP;         // Tablica przepustowości rezydualnych
int n, m, fmax, cp, v, u, i, j; // Zmienne proste algorytmu
bool esc;         // Do wychodzenia z zagnieżdżonych pętli
slistEl *pr, *rr; // Wskaźniki elementów listy

// Funkcja zwraca true, jeśli graf jest dwudzielny.
// Ustala kolory wierzchołków w tablicy Color
//------------------------------------------------
bool isBipartite( )
{
  for( int i = 0; i < n; i++ )          // Przechodzimy przez kolejne wierzchołki
    if( !Color [ i ] )                  // Szukamy wierzchołka szarego
    {
      Color [ i ] = 1;                  // Wierzchołek startowy kolorujemy na czerwono
      Q.push ( i );                     // i umieszczamy w kolejce

      while( !Q.empty( ) )              // Przejście BFS
      {
        v = Q.front( );                 // Pobieramy wierzchołek z kolejki
        Q.pop( );                       // Pobrany wierzchołek usuwamy z kolejki
        for( pr = graf [ v ]; pr; pr = pr->next ) // Przeglądamy sąsiadów wierzchołka v
        {
          u = pr->data;                 // pobieramy z listy sąsiedztwa numer sąsiada
          if( Color [ u ] == Color [ v ] ) return false;

          if( !Color [ u ] )            // Jeśli wierzchołek nie jest odwiedzony, 
          {
            Color [ u ] = -Color [ v ]; // kolorujemy go na kolor przeciwny
            Q.push ( u );               // i umieszczamy w kolejce
          }
        }
      }
    }

  return true;
}

int main( )
{
  // Ze standardowego wejścia odczytujemy
  // n - liczbę wierzchołków w grafie sieci
  // m - liczbę krawędzi

  cin >> n >> m;

  // Tworzymy dane dynamiczne

  Color = new int [ n ];      // Tablica kolorów wierzchołków
  graf = new slistEl * [ n ]; // Tablica list sąsiedztwa
  for( i = 0; i < n; i++ )
  {
    graf [ i ] = NULL;
    Color [ i ] = 0;
  }

  C = new int * [ n + 2 ]; // Macierz przepustowości krawędzi
  F = new int * [ n + 2 ]; // Macierz przepływów netto
  for( i = 0; i <= n + 1; i++ )
  {
    C [ i ] = new int [ n + 2 ];
    F [ i ] = new int [ n + 2 ];
    for( j = 0; j <= n + 1; j++ )
    {
      C [ i ][ j ] = 0;
      F [ i ][ j ] = 0;
    }
  }

  P = new int [ n + 2 ];   // Tablica poprzedników
  CFP = new int [ n + 2 ]; // Tablica przepustowości rezydualnych

  // Odczytujemy definicje krawędzi i dodajemy je do list sąsiedztwa

  for( i = 0; i < m; i++ )
  {
    cin >> v >> u;
    pr = new slistEl;
    pr->data = u;
    pr->next = graf [ v ];
    graf [ v ]  = pr;

    pr = new slistEl;
    pr->data = v;
    pr->next = graf [ u ];
    graf [ u ]  = pr;
  }

  if( isBipartite( ) )
  {
    // Ustawiamy macierz przepustowości
    for( i = 0; i < n; i++ )
      if( Color [ i ] == -1 )
      {
        for( pr = graf [ i ]; pr; pr = pr -> next ) // Przeglądamy listę sąsiadów wierzchołka niebieskiego
          C [ i ][ pr->data ] = 1; // Przepustowość krawędzi do wierzchołka czerwonego
        C [ n ][ i ] = 1;          // Przepustowość krawędzi od źródła
      }
      else C [ i ][ n + 1 ] = 1;   // Przepustowość krawędzi do ujścia

    //**************************************************
    //** Tutaj rozpoczyna się algorytm Edmondsa-Karpa **
    //**************************************************

    fmax = 0;

    while( true )
    {
      for( i = 0; i <= n + 1; i++ ) P [ i ] = -1;

      P [ n ] = -2;
      CFP [ n ] = MAXINT;

      while( !Q.empty( ) ) Q.pop( );
      Q.push ( n );

      esc = false;

      while( !Q.empty( ) )
      {
        v = Q.front( ); Q.pop( );

        for( u = 0; u <= n + 1; u++ )
        {
          cp = C [ v ][ u ] - F [ v ][ u ];
          if( cp && ( P [ u ] == -1 ) )
          {
            P [ u ] = v;
            if( CFP [ v ] > cp ) CFP [ u ] = cp; else CFP [ u ] = CFP [ v ];
            if( u == n+1 )
            {
              fmax += CFP [ n+1 ];
              i = u;
              while( i != n )
              {
                v = P [ i ];
                F [ v ][ i ] += CFP [ n + 1 ];
                F [ i ][ v ] -= CFP [ n + 1 ];
                i = v;
              }
              esc = true; break;
            }
            Q.push ( u );
          }
        }
        if( esc ) break;
      }
      if( !esc ) break;
    }

    // Wyświetlamy wyniki

    cout << endl
         << "NUMBER OF MATCHES = " << fmax
         << endl;
    if( fmax > 0 )
      for( v = 0; v < n; v++ )
        for( u = 0; u < n; u++ )
          if( ( C [ v ][ u ] == 1 ) && ( F [ v ][ u ] == 1 ) )
            cout << v << " - " << u << endl;
  }
  else cout << endl << "NOT A BIBARTITE GRAPH" << endl;

  cout << endl;

  // Usuwamy dane dynamiczne

  delete [ ] Color; // Tablica kolorów wierzchołków

  for( i = 0; i < n; i++ )
  {
    pr = graf [ i ];
    while( pr )
    {
      rr = pr;
      pr = pr->next;
      delete rr;
    }
  }

  delete [ ] graf; // Tablica list sąsiedztwa

  for( i = 0; i <= n + 1; i++ )
  {
    delete [ ] C [ i ];
    delete [ ] F [ i ];
  }
  delete [ ] C;   // Macierz przepustowości krawędzi
  delete [ ] F;   // Macierz przepływów netto

  delete [ ] P;   // Tablica poprzedników
  delete [ ] CFP; // Tablica przepustowości rezydualnych

  return 0;
}
Basic
' Maksymalne skojarzenia
' Data: 26.10.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

Const MAXINT = 2147483647

' Definicja typu elementów listy
'-------------------------------
Type slistEl
  next As slistEl Ptr
  Data As Integer
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As slistEl Ptr
    tail As slistEl Ptr

  Public:
    Declare Constructor( )
    Declare Destructor( )
    Declare Function empty( ) As Integer
    Declare Function front As Integer
    Declare Sub push ( ByVal x As Integer )
    Declare Sub pop( )
End Type

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor - tworzy pustą listę
'---------------------------------
Constructor queue( )
  head = 0
  tail = 0
End Constructor

' Destruktor - usuwa listę z pamięci
'-----------------------------------
Destructor queue( )
  While empty = 0: pop: Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty( ) As Integer
  If head = 0 Then Return 1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front( ) As Integer
  If head = 0 then
    front = -MAXINT
  Else
    front = head->data
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push ( ByVal v As Integer )
  Dim p As slistEl Ptr
  p = new slistEl
  p->next = 0
  p->Data = v
  If tail = 0 Then
    head = p
  Else
    tail->next = p
  End If
  tail = p
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop( )
  Dim p As slistEl Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

'---------------
' Program główny
'---------------

Dim Shared As queue Q              ' Kolejka
Dim Shared As Integer Ptr VColor, P, CFP ' Tablice kolorów, poprzedników i przepustowości rezydualnych 
Dim Shared As slistEl Ptr Ptr graf ' Tablica list sąsiedztwa
Dim As Integer Ptr Ptr C, F        ' Macierze przepustowości i przepływów netto
Dim Shared As Integer n, m, fmax, cp, v, u, i, j ' Zmienne proste algorytmu
Dim As Byte esc                    ' Do wychodzenia z zagnieżdżonych pętli
Dim Shared As slistEl Ptr pr, rr   ' Wskaźniki elementów listy

' Funkcja zwraca true, jeśli graf jest dwudzielny.
' Ustala kolory wierzchołków w tablicy Color
'------------------------------------------------
Function isBipartite( ) As Byte

  For i = 0 To n - 1      ' Przechodzimy przez kolejne wierzchołki
    If VColor [ i ] = 0 Then ' Szukamy wierzchołka szarego
      VColor [ i ] = 1    ' Wierzchołek startowy kolorujemy na czerwono
      Q.push ( i )        ' i umieszczamy w kolejce

      While Q.empty( ) = 0 ' Przejście BFS
        v = Q.front( )    ' Pobieramy wierzchołek z kolejki
        Q.pop( )          ' Pobrany wierzchołek usuwamy z kolejki
        pr = graf [ v ] 
        While pr <> 0     ' Przeglądamy sąsiadów wierzchołka v
          u = pr->Data    ' pobieramy z listy sąsiedztwa numer sąsiada
          If VColor [ u ] = VColor [ v ] Then return 0

          If VColor [ u ] = 0 Then ' Jeśli wierzchołek nie jest odwiedzony, 
            VColor [ u ] = -VColor [ v ] ' kolorujemy go na kolor przeciwny
            Q.push ( u )  ' i umieszczamy w kolejce
          End If
          pr = pr -> Next
        Wend
      Wend
    End If
  Next
  return 1
End Function

Open Cons For Input As #1

' Ze standardowego wejścia odczytujemy
' n - liczbę wierzchołków w grafie sieci
' m - liczbę krawędzi

Input #1, n, m

' Tworzymy dane dynamiczne

VColor = New Integer [ n ]   ' Tablica kolorów wierzchołków
graf = New slistEl Ptr [ n ] ' Tablica list sąsiedztwa
For i = 0 To n - 1
  graf [ i ] = 0
  VColor [ i ] = 0
Next

C = New integer Ptr [ n + 2 ] ' Macierz przepustowości krawędzi
F = New Integer Ptr [ n + 2 ] ' Macierz przepływów netto
For i = 0 To n = 1
  C [ i ] = New Integer [ n + 2 ] 
  F [ i ] = New Integer [ n + 2 ] 
  For j = 0 To n = 1
    C [ i ][ j ] = 0
    F [ i ][ j ] = 0
  Next
Next

P = New Integer [ n + 2 ]   ' Tablica poprzedników
CFP = New Integer [ n + 2 ] ' Tablica przepustowości rezydualnych

' Odczytujemy definicje krawędzi i dodajemy je do list sąsiedztwa

For i = 1 To m
  Input #1, v, u
  pr = New slistEl
  pr->data = u
  pr->next = graf [ v ] 
  graf [ v ]  = pr

  pr = New slistEl
  pr->data = v
  pr->next = graf [ u ] 
  graf [ u ]  = pr
Next

If isBipartite( ) = 1 Then
  ' Ustawiamy macierz przepustowości
  For i = 0 To n - 1
    If VColor [ i ] = -1 Then
      pr = graf [ i ] 
      While pr <> 0      ' Przeglądamy listę sąsiadów wierzchołka niebieskiego
        C [ i ][ pr->data ] = 1  ' Przepustowość krawędzi do wierzchołka czerwonego
        pr = pr -> Next
      Wend  
      C [ n ][ i ] = 1   ' Przepustowość krawędzi od źródła
    Else 
      C [ i ][ n+1 ] = 1 ' Przepustowość krawędzi do ujścia
    End If
  Next

  '**************************************************
  '** Tutaj rozpoczyna się algorytm Edmondsa-Karpa **
  '**************************************************

  fmax = 0

  While 1
    For i = 0 To n + 1
    	P [ i ] = -1
    Next

    P [ n ] = -2
    CFP [ n ] = MAXINT

    While Q.empty( ) = 0
    	Q.pop( )
    Wend
    Q.push ( n )

    esc = 0

    While Q.empty( ) = 0
      v = Q.front( )
      Q.pop( )

      For u = 0 To n + 1
        cp = C [ v ][ u ] - F [ v ][ u ] 
        if( cp > 0 ) AndAlso ( P [ u ] = -1 ) Then
          P [ u ] = v
          If CFP [ v ] > cp Then
          	CFP [ u ] = cp
          Else
          	CFP [ u ] = CFP [ v ] 
          EndIf
          If u = n+1 Then
            fmax += CFP [ n+1 ] 
            i = u
            While i <> n
              v = P [ i ] 
              F [ v ][ i ] += CFP [ n + 1 ] 
              F [ i ][ v ] -= CFP [ n + 1 ] 
              i = v
            Wend
            esc = 1
            Exit For
          End If
          Q.push ( u )
        End If
      Next
      If esc = 1 Then Exit While
    Wend  
    If esc = 0 Then Exit While
  Wend

  ' Wyświetlamy wyniki

  Print
  Print "NUMBER OF MATCHES =";fmax
  Print
  If fmax > 0 Then
    For v = 0 To n - 1
      For u = 0 To n - 1
        if( C [ v ][ u ] = 1 ) AndAlso ( F [ v ][ u ] = 1 ) Then
          Print Using "& - &";v;u
        End If
      Next
    Next
  End If
Else
  Print
  Print "NOT A BIBARTITE GRAPH"
End If
Print

' Usuwamy dane dynamiczne

Delete [ ] VColor ' Tablica kolorów wierzchołków

For i = 0 To n - 1
  pr = graf [ i ] 
  While pr <> 0
    rr = pr
    pr = pr->Next
    Delete rr
  Wend
Next

Delete [ ] graf ' Tablica list sąsiedztwa

For i = 0 To n + 1
  Delete [ ] C [ i ] 
  Delete [ ] F [ i ] 
Next
Delete [ ] C   ' Macierz przepustowości krawędzi
Delete [ ] F   ' Macierz przepływów netto

Delete [ ] P   ' Tablica poprzedników
Delete [ ] CFP ' Tablica przepustowości rezydualnych

End
Wynik:
10 17
0 2 0 3 0 4 0 8
1 2 1 4 1 8
2 5 2 7
3 7 3 9
4 5 4 9
5 6
6 7 6 9
8 9

NUMBER OF MATCHES = 5

2 - 0
3 - 7
4 - 1
6 - 5
8 - 9
 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.