Kojarzenie małżeństw


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

Problem

Dobrać w pary małżeńskie n panien i n kawalerów, gdzie każda z panien jest skłonna wyjść za mąż za jednego z k kawalerów.



Na pierwszy rzut oka nie jest tutaj widoczny problem grafowy. Jednakże przyjrzyjmy się bliżej temu zadaniu. Niech wierzchołkami naszego grafu będą panny i kawalerowie. Krawędzie natomiast niech określają preferencje poszczególnych panien, czyli prowadzą do kawalerów, za których panny są skłonne wyjść za mąż. Ponieważ związki są heteroseksualne, od razu możemy stwierdzić, iż powstaje graf dwudzielny – jedną klasą wierzchołków są panny, a drugą kawalerowie. Krawędzie łączą tylko panny z kawalerami – nie ma połączeń pomiędzy pannami ani pomiędzy kawalerami.

 

Przykład:

Mamy 5 panien:

Anna (0), Beata (1), Celina  (2), Dorota (3), Ewa (4)

oraz pięciu kawalerów:

Fryderyk (5), Grzegorz (6), Henryk (7), Igor (8), Jan (9).

Preferencje każdej z panien są następujące:

Anna  Henryk, Igor         0 →  7, 8
Beata  Fryderyk, Grzegorz, Igor   1 →  5, 6, 8
Celina  Fryderyk   2 →  5
Dorota  Grzegorz, Igor, Jan   3 →  6, 8, 9
Ewa  Henryk, Igor   4 →  7, 8

Na podstawie tych danych tworzymy graf dwudzielny:

 

 

Photograph of Philip Hall
Philip Hall

Rozwiązalność problemu skojarzenia małżeństw określa twierdzenie Philipa Halla:

Problem małżeństw jest rozwiązywalny, jeśli każdy podzbiór k panien, akceptuje jako przyszłych mężów co najmniej k kawalerów, gdzie kn.

Okazuje się, że jest to warunek konieczny i wystarczający. Dowód tego twierdzenia możesz znaleźć w sieci lub w podręczniku teorii grafów. Warunek ten oznacza, iż dla każdej grupy panien liczba kawalerów jest wystarczająca do skojarzenia wszystkich małżeństw. Problemem pozostaje znalezienie takiego skojarzenia.

Poszukiwane skojarzenie jest również grafem dwudzielnym zbudowanym z wierzchołków grafu wyjściowego i z niektórych jego krawędzi w taki sposób, iż każdy wierzchołek posiada stopień jeden – czyli łączy się krawędzią dokładnie z jednym wierzchołkiem klasy przeciwnej.

Konstrukcję skojarzenia rozpoczynamy od wyboru pierwszej panny (Anny) i połączenia jej krawędzią z akceptowanym przez nią kawalerem (Henrykiem):

 

Następnie bierzemy kolejną pannę (Beatę) i łączymy ją z jej kawalerem (Fryderykiem).

 

 

Operację tę kontynuujemy do momentu, aż kolejnej zabraknie kawalerów. W naszym przypadku tak stanie się teraz z Celiną. Celinie podoba się tylko Fryderyk. Niestety, Fryderyk został przydzielony Beacie. Na szczęście (twierdzenie Halla) Beata lubi jeszcze Grzegorza oraz Igora. Daje nam to możliwość manewrów i zmiany bieżących skojarzeń małżeństw, aby Celina mogła poślubić swojego upragnionego Fryderyka. W tym celu wprowadźmy pojęcie ścieżki naprzemiennej (ang. alternating path):

Ścieżka naprzemienna jest ścieżką w grafie dwudzielnym, która przebiega na przemian przez krawędzie swobodne (nieskojarzone) i skojarzone. Ścieżkę rozpoczynamy zawsze od krawędzi swobodnej.

Zbudujmy ścieżkę naprzemienną, wychodzącą od Celiny. Ścieżkę budujemy dotąd, aż napotkamy nieskojarzonego jeszcze kawalera.

 

 

Ścieżka biegnie przez: Celinę → Fryderyka → Beatę → Grzegorza. Krawędzie zielone są krawędziami skojarzonymi. Krawędzie czerwone są krawędziami wolnymi. Ścieżka kończy się na Grzegorzu, który nie został jeszcze skojarzony z żadną panną.

