Maksymalne skojarzenia w grafach dwudzielnych


Tematy pokrewne  
Sieci przepływowe
Podstawowe pojęcia dotyczące sieci przepływowych
Maksymalny przepływ w sieci – algorytmy Forda-Fulkersona i Edmondsa-Karpa
Znajdowanie maksymalnych skojarzeń za pomocą wyznaczania maksymalnego przepływu

Podstawowe pojęcia dotyczące list
Reprezentacja list w pamięci komputera
Operacje na listach jednokierunkowych
Podstawowe pojęcia dotyczące kolejek
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Znajdowanie ścieżki w grafie
Grafy dwudzielne
Kojarzenie małżeństw

 

Problem

Dla danego grafu dwudzielnego znaleźć maksymalne skojarzenie.

 

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ą.

 

 

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.

 

 

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:

 

 

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:

 

 

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] x [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 x 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.

Elementy 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 cf(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 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 K09...K15 ; rozpoczynamy przejście BFS
K09:         vQ.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 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 x n+2 ; tworzymy macierz przepustowości
K17: Ustaw wszystkie elementy macierzy C na 0  
K18: Dla i = 0,1,...,n-1, wykonuj K19...K23 ; przechodzimy przez kolejne wierzchołki grafu
K19:     Jeśli Color[i] = 1, to idź do 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 x 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 K32...K39  
K32:         v = Q.front();  Q.pop() ; pobieramy numer wierzchołka z kolejki
K33:         Dla u = 0,1,...,n + 1, wykonuj K34...K39 ; rozpoczynamy BFS
K34:             cpC[v][u] - F[v][u] ; wyznaczamy przepustowość rezydualną kanału (v,u)
K35:             Jeśli (cp = 0) (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 K41 ; ścieżka rozszerzająca znaleziona!
K39:             Q.push(u)  
K40:     Idź do K48 ; brak ścieżki, idziemy do końcówki algorytmu
K41:     fmaxfmax + CFP[n+1] ; zwiększamy przepływ sieciowy
K42:     Dopóki un, wykonuj K43...K46 ; cofamy się po ścieżce rozszerzającej od ujścia t do źródła s
K43:         vP[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:         uv ; przechodzimy do następnej krawędzi ścieżki
K47: Idź do 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 K51 ; przeglądamy macierz przepływów
K51:     Dla u = 0,1,...,n - 1, wykonuj
        Jeśli (C[v,u] = 1) (F[v,u] = 1), to pisz v,u
; wypisujemy pary skojarzonych wierzchołków
K52: Zakończ  

 

Program

Ważne:

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

 

Program odczytuje definicję grafu nieskierowanego. Jeśli graf jest grafem dwudzielnym, to wyznacza dla niego maksymalne skojarzenie.

Przykładowe dane dla programu:

  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

 
Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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

 

 


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

©2018 mgr Jerzy Wałaszek

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

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

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