Serwis Edukacyjny w I-LO w Tarnowie ![]() 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 |
ProblemNależy dobrać |
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:
oraz pięciu kawalerów:
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:
![]() 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
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 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.
Ś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:
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
Drzewo rozpinające wszerz tworzymy następująco:
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] > -1color[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: x ← Q.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
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. |
![]() |
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. |
// 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 |
![]() |
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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.