Ścieżkę naprzemienną, w której węzły początkowy i końcowy są nieskojarzone (wolne), nazywamy ścieżką rozszerzającą (ang. augmenting path). Nazwa ta pochodzi z faktu, iż ścieżka rozszerzająca pozwoli nam rozszerzyć bieżące skojarzenie par małżeńskich o nową parę. W tym celu na ścieżce rozszerzającej krawędzie skojarzone zastępujemy krawędziami wolnymi (usuwamy dany związek panny z kawalerem), a krawędzie wolne czynimy krawędziami skojarzonymi (tworzymy nowy związek panny z innym akceptowanym przez nią kawalerem). W efekcie Celina otrzyma za męża swojego Fryderyka, a inne panny, które poprzednio były skojarzone z kawalerami, wciąż mają przydzielonych kandydatów na mężów – graf skojarzenia otrzymał nową krawędź, czyli został rozszerzony.

 

 

Z Dorotą nie ma problemów, ponieważ lubi Igora, który wciąż jest wolny.

 

 

Pozostała nam ostatnia panna i ostatni kawaler. Niestety, Ewa nie chce wyjść za mąż za Jana. Szukamy zatem w grafie ścieżki rozszerzającej, która prowadzi od Ewy do Jana. Jeśli graf spełnia twierdzenie Halla, to ścieżka ta zawsze istnieje.

 

 

Ścieżka rozszerzająca przebiega przez: Ewę → Igora → Dorotę → Jana. Zamieniamy na tej ścieżce krawędzie wolne na skojarzone i skojarzone na wolne. W efekcie otrzymujemy zupełne skojarzenie małżeństw (ang. perfect matching).

 

 

Skojarzyliśmy pary małżeńskie:

Anna + Henryk
Beata + Grzegorz
Celina + Fryderyk
Dorota + Jan
Ewa + Igor

Teraz możemy przystąpić do zaprojektowania odpowiedniego algorytmu kojarzenia małżeństw (problem ten można rozszerzyć na kojarzenie w pary dowolnych obiektów, np. pracowników o różnych kwalifikacjach i prac do wykonania, które wymagają określonych kwalifikacji). Algorytm jest następujący:

Przejdź przez kolejne wierzchołki grafu. Jeśli wierzchołek jest nieskojarzoną panną, to spróbuj utworzyć ścieżkę rozszerzającą prowadzącą do pierwszego napotkanego wolnego wierzchołka kawalera. Ścieżka rozszerzająca jest ścieżką naprzemienną, która zawiera na przemian krawędzie wolne i skojarzone (łączące wierzchołki skojarzone ze sobą). Jeśli znajdziemy ścieżkę rozszerzającą (może jej nie być, jeśli nie jest spełniony w grafie warunek Halla), to wszystkie krawędzie wolne zmieniamy na skojarzone, a wszystkie krawędzie skojarzone zamieniamy na wolne. Do znalezienia ścieżki możemy posłużyć się metodą BFS oraz drzewem rozpinającym w szerz – odpowiednio przystosowanymi do warunków tego algorytmu. Ponieważ nie jest nam potrzebna pełna struktura drzewa rozpinającego, lecz jedynie ścieżki od jego liści do korzenia, to drzewo w prosty sposób można zrealizować w tablicy, której elementy o indeksie i będą zawierały numery wierzchołków grafu będące wierzchołkami nadrzędnymi w drzewie rozpinającym w stosunku do wierzchołka i-tego. Korzeń drzewa może być reprezentowany w tej tablicy przez wartość -1. Takie rozwiązanie umożliwi przejście od liścia do korzenia – wystarczy podążać za kolejnymi numerami wierzchołków nadrzędnych.

Drzewo rozpinające w szerz tworzymy następująco:

  • Jeśli węzeł jest panną, to dodajemy do drzewa wszystkie krawędzie łączące pannę z kawalerami, którzy nie zostali jeszcze odwiedzeni – powstają krawędzie nieskojarzone.
  • Jeśli węzeł jest kawalerem, to dodajemy do drzewa tylko krawędź skojarzoną.

 

Algorytm kojarzenia małżeństw

Wejście
n  –  liczba wierzchołków w grafie, n C
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
color  –  n elementowa tablica logiczna określająca rodzaj wierzchołka, true – kawaler, false – panna
Wyjście:
maching  –  n elementowa tablica skojarzeń. Indeksy elementów odpowiadają numerom wierzchołków grafu. Każdy element zawiera numer skojarzonego wierzchołka z klasy przeciwnej
 
