Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2021 mgr Jerzy Wałaszek
I LO w Tarnowie

Kojarzenie małżeństw

SPIS TREŚCI

Problem

Należy 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.

Rozwiązanie

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:

obrazek

obrazek
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 k  ≤ n.

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 ):

obrazek

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

obrazek

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.

obrazek

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

obrazek

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

obrazek

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.

obrazek

Ś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 ).

obrazek

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:

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.
Zmienne 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
kroki K06...K24
przechodzimy przez kolejne wierzchołki grafu
K06:     Jeśli matching [ v  ] > -1 obrazek color [ v  ] = true,
    to następny obieg pętli K05
pomijamy skojarzone wierzchołki oraz wierzchołki kawalerów
K07     Ustaw wszystkie elementy 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 kroki K10...K24
 
K10:         x  ← Q.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:
        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:             x  ← augment [ 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  

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 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.
Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli ):
obrazek      10 11
0 8 0 7
1 8 1 6 1 5
2 5
3 9 3 8 3 6
4 8 4 7
Pascal
// 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.
C++
// 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;
}
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
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
©2021 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.