การจับคู่สองฝ่ายสูงสุด

การจับคู่แบบสองฝ่ายคือชุดของขอบในกราฟที่ถูกเลือกในลักษณะที่ว่าจะไม่มีสองขอบในชุดนั้นที่จะแชร์จุดสิ้นสุด การจับคู่สูงสุดตรงกับจำนวนขอบสูงสุด

เมื่อพบการจับคู่สูงสุด เราไม่สามารถเพิ่มขอบอื่นได้ หากมีการเพิ่มขอบหนึ่งลงในกราฟที่ตรงกันสูงสุด ขอบนั้นจะไม่ตรงกันอีกต่อไป สำหรับกราฟสองส่วน อาจมีการจับคู่สูงสุดได้มากกว่าหนึ่งรายการ

อินพุตและเอาต์พุต

Input:
The adjacency matrix.
0 1 1 0 0 0
1 0 0 1 0 0
0 0 1 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 1

Output:
Maximum number of applicants matching for job: 5

อัลกอริทึม

bipartiteMatch(u, เข้าชม, กำหนด)

อินพุต: โหนดเริ่มต้น รายการที่เข้าชมเพื่อติดตาม กำหนดรายการเพื่อกำหนดโหนดกับโหนดอื่น

ผลลัพธ์ − คืนค่า จริง เมื่อจับคู่จุดยอด u เป็นไปได้

Begin
   for all vertex v, which are adjacent with u, do
      if v is not visited, then
         mark v as visited
         if v is not assigned, or bipartiteMatch(assign[v], visited, assign) is true, then
            assign[v] := u
            return true
   done
   return false
End

maxMatch(กราฟ)

อินพุต - กราฟที่กำหนด

ผลลัพธ์ − จำนวนการแข่งขันสูงสุด

Begin
   initially no vertex is assigned
   count := 0
   for all applicant u in M, do
      make all node as unvisited
      if bipartiteMatch(u, visited, assign), then
         increase count by 1
   done
End

ตัวอย่าง

#include <iostream>
#define M 6
#define N 6
using namespace std;

bool bipartiteGraph[M][N] = {    //A graph with M applicant and N jobs
   {0, 1, 1, 0, 0, 0},
   {1, 0, 0, 1, 0, 0},
   {0, 0, 1, 0, 0, 0},
   {0, 0, 1, 1, 0, 0},
   {0, 0, 0, 0, 0, 0},
   {0, 0, 0, 0, 0, 1}
};

bool bipartiteMatch(int u, bool visited[], int assign[]) {
   for (int v = 0; v < N; v++) {    //for all jobs 0 to N-1
      if (bipartiteGraph[u][v] && !visited[v]) {    //when job v is not visited and u is interested
         visited[v] = true;    //mark as job v is visited
         //when v is not assigned or previously assigned
         if (assign[v] < 0 || bipartiteMatch(assign[v], visited, assign)) {
            assign[v] = u;    //assign job v to applicant u
            return true;
         }
      }
   }
   return false;
}

int maxMatch() {
   int assign[N];    //an array to track which job is assigned to which applicant
   for(int i = 0; i<N; i++)
      assign[i] = -1;    //initially set all jobs are available
   int jobCount = 0;

   for (int u = 0; u < M; u++) {    //for all applicants
      bool visited[N];
      for(int i = 0; i<N; i++)
         visited[i] = false;    //initially no jobs are visited
      if (bipartiteMatch(u, visited, assign))    //when u get a job
         jobCount++;
   }
   return jobCount;
}

int main() {
   cout << "Maximum number of applicants matching for job: " << maxMatch();
}

ผลลัพธ์

Maximum number of applicants matching for job: 5