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

©2025 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 tak, 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 wszerz – 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 wszerz 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.

Elementy pomocnicze:

Q : kolejka służąca do składowania wierzchołków grafu dla metody BFS.
vs : 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
K03: Utwórz n elementową tablicę vs
K04: Utwórz kolejkę Q
K05: Dla v = 0, 1, …, n-1: ; przechodzimy przez kolejne wierzchołki grafu
     wykonuj kroki K06…K24
K06:   Jeśli matching[v] > -1 obrazek color[v] = true, ; pomijamy skojarzone
       to następny obieg pętli K05 ; wierzchołki oraz wierzchołki kawalerów
K07:   Ustaw wszystkie elementy vs na false ; uruchamiamy BFS
       Wyzeruj kolejkę Q ; do utworzenia ścieżek rozszerzających
K08:   vs[v] ← true ; inicjujemy zmienne przed wejściem do pętli
       augment[v] ← -1
       Q.push(v)
K09:   Dopóki Q.empty() = false, 
       wykonuj kroki K10…K24
K10:     xQ.front() ; pobieramy wierzchołek z początku kolejki
         Q.pop() ; pobrany wierzchołek usuwamy z kolejki
K11:     Jeśli color[x] = false, ; jeśli wierzchołek oznacza pannę,
         to idź do kroku K21 ; przechodzimy dalej
K12:     Jeśli matching[x] > -1, ; jeśli kawaler jest już zajęty,
         to idź do kroku K18 ; przechodzimy dalej
K13:     Dopóki augment[x] > -1: ; tutaj obsługujemy przypadek znalezienia
         wykonuj kroki K14…K16 ; wolnego kawalera. Cofamy się
K14:       Jeśli color[x] = false, ; po ścieżce rozszerzającej
           to idź do kroku K16 ; w kierunku wolnej panny. Po drodze
K15:       matching[x] ← augment[x] ; zamieniamy ze sobą krawędzie
           matching[augment[x]] ← x ; 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 ; w przypadku kawalera w kolejce
         vs[matching[x]] ← true ; 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: ; w przypadku panny w kolejce
         wykonuj kroki K22…K24 ; umieszczamy wszystkie, nie odwiedzone
K22:       Jeśli vs[y] = true, ; wierzchołki sąsiednie.
           to następny obieg pętli K21 ; Łączące krawędzie są krawędziami
K23:       vs[y] ← true ; nieskojarzonymi.
           augment[y] ← x
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
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

TList = array of PSLel;

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

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

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

// Konstruktor
//------------
constructor queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor
//-----------
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 : PSLel;
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 : PSLel;
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, vs : array of boolean;
  matching, augment : array of integer;
  Q : queue;
  p, r : PSLel;
  graf : TList;

begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy zmienne dynamiczne
  //----------------------------
  // Kawalerowie (true),
  // panny (false)
  SetLength(color, n);
  // Skojarzenia
  SetLength(matching, n);
  // Ścieżka rozszerzająca
  SetLength(augment, n);
  // Odwiedziny
  SetLength(vs, n);
  // Kolejka
  Q.init;
  // Tablica list sąsiedztwa
  SetLength(graf, n);
  // 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
    // Krawędź panna-kawaler
    read(x, y);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako kawaler
    p^.v := y;
    // Dodajemy go na początek
    // listy panny
    p^.next := graf[x];
    graf[x] := p;
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako pannę
    p^.v := x;
    // Dodajemy go na początek
    // listy kawalera
    p^.next := graf[y];
    graf[y] := p;
    // Panna
    color[x] := false;
    // Kawaler
    color[y] := true;
  end;
  writeln;
  // Algorytm znajdowania
  // maksymalnego skojarzenia
  //-------------------------
  // Elementy tablicy matching
  // ustawiamy na -1,
  // co oznacza brak skojarzenia
  for i := 0 to n-1 do
    matching[i] := -1;
  // Przechodzimy przez
  // kolejne wierzchołki
  for v := 0 to n-1 do
    if (matching[v] = -1) and
        not color[v] then
    begin
      for i := 0 to n-1 do
        // Zerujemy tablicę odwiedzin
        vs[i] := false;
      while not Q.empty do
        // Zerujemy kolejkę
        Q.pop;
      // Oznaczamy v jako
      // wierzchołek odwiedzony
      vs[v] := true;
      // Poprzednikiem v jest
      // korzeń drzewa rozpinającego
      augment[v] := -1;
      // Umieszczamy v w kolejce
      Q.push(v);
      // Uruchamiamy BFS
      while Q.empty = false do
      begin
        // Pobieramy x z kolejki
        x := Q.front;
        // Pobrany wierzchołek
        // usuwamy z kolejki
        Q.pop;
        if color[x] then
        // Kawalerowie
        begin
          if matching[x] = -1 then
          // Kawaler wolny
          begin
            while augment[x] > -1 do
            begin
              if color[x] then
              // Zamieniamy krawędzie
              // skojarzone
              // z nieskojarzonymi
              begin
                matching[x] := augment[x];
                matching[augment[x]] := x;
              end;
              // Cofamy się po ścieżce
              // rozszerzającej
              x := augment[x];
            end;
            // Wracamy do pętli głównej
            break;
          end
          else
          // Kawaler skojarzony
          begin
            augment[matching[x]] := x;
            vs[matching[x]] := true;
            // W kolejce umieszczamy
            // skojarzoną pannę
            Q.push(matching[x]);
          end;
        end
        else
        // Panny
        begin
          // Przeglądamy kawalerów
          p := graf[x];
          while p <> nil do
          begin
            // Numer kawalera
            y := p^.v;
            // Tylko kawalerowie
            // nieskojarzeni
            if vs[y] = false then
            // są umieszczani w kolejce
            begin
              vs[y] := true;
              // Tworzymy ścieżkę
              // rozszerzającą
              augment[y] := x;
              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(vs, 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 SLel
{
  SLel * next;
  int v;
};

const int MAXINT = 2147483647;

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

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

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

// Konstruktor
//------------
queue::queue()
{
  head = tail = nullptr;
}

// Destruktor
//-----------
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)
{
  SLel * p = new SLel;
  p->next = nullptr;
  p->v    = x;
  if(tail) tail->next = p;
  else     head = p;
  tail = p;
}

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

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

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

  // Czytamy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy zmienne dynamiczne
  //----------------------------
  // Kawalerowie (true),
  // panny (false)
  color = new bool [n];
  // Skojarzenia
  matching = new int [n];
  // Ścieżka rozszerzająca
  augment = new int [n];
  // Odwiedziny
  vs = new bool [n];
  // Tworzymy tablicę
  // list sąsiedztwa
  graf = new SLel * [n];
  // Tablicę wypełniamy
  // pustymi listami
  for(i = 0; i < n; i++)
    graf[i] = nullptr;
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Krawędź panna-kawaler
    cin >> x >> y;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako kawaler
    p->v = y;
    // Dodajemy go
    // na początek listy panny
    p->next = graf[x];
    graf[x] = p;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako pannę
    p->v = x;
    // Dodajemy go na początek
    // listy kawalera
    p->next = graf[y];
    graf[y] = p;
    color[x] = false; // Panna
    color[y] = true; // Kawaler
  }
  cout << endl;
  // Algorytm znajdowania
  // maksymalnego skojarzenia
  //-------------------------
  // Elementy tablicy matching
  // ustawiamy na -1
  for(i = 0; i < n; i++)
    // Co oznacza brak skojarzenia
    matching[i] = -1;
  // Przechodzimy przez
  // kolejne wierzchołki
  for(v = 0; v < n; v++)
    if((matching[v] == -1) &&
       !color[v])
    {
      for(i = 0; i < n; i++)
        // Zerujemy
        // tablicę odwiedzin
        vs[i] = false;
      while(!Q.empty())
        // Zerujemy kolejkę
        Q.pop();
      // Oznaczamy v jako
      // wierzchołek odwiedzony
      vs[v] = true;
      // Poprzednikiem v jest
      // korzeń drzewa rozpinającego
      augment[v] = -1;
      // Umieszczamy v w kolejce
      Q.push(v);
      // Uruchamiamy BFS
      while(!Q.empty())
      {
        // Pobieramy x z kolejki
        x = Q.front();
        // Pobrany wierzchołek
        // usuwamy z kolejki
        Q.pop();
        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;
              }
              // Cofamy się po ścieżce
              // rozszerzającej
              x = augment[x];
            }
            // Wracamy do pętli głównej
            break;
          }
          else
          // Kawaler skojarzony
          {
            augment[matching[x]] = x;
            vs[matching[x]] = true;
            // W kolejce umieszczamy
            // skojarzoną pannę
            Q.push(matching[x]);
          }
        }
        else
        // Panny
        {
          // Przeglądamy kawalerów
          p = graf[x];
          while(p)
          {
            // Numer kawalera
            y = p->v;
            // Tylko kawalerowie
            // nieskojarzeni
            if(!vs[y])
            // są umieszczani
            // w kolejce
            {
              vs[y] = true;
              // Tworzymy
              // ścieżkę rozszerzającą
              augment[y] = x;
              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 [] vs;
  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 SLel
  next As SLel Ptr
  v As Integer
End Type

Const MAXINT = 2147483647

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As SLel Ptr
    tail As SLel 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
'------------
Constructor queue
  head = 0
  tail = 0
End Constructor

' Destruktor
'-----------
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 SLel Ptr
  p = new SLel
  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 SLel 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 SLel Ptr p, r
Dim As SLel Ptr Ptr graf
Dim As Integer Ptr vs, matching, _
                   augment, ccolor
Dim As queue Q

Open Cons For Input As #1
' Czytamy liczbę
' wierzchołków i krawędzi
Input #1, n, m
' Tworzymy zmienne dynamiczne
'----------------------------
' Kawalerowie (true), panny (false)
ccolor = New Integer [n]
' Skojarzenia
matching = New Integer [n]
' Ścieżka rozszerzająca
augment = New Integer [n]
' Odwiedziny
vs = New Integer [n]
' Tworzymy tablicę list sąsiedztwa
graf = New SLel Ptr [n]
' 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
  ' Krawędź panna-kawaler
  Input #1, x, y
  ' Tworzymy nowy element
  p = New SLel
  ' Numerujemy go jako kawaler
  p->v = y
  ' Dodajemy go na początek listy panny
  p->next = graf[x]
  graf[x] = p
  ' Tworzymy nowy element
  p = new SLel
  ' Numerujemy go jako pannę
  p->v = x
  ' Dodajemy go na początek
  ' listy kawalera
  p->next = graf[y]
  graf[y] = p
  ccolor[x] = 0 ' Panna
  ccolor[y] = 1 ' Kawaler
Next
Close #1
Print
' Algorytm znajdowania
' maksymalnego skojarzenia
'-------------------------
' Elementy tablicy matching
' ustawiamy na -1
For i = 0 To n-1
  ' Co oznacza brak skojarzenia
  matching[i] = -1
Next
' Przechodzimy przez kolejne wierzchołki
For v = 0 To n-1
  If (matching[v] = -1) AndAlso _
     (ccolor[v] = 0) Then
    For i = 0 To n-1
      ' Zerujemy tablicę odwiedzin
      vs[i] = 0
    Next
    While Q.empty = 0
      ' Zerujemy kolejkę
      Q.pop
    Wend
    ' Oznaczamy v jako
    ' wierzchołek odwiedzony
    vs[v] = 1
    ' Poprzednikiem v jest korzeń
    ' drzewa rozpinającego
    augment[v] = -1
    ' Umieszczamy v w kolejce
    Q.push(v)
    ' Uruchamiamy BFS
    While Q.empty = 0
      ' Pobieramy x z kolejki
      x = Q.front
      ' Pobrany wierzchołek
      ' usuwamy z kolejki
      Q.pop
      ' Kawalerowie
      If ccolor[x] = 1 Then
        ' Kawaler wolny
        If matching[x] = -1 Then
          While augment[x] > -1
            ' Zamieniamy krawędzie
            ' skojarzone
            ' z nieskojarzonymi
            If ccolor[x] = 1 Then
              matching[x] = augment[x]
              matching[augment[x]] = x
            End If
            ' Cofamy się
            ' po ścieżce rozszerzającej
            x = augment[x]
          Wend
          ' Wracamy do pętli głównej
          Exit While
        ' Kawaler skojarzony
        Else
          augment[matching[x]] = x
          vs[matching[x]] = 1
          ' W kolejce umieszczamy
          ' skojarzoną pannę
          Q.push(matching[x])
        End If
      Else ' Panny
        ' Przeglądamy kawalerów
        p = graf[x]
        While p
          ' Numer kawalera
          y = p->v
          ' Tylko kawalerowie
          ' nieskojarzeni
          If vs[y] = 0 Then
            ' są umieszczani w kolejce
            vs[y] = 1
            ' Tworzymy
            ' ścieżkę rozszerzającą
            augment[y] = x
            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 [] vs
For i = 0 To n-1
  p = graf[i]
  While p
    r = p
    p = p->next
    Delete r
  Wend
Next
Delete [] graf
End
Python (dodatek)
# Kojarzenie małżeństw
# Data: 23.01.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# Klasa dla dynamicznej tablicy list
# sąsiedztwa i kolejki
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0

MAXINT = 2147483647

# Definicja typu obiektowego Queue
class Queue:
    # Konstruktor
    def __init__(self):
        self.head = None
        self.tail = None


    # Destruktor
    def __del__(self):
        while not self.empty():
            self.pop()


    # Sprawdza, czy kolejka jest pusta
    def empty(self):
        if not self.head: return True
        return False


    # Zwraca początek kolejki.
    # Wartość specjalna to -MAXINT
    def front(self):
        global MAXINT
        if not self.head:
            return -MAXINT
        else:
            return self.head.v


    # Zapisuje do kolejki
    def push(self, x):
        p = SLel()
        p.next = None
        p.v = x
        if not self.tail:
            self.head = p
        else:
            self.tail.next = p
        self.tail = p

    # Usuwa z kolejki
    def pop(self):
        if self.head:
            self.head = self.head.next
            if not self.head:
                self.tail = None


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

q = Queue()
# Czytamy liczbę
# wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy zmienne dynamiczne
#----------------------------
# Kawalerowie (true), panny (false)
ccolor = [False] * n
# Skojarzenia
matching = [-1] * n
# Ścieżka rozszerzająca
augment = [0] * n
# Odwiedziny
vs = [False] * n
# Tworzymy tablicę list sąsiedztwa
graf = [None] * n
# Odczytujemy kolejne
# definicje krawędzi
for i in range(m):
    # Krawędź panna-kawaler
    xx = input().split()
    x = int(xx[0])
    y = int(xx[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako kawaler
    p.v = y
    # Dodajemy go na początek listy panny
    p.next = graf[x]
    graf[x] = p
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako pannę
    p.v = x
    # Dodajemy go na początek
    # listy kawalera
    p.next = graf[y]
    graf[y] = p
    ccolor[x] = False # Panna
    ccolor[y] = True # Kawaler
print()
# Algorytm znajdowania
# maksymalnego skojarzenia
#-------------------------
# Przechodzimy przez kolejne wierzchołki
for v in range(n):
    if (matching[v] == -1) and \
         not ccolor[v]:
        for i in range(n):
            # Zerujemy tablicę odwiedzin
            vs[i] = False
        while not q.empty():
            # Zerujemy kolejkę
            q.pop()
        # Oznaczamy v jako
        # wierzchołek odwiedzony
        vs[v] = True
        # Poprzednikiem v jest korzeń
        # drzewa rozpinającego
        augment[v] = -1
        # Umieszczamy v w kolejce
        q.push(v)
        # Uruchamiamy BFS
        while not q.empty():
            # Pobieramy x z kolejki
            x = q.front()
            # Pobrany wierzchołek
            # usuwamy z kolejki
            q.pop()
            # Kawalerowie
            if ccolor[x]:
                # Kawaler wolny
                if matching[x] == -1:
                    while augment[x] > -1:
                        # Zamieniamy krawędzie
                        # skojarzone
                        # z nieskojarzonymi
                        if ccolor[x]:
                            matching[x] = augment[x]
                            matching[augment[x]] = x
                        # Cofamy się
                        # po ścieżce rozszerzającej
                        x = augment[x]
                    # Wracamy do pętli głównej
                    break
                # Kawaler skojarzony
                else:
                    augment[matching[x]] = x
                    vs[matching[x]] = True
                    # W kolejce umieszczamy
                    # skojarzoną pannę
                    q.push(matching[x])
            else: # Panny
                # Przeglądamy kawalerów
                p = graf[x]
                while p:
                    # Numer kawalera
                    y = p.v
                    # Tylko kawalerowie
                    # nieskojarzeni
                    if not vs[y]:
                        # są umieszczani w kolejce
                        vs[y] = True
                        # Tworzymy
                        # ścieżkę rozszerzającą
                        augment[y] = x
                        q.push(y)
                    p = p.next
# Wyświetlamy skojarzenia panna-kawaler
for i in range(n):
    if not ccolor[i]:
        print(i,"---",matching[i])
# Usuwamy dynamiczne struktury danych
del ccolor, matching, augment, vs
for i in range(n):
    while graf[i]:
        graf[i] = graf[i].next
del graf
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

do podrozdziału  do strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2025 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.