Elementy pomocnicze:
Q  –  kolejka służąca do składowania wierzchołków grafu dla metody BFS
visited  –  n elementowa tablica logiczna służąca do zaznaczania wierzchołków odwiedzonych
augment  –  n elementowa tablica pomocnicza do tworzenia naprzemiennej ścieżki rozszerzającej, przechowuje tworzoną przez BFS strukturę drzewa rozpinającego wszerz. Element i-ty zawiera numer swojego wierzchołka nadrzędnego na drzewie rozpinającym.
v,x,y  –  numery wierzchołków, v,x,y C

 

Lista kroków:
K01 Utwórz n elementową tablicę matching.  
K02: Ustaw wszystkie elementy tablicy matching na -1 ; zerujemy tablicę skojarzeń
K03 Utwórz n elementową tablicę visited  
K04 Utwórz kolejkę Q  
K05: Dla v = 0,1,...,n - 1: wykonuj K06...K24 ; przechodzimy przez kolejne wierzchołki grafu
K06:     Jeśli matching[v] > -1 color[v] = true, to następny obieg pętli K05 ; pomijamy skojarzone wierzchołki oraz wierzchołki kawalerów
K07     Ustaw wszystkie elementy tablicy visited na false
    Wyzeruj kolejkę Q
; uruchamiamy BFS do utworzenia ścieżek rozszerzających
K08:     visited[v] ← true
    augment[v] ← -1
    Q.push(v)
; inicjujemy zmienne przed wejściem do pętli
K09:     Dopóki Q.empty() = false, wykonuj K10...K24  
K10:         xQ.front()
        Q.pop()
; pobieramy wierzchołek z początku kolejki
; pobrany wierzchołek usuwamy z kolejki
K11:         Jeśli color[x] = false, to idź do kroku K21 ; jeśli wierzchołek oznacza pannę, przechodzimy dalej
K12:         Jeśli matching[x] > -1, to idź do kroku K18 ; jeśli kawaler jest już zajęty, przechodzimy dalej
K13:         Dopóki augment[x] > -1: to wykonuj kroki K14...K16 ; tutaj obsługujemy przypadek znalezienia wolnego kawalera. Cofamy się
K14:             Jeśli color[x] = false, to idź do kroku K16 ; po ścieżce rozszerzającej w kierunku wolnej panny. Po drodze
K15:             matching[x] ← augment[x]
            matching[augment[x]] ← x
; zamieniamy ze sobą krawędzie skojarzone i nieskojarzone
K16:             xaugment[x]  
K17:         Następny obieg pętli K05 ; po zakończeniu pętli K13 wracamy na początek pętli K05
K18:         augment[matching[x]] ← x
        visited[matching[x]] ← true
; w przypadku kawalera w kolejce umieszczamy skojarzoną z nim pannę
K19:         Q.push(matching[x]) ; w ten sposób powstaje ścieżka naprzemienna.
K20:         Następny obieg pętli K09  
K21         Dla każdego sąsiada y wierzchołka x wykonuj kroki K22...K24 ; w przypadku panny w kolejce umieszczamy wszystkie, nie odwiedzone
K22:             Jeśli visited[y] = true, to następny obieg pętli K21 ; wierzchołki sąsiednie. Łączące krawędzie są krawędziami
K23:             visited[y] ← true
            augment[y] ← x
; nieskojarzonymi.
K24:             Q.push(y)  
K25: 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 dwudzielnego. Umówmy się, że para wierzchołków definiujących krawędź to panna – kawaler. Następnie program wyznacza maksymalne skojarzenie i wyświetla je.

 

Przykładowy graf dwudzielny
     10 11
0 8 0 7
1 8 1 6 1 5
2 5
3 9 3 8 3 6
4 8 4 7

 

Lazarus
// Kojarzenie małżeństw
// Data: 23.12.2013
// (C)2013 mgr Jerzy Wałaszek
//----------------------------------------

program perfmach;

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

