相配的 二部图 是一组边的选择方式，使两条边不共享一个端点。最大匹配是最大大小（最大边数）的匹配。在最大匹配中，如果向其添加任何边，则它不再是匹配。给定的二部图可以有多个最大匹配。 我们为什么在乎？ 现实世界中有许多问题可以通过二部匹配来解决。例如，考虑以下问题： 有M个求职者和N个工作岗位。每个申请人都有自己感兴趣的工作子集。每个职位空缺只能接受一名申请人，一名申请人只能被指定从事一项工作。找一份工作分配给求职者，让尽可能多的求职者找到工作。
null
我们强烈建议您先阅读以下帖子。 最大流问题的Ford-Fulkerson算法 最大二部匹配与最大流问题 M 最大值 B ipartite M 守望( MBP )问题可以通过将其转化为流动网络来解决（参见 这 视频了解我们是如何得出这个结论的）。以下是步骤。
1） 建立流动网络 流动网络中必须有一个源和一个汇。因此，我们添加一个源，并从源向所有申请者添加边。同样，将所有作业的边添加到水槽中。每条边的容量标记为1个单位。
2） 找到最大流量。 我们使用 福特-富尔克森算法 在步骤1中构建的流量网络中查找最大流量。最大流量实际上是我们正在寻找的MBP。
如何实施上述方法？ 让我们首先定义输入和输出表单。输入的形式是 爱德蒙矩阵 这是一个2D数组“bpGraph[M][N]”，其中有M行（针对M个求职者）和N列（针对N个工作）。如果第i位申请人对第j份工作感兴趣，则bpGraph[i][j]的值为1，否则为0。 产出是能找到工作的最大人数。 实现这一点的一个简单方法是创建一个表示 邻接矩阵表示法 具有M+N+2个顶点的有向图。打电话给 福德克森（） 为了矩阵。这个实现需要O（（M+N）*（M+N））额外的空间。 利用图是二部图且每条边的容量为0或1的事实，可以减少额外的空间并简化代码。其想法是使用DFS遍历为申请者找到工作（类似于福特富尔克森（Ford Fulkerson）中的增强路径）。我们为每个申请者调用bpm（），bpm（）是一个基于DFS的函数，它会尝试所有可能的方法为申请者分配工作。 在bpm（）中，我们会一个接一个地尝试申请者“u”感兴趣的所有工作，直到找到一份工作，或者所有工作都是在运气不佳的情况下尝试的。对于我们尝试的每一项工作，我们都会跟随。 如果一份工作没有分配给任何人，我们只需将其分配给申请人，并返回true。如果一个任务被分配给了其他人，比如x，那么我们递归地检查x是否可以被分配给其他任务。为了确保x不再获得相同的工作，我们在递归调用x之前将工作标记为“v”。如果x可以获得其他工作，我们将申请者更改为“v”，并返回true。我们使用一个数组maxR[0..N-1]来存储分配给不同工作的申请者。 如果bmp（）返回true，则表示流网络中存在一个增强路径，并且在maxBPM（）中向结果添加1个流单位。
C++
// A C++ program to find maximal // Bipartite matching. #include <iostream> #include <string.h> using namespace std; // M is number of applicants // and N is number of jobs #define M 6 #define N 6 // A DFS based recursive function // that returns true if a matching // for vertex u is possible bool bpm( bool bpGraph[M][N], int u, bool seen[], int matchR[]) { // Try every job one by one for ( int v = 0; v < N; v++) { // If applicant u is interested in // job v and v is not visited if (bpGraph[u][v] && !seen[v]) { // Mark v as visited seen[v] = true ; // If job 'v' is not assigned to an // applicant OR previously assigned // applicant for job v (which is matchR[v]) // has an alternate job available. // Since v is marked as visited in // the above line, matchR[v] in the following // recursive call will not get job 'v' again if (matchR[v] < 0 || bpm(bpGraph, matchR[v], seen, matchR)) { matchR[v] = u; return true ; } } } return false ; } // Returns maximum number // of matching from M to N int maxBPM( bool bpGraph[M][N]) { // An array to keep track of the // applicants assigned to jobs. // The value of matchR[i] is the // applicant number assigned to job i, // the value -1 indicates nobody is // assigned. int matchR[N]; // Initially all jobs are available memset (matchR, -1, sizeof (matchR)); // Count of jobs assigned to applicants int result = 0; for ( int u = 0; u < M; u++) { // Mark all jobs as not seen // for next applicant. bool seen[N]; memset (seen, 0, sizeof (seen)); // Find if the applicant 'u' can get a job if (bpm(bpGraph, u, seen, matchR)) result++; } return result; } // Driver Code int main() { // Let us create a bpGraph // shown in the above example bool bpGraph[M][N] = {{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}}; cout << "Maximum number of applicants that can get job is " << maxBPM(bpGraph); return 0; } |
JAVA
// A Java program to find maximal // Bipartite matching. import java.util.*; import java.lang.*; import java.io.*; class GFG { // M is number of applicants // and N is number of jobs static final int M = 6 ; static final int N = 6 ; // A DFS based recursive function that // returns true if a matching for // vertex u is possible boolean bpm( boolean bpGraph[][], int u, boolean seen[], int matchR[]) { // Try every job one by one for ( int v = 0 ; v < N; v++) { // If applicant u is interested // in job v and v is not visited if (bpGraph[u][v] && !seen[v]) { // Mark v as visited seen[v] = true ; // If job 'v' is not assigned to // an applicant OR previously // assigned applicant for job v (which // is matchR[v]) has an alternate job available. // Since v is marked as visited in the // above line, matchR[v] in the following // recursive call will not get job 'v' again if (matchR[v] < 0 || bpm(bpGraph, matchR[v], seen, matchR)) { matchR[v] = u; return true ; } } } return false ; } // Returns maximum number // of matching from M to N int maxBPM( boolean bpGraph[][]) { // An array to keep track of the // applicants assigned to jobs. // The value of matchR[i] is the // applicant number assigned to job i, // the value -1 indicates nobody is assigned. int matchR[] = new int [N]; // Initially all jobs are available for ( int i = 0 ; i < N; ++i) matchR[i] = - 1 ; // Count of jobs assigned to applicants int result = 0 ; for ( int u = 0 ; u < M; u++) { // Mark all jobs as not seen // for next applicant. boolean seen[] = new boolean [N] ; for ( int i = 0 ; i < N; ++i) seen[i] = false ; // Find if the applicant 'u' can get a job if (bpm(bpGraph, u, seen, matchR)) result++; } return result; } // Driver Code public static void main (String[] args) throws java.lang.Exception { // Let us create a bpGraph shown // in the above example boolean bpGraph[][] = new boolean [][]{ { false , true , true , false , false , false }, { true , false , false , true , false , false }, { false , false , true , false , false , false }, { false , false , true , true , false , false }, { false , false , false , false , false , false }, { false , false , false , false , false , true }}; GFG m = new GFG(); System.out.println( "Maximum number of applicants that can" + " get job is " +m.maxBPM(bpGraph)); } } |
Python3
# Python program to find # maximal Bipartite matching. class GFG: def __init__( self ,graph): # residual graph self .graph = graph self .ppl = len (graph) self .jobs = len (graph[ 0 ]) # A DFS based recursive function # that returns true if a matching # for vertex u is possible def bpm( self , u, matchR, seen): # Try every job one by one for v in range ( self .jobs): # If applicant u is interested # in job v and v is not seen if self .graph[u][v] and seen[v] = = False : # Mark v as visited seen[v] = True '''If job 'v' is not assigned to an applicant OR previously assigned applicant for job v (which is matchR[v]) has an alternate job available. Since v is marked as visited in the above line, matchR[v] in the following recursive call will not get job 'v' again''' if matchR[v] = = - 1 or self .bpm(matchR[v], matchR, seen): matchR[v] = u return True return False # Returns maximum number of matching def maxBPM( self ): '''An array to keep track of the applicants assigned to jobs. The value of matchR[i] is the applicant number assigned to job i, the value -1 indicates nobody is assigned.''' matchR = [ - 1 ] * self .jobs # Count of jobs assigned to applicants result = 0 for i in range ( self .ppl): # Mark all jobs as not seen for next applicant. seen = [ False ] * self .jobs # Find if the applicant 'u' can get a job if self .bpm(i, matchR, seen): result + = 1 return result bpGraph = [[ 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 ]] g = GFG(bpGraph) print ( "Maximum number of applicants that can get job is %d " % g.maxBPM()) # This code is contributed by Neelam Yadav |
C#
// A C# program to find maximal // Bipartite matching. using System; class GFG { // M is number of applicants // and N is number of jobs static int M = 6; static int N = 6; // A DFS based recursive function // that returns true if a matching // for vertex u is possible bool bpm( bool [,]bpGraph, int u, bool []seen, int []matchR) { // Try every job one by one for ( int v = 0; v < N; v++) { // If applicant u is interested // in job v and v is not visited if (bpGraph[u, v] && !seen[v]) { // Mark v as visited seen[v] = true ; // If job 'v' is not assigned to // an applicant OR previously assigned // applicant for job v (which is matchR[v]) // has an alternate job available. // Since v is marked as visited in the above // line, matchR[v] in the following recursive // call will not get job 'v' again if (matchR[v] < 0 || bpm(bpGraph, matchR[v], seen, matchR)) { matchR[v] = u; return true ; } } } return false ; } // Returns maximum number of // matching from M to N int maxBPM( bool [,]bpGraph) { // An array to keep track of the // applicants assigned to jobs. // The value of matchR[i] is the // applicant number assigned to job i, // the value -1 indicates nobody is assigned. int []matchR = new int [N]; // Initially all jobs are available for ( int i = 0; i < N; ++i) matchR[i] = -1; // Count of jobs assigned to applicants int result = 0; for ( int u = 0; u < M; u++) { // Mark all jobs as not // seen for next applicant. bool []seen = new bool [N] ; for ( int i = 0; i < N; ++i) seen[i] = false ; // Find if the applicant // 'u' can get a job if (bpm(bpGraph, u, seen, matchR)) result++; } return result; } // Driver Code public static void Main () { // Let us create a bpGraph shown // in the above example bool [,]bpGraph = new bool [,] {{ false , true , true , false , false , false }, { true , false , false , true , false , false }, { false , false , true , false , false , false }, { false , false , true , true , false , false }, { false , false , false , false , false , false }, { false , false , false , false , false , true }}; GFG m = new GFG(); Console.Write( "Maximum number of applicants that can" + " get job is " +m.maxBPM(bpGraph)); } } //This code is contributed by nitin mittal. |
PHP
<?php // A PHP program to find maximal // Bipartite matching. // M is number of applicants // and N is number of jobs $M = 6; $N = 6; // A DFS based recursive function // that returns true if a matching // for vertex u is possible function bpm( $bpGraph , $u , & $seen , & $matchR ) { global $N ; // Try every job one by one for ( $v = 0; $v < $N ; $v ++) { // If applicant u is interested in // job v and v is not visited if ( $bpGraph [ $u ][ $v ] && ! $seen [ $v ]) { // Mark v as visited $seen [ $v ] = true; // If job 'v' is not assigned to an // applicant OR previously assigned // applicant for job v (which is matchR[v]) // has an alternate job available. // Since v is marked as visited in // the above line, matchR[v] in the following // recursive call will not get job 'v' again if ( $matchR [ $v ] < 0 || bpm( $bpGraph , $matchR [ $v ], $seen , $matchR )) { $matchR [ $v ] = $u ; return true; } } } return false; } // Returns maximum number // of matching from M to N function maxBPM( $bpGraph ) { global $N , $M ; // An array to keep track of the // applicants assigned to jobs. // The value of matchR[i] is the // applicant number assigned to job i, // the value -1 indicates nobody is // assigned. $matchR = array_fill (0, $N , -1); // Initially all jobs are available // Count of jobs assigned to applicants $result = 0; for ( $u = 0; $u < $M ; $u ++) { // Mark all jobs as not seen // for next applicant. $seen = array_fill (0, $N , false); // Find if the applicant 'u' can get a job if (bpm( $bpGraph , $u , $seen , $matchR )) $result ++; } return $result ; } // Driver Code // Let us create a bpGraph // shown in the above example $bpGraph = array ( array (0, 1, 1, 0, 0, 0), array (1, 0, 0, 1, 0, 0), array (0, 0, 1, 0, 0, 0), array (0, 0, 1, 1, 0, 0), array (0, 0, 0, 0, 0, 0), array (0, 0, 0, 0, 0, 1)); echo "Maximum number of applicants that can get job is " .maxBPM( $bpGraph ); // This code is contributed by chadan_jnu ?> |
Javascript
<script> // A JavaScript program to find maximal // Bipartite matching. // M is number of applicants // and N is number of jobs let M = 6; let N = 6; // A DFS based recursive function that // returns true if a matching for // vertex u is possible function bpm(bpGraph, u, seen, matchR) { // Try every job one by one for (let v = 0; v < N; v++) { // If applicant u is interested // in job v and v is not visited if (bpGraph[u][v] && !seen[v]) { // Mark v as visited seen[v] = true ; // If job 'v' is not assigned to // an applicant OR previously // assigned applicant for job v (which // is matchR[v]) has an alternate job available. // Since v is marked as visited in the // above line, matchR[v] in the following // recursive call will not get job 'v' again if (matchR[v] < 0 || bpm(bpGraph, matchR[v], seen, matchR)) { matchR[v] = u; return true ; } } } return false ; } // Returns maximum number // of matching from M to N function maxBPM(bpGraph) { // An array to keep track of the // applicants assigned to jobs. // The value of matchR[i] is the // applicant number assigned to job i, // the value -1 indicates nobody is assigned. let matchR = new Array(N); // Initially all jobs are available for (let i = 0; i < N; ++i) matchR[i] = -1; // Count of jobs assigned to applicants let result = 0; for (let u = 0; u < M; u++) { // Mark all jobs as not seen // for next applicant. let seen = new Array(N); for (let i = 0; i < N; ++i) seen[i] = false ; // Find if the applicant 'u' can get a job if (bpm(bpGraph, u, seen, matchR)) result++; } return result; } // Let us create a bpGraph shown // in the above example let bpGraph = [ [ false , true , true , false , false , false ], [ true , false , false , true , false , false ], [ false , false , true , false , false , false ], [ false , false , true , true , false , false ], [ false , false , false , false , false , false ], [ false , false , false , false , false , true ]]; document.write( "Maximum number of applicants that can" + " get job is " + maxBPM(bpGraph)); </script> |
输出：
Maximum number of applicants that can get job is 5
您可能还希望看到以下内容： Hopcroft–最大匹配|集1的Karp算法（简介） Hopcroft–最大匹配|集2的Karp算法（实现） 参考资料： http://www.cs.cornell.edu/~wdtseng/icpc/notes/graph_part5。pdf http://www.youtube.com/watch?v=NlQqmEXuiC8 http://en.wikipedia.org/wiki/Maximum_matching http://www.stanford.edu/class/cs97si/08-network-flow-problems.pdf http://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/07NetworkFlowII-2×2.pdf http://www.ise.ncsu.edu/fangroup/or766.dir/or766_ch7.pdf 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