TList = array of PslistEl;

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

    public
      constructor init;
      destructor  destroy;
      function    empty : boolean;
      function    front : integer;
      procedure   push(x : 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^.v;
end;

// Zapisuje do kolejki
//--------------------
procedure queue.push(x : integer);
var
  p : PslistEl;
begin
  new(p);
  p^.next := nil;
  p^.v    := x;
  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
  n,m,i,v,x,y      : integer;
  color,visited    : array of boolean;
  matching,augment : array of integer;
  Q                : queue;
  p,r              : PslistEl;
  graf             : TList;

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

  // Tworzymy zmienne dynamiczne

  SetLength(color,n);    // Kawalerowie (true), panny (false)
  SetLength(matching,n); // Skojarzenia
  SetLength(augment,n);  // Ścieżka rozszerzająca
  SetLength(visited,n);  // Odwiedziny
  Q.init;                // Kolejka
  SetLength(graf,n);     // Tablica list sąsiedztwa

  // Tablice list sąsiedztwa wypełniamy pustymi listami

  for i := 0 to n - 1 do graf[i] := nil;

  // Odczytujemy kolejne definicje krawędzi

  for i := 0 to m - 1 do
  begin
    read(x,y);                  // Krawędź panna --- kawaler
    new(p);                     // Tworzymy nowy element
    p^.v := y;                  // Numerujemy go jako kawaler
    p^.next := graf[x];         // Dodajemy go na początek listy panny
    graf[x] := p;
    new(p);                     // Tworzymy nowy element
    p^.v := x;                  // Numerujemy go jako pannę
    p^.next := graf[y];         // Dodajemy go na początek listy kawalera
    graf[y] := p;
    color[x] := false;          // Panna
    color[y] := true;           // Kawaler
  end;

  writeln;

  // Algorytm znajdowania maksymalnego skojarzenia

  for i := 0 to n - 1 do        // Elementy tablicy matching ustawiamy na -1
    matching[i] := -1;          // Co oznacza brak skojarzenia

  for v := 0 to n - 1 do        // Przechodzimy przez kolejne wierzchołki
    if (matching[v] = -1) and not color[v] then
    begin

      for i := 0 to n - 1 do
        visited[i] := false;    // Zerujemy tablicę odwiedzin

      while Q.empty = false do
        Q.pop;                  // Zerujemy kolejkę

      visited[v] := true;       // Oznaczamy v jako wierzchołek odwiedzony
      augment[v] := -1;         // Poprzednikiem v jest korzeń drzewa rozpinającego
      Q.push(v);                // Umieszczamy v w kolejce

      while Q.empty = false do  // Uruchamiamy BFS
      begin
        x := Q.front;           // Pobieramy x z kolejki
        Q.pop;                  // Pobrany wierzchołek usuwamy z kolejki

        if color[x] then
        begin                   // Kawalerowie
          if matching[x] = -1 then
          begin                 // Kawaler wolny
            while augment[x] > -1 do
            begin
              if color[x] then
              begin             // Zamieniamy krawędzie skojarzone z nieskojarzonymi
                matching[x] := augment[x];
                matching[augment[x]] := x;
              end;
              x := augment[x];  // Cofamy się po ścieżce rozszerzającej
            end;
            break;              // Wracamy do pętli głównej
          end
          else
          begin                 // Kawaler skojarzony
            augment[matching[x]] := x;
            visited[matching[x]] := true;
            Q.push(matching[x]);// W kolejce umieszczamy skojarzoną pannę
          end;
        end
        else
        begin                   // Panny
          p := graf[x];         // Przeglądamy kawalerów
          while p <> nil do
          begin
            y := p^.v;          // Numer kawalera
            if visited[y] = false then // Tylko kawalerowie nieskojarzeni
            begin               // są umieszczani w kolejce
              visited[y] := true;
              augment[y] := x;  // Tworzymy ścieżkę rozszerzającą
              Q.push(y);
            end;
            p := p^.next;
          end;
        end;
      end;
    end;

  // Wyświetlamy skojarzenia panna --- kawaler

  for i := 0 to n - 1 do
    if not color[i] then writeln(i,' --- ',matching[i]);

  // Usuwamy dynamiczne struktury danych

  SetLength(color,0);
  SetLength(matching,0);
  SetLength(augment,0);
  SetLength(visited,0);
  Q.destroy;

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

  SetLength(graf,0);

end.
Code::Blocks
// Kojarzenie małżeństw
// Data: 23.12.2013
// (C)2013 mgr Jerzy Wałaszek
//----------------------------------------

#include <iostream>

using namespace std;

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

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

const int MAXINT = -2147483647;

// 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 x);
    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->v;
  else     return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push(int x)
{
  slistEl * p = new slistEl;
  p->next = NULL;
  p->v    = x;
  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 ***
// **********************

int main()
{
  int n,m,i,v,x,y, * matching, * augment;
  slistEl * p,* r, ** graf;
  bool * visited, * color;
  queue Q;

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

  // Tworzymy zmienne dynamiczne

  color    = new bool[n];       // Kawalerowie (true), panny (false)
  matching = new int[n];        // Skojarzenia
  augment  = new int[n];        // Ścieżka rozszerzająca
  visited  = new bool[n];       // Odwiedziny
  graf     = new slistEl * [n]; // Tworzymy tablicę list sąsiedztwa

  // Tablicę wypełniamy pustymi listami

  for(i = 0; i < n; i++) graf[i] = NULL;

  // Odczytujemy kolejne definicje krawędzi

  for(i = 0; i < m; i++)
  {
    cin >> x >> y;              // Krawędź panna --- kawaler
    p = new slistEl;            // Tworzymy nowy element
    p->v = y;                   // Numerujemy go jako kawaler
    p->next = graf[x];          // Dodajemy go na początek listy panny
    graf[x] = p;
    p = new slistEl;            // Tworzymy nowy element
    p->v = x;                   // Numerujemy go jako pannę
    p->next = graf[y];          // Dodajemy go na początek listy kawalera
    graf[y] = p;
    color[x] = false;           // Panna
    color[y] = true;            // Kawaler
  }

  cout << endl;

  // Algorytm znajdowania maksymalnego skojarzenia

  for(i = 0; i < n; i++)        // Elementy tablicy matching ustawiamy na -1
    matching[i] = -1;           // Co oznacza brak skojarzenia

  for(v = 0; v < n; v++)        // Przechodzimy przez kolejne wierzchołki
    if((matching[v] == -1) && !color[v])
    {
      for(i = 0; i < n; i++)
        visited[i] = false;     // Zerujemy tablicę odwiedzin

      while(!Q.empty()) Q.pop();// Zerujemy kolejkę

      visited[v] = true;        // Oznaczamy v jako wierzchołek odwiedzony
      augment[v] = -1;          // Poprzednikiem v jest korzeń drzewa rozpinającego
      Q.push(v);                // Umieszczamy v w kolejce

      while(!Q.empty())         // Uruchamiamy BFS
      {
        x = Q.front();          // Pobieramy x z kolejki
        Q.pop();                // Pobrany wierzchołek usuwamy z kolejki

        if(color[x])
        {                       // Kawalerowie
          if(matching[x] == -1)
          {                     // Kawaler wolny
            while(augment[x] > -1)
            {
              if(color[x])
              {                 // Zamieniamy krawędzie skojarzone z nieskojarzonymi
                matching[x] = augment[x];
                matching[augment[x]] = x;
              }
              x = augment[x];   // Cofamy się po ścieżce rozszerzającej
            }
            break;              // Wracamy do pętli głównej
          }
          else
          {                     // Kawaler skojarzony
            augment[matching[x]] = x;
            visited[matching[x]] = true;
            Q.push(matching[x]);// W kolejce umieszczamy skojarzoną pannę
          }
        }
        else
        {                       // Panny
          p = graf[x];          // Przeglądamy kawalerów
          while(p)
          {
            y = p->v;           // Numer kawalera
            if(!visited[y])     // Tylko kawalerowie nieskojarzeni
            {                   // są umieszczani w kolejce
              visited[y] = true;
              augment[y] = x;   // Tworzymy ścieżkę rozszerzającą
              Q.push(y);
            }
            p = p->next;
          }
        }
      }
    }

  // Wyświetlamy skojarzenia panna --- kawaler

  for(i = 0; i < n; i++)
    if(!color[i]) cout << i << " --- " << matching[i] << endl;

  // Usuwamy dynamiczne struktury danych

  delete [] color;
  delete [] matching;
  delete [] augment;
  delete [] visited;

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

  delete [] graf;

  return 0;
}
Free Basic
' Kojarzenie małżeństw
' Data: 23.12.2013
' (C)2013 mgr Jerzy Wałaszek
'----------------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa i kolejki

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

Const MAXINT = 2147483647

' 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->v
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push(ByVal x As Integer)
  Dim p As slistEl Ptr
  p = new slistEl
  p->next = 0
  p->v = x
  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 As Integer n,m,i,v,x,y
Dim As slistEl Ptr p,r
Dim As slistEl Ptr Ptr graf
Dim As Integer Ptr visited,matching,augment,ccolor
Dim As queue Q

Open Cons For Input As #1

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

' Tworzymy zmienne dynamiczne

ccolor   = New Integer[n]      ' Kawalerowie (true), panny (false)
matching = New Integer[n]      ' Skojarzenia
augment  = New Integer[n]      ' Ścieżka rozszerzająca
visited  = New Integer[n]      ' Odwiedziny
graf     = New slistEl Ptr [n] ' Tworzymy tablicę list sąsiedztwa

' Tablicę wypełniamy pustymi listami

For i = 0 To n - 1
  graf[i] = 0
Next

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m -1
  Input #1,x,y              ' Krawędź panna --- kawaler
  p = New slistEl           ' Tworzymy nowy element
  p->v = y                  ' Numerujemy go jako kawaler
  p->next = graf[x]         ' Dodajemy go na początek listy panny
  graf[x] = p
  p = new slistEl           ' Tworzymy nowy element
  p->v = x                  ' Numerujemy go jako pannę
  p->next = graf[y]         ' Dodajemy go na początek listy kawalera
  graf[y] = p
  ccolor[x] = 0             ' Panna
  ccolor[y] = 1             ' Kawaler
Next

Close #1

Print

' Algorytm znajdowania maksymalnego skojarzenia

For i = 0 To n - 1                ' Elementy tablicy matching ustawiamy na -1
  matching[i] = -1                ' Co oznacza brak skojarzenia
Next

For v = 0 To n - 1                ' Przechodzimy przez kolejne wierzchołki
  If (matching[v] = -1) AndAlso (ccolor[v] = 0) Then
    For i = 0 To n - 1
      visited[i] = 0              ' Zerujemy tablicę odwiedzin
    Next
    
    While Q.empty() = 0
      Q.pop()                     ' Zerujemy kolejkę
    Wend

    visited[v] = 1                ' Oznaczamy v jako wierzchołek odwiedzony
    augment[v] = -1               ' Poprzednikiem v jest korzeń drzewa rozpinającego
    Q.push(v)                     ' Umieszczamy v w kolejce

    While Q.empty() = 0           ' Uruchamiamy BFS
      x = Q.front()               ' Pobieramy x z kolejki
      Q.pop()                     ' Pobrany wierzchołek usuwamy z kolejki

      If ccolor[x] = 1 Then       ' Kawalerowie 
        If matching[x] = -1 Then  ' Kawaler wolny          
          While augment[x] > -1
            If ccolor[x] = 1 Then ' Zamieniamy krawędzie skojarzone z nieskojarzonymi 
              matching[x] = augment[x]
              matching[augment[x]] = x
            End If
            x = augment[x]        ' Cofamy się po ścieżce rozszerzającej
          Wend
          Exit While              ' Wracamy do pętli głównej
        Else                      ' Kawaler skojarzony
          augment[matching[x]] = x
          visited[matching[x]] = 1
          Q.push(matching[x])     ' W kolejce umieszczamy skojarzoną pannę
        End If
      Else                        ' Panny 
        p = graf[x]               ' Przeglądamy kawalerów
        While p
          y = p->v                ' Numer kawalera
          If visited[y] = 0 Then  ' Tylko kawalerowie nieskojarzeni
            visited[y] = 1        ' są umieszczani w kolejce
            augment[y] = x        ' Tworzymy ścieżkę rozszerzającą
            Q.push(y)
          End If
          p = p->Next
        Wend
      End If
    Wend
  End If 
Next

' Wyświetlamy skojarzenia panna --- kawaler

For i = 0 To n - 1
  If ccolor[i] = 0 then Print i;" ---";matching[i]
Next

' Usuwamy dynamiczne struktury danych

Delete [] ccolor
Delete [] matching
Delete [] augment
Delete [] visited
  
For i = 0 To n - 1
  p = graf[i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [] graf

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

0 --- 7
1 --- 6
2 --- 5
3 --- 9
4 --- 8

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



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

©2017 mgr Jerzy Wałaszek

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