# Graph::bipartiteMatching

Function

vector<Edge<T> > bipartiteMatching(vector <T> m, vector<T> m1);
vector<Edge<T> > bipartiteMatching(vector <Vertex<T> > v, vector<Vertex<T> > v1);

Get the edges of the maximum bipartite matching by given the vertices of two independent sets.

## Parameters

m, m1
vector of label of vertices of two independent sets in the bipartite graph.

v, v1
vector of vertices of two independent sets in the bipartite graph.

## Return value

Return vector of edges of the bipartite graph maximum matching.

Example

 ```#include "HKUAL_graph.h" #include #include using namespace std; using namespace HKUAL; int main(){ Graph g; g.addVertex("A"); g.addVertex("B"); g.addVertex("C"); g.addEdge("A", "B"); g.addEdge("A", "C"); vector v1, v2; v1.push_back("A"); v1.push_back("B"); v1.push_back("C"); v2.push_back("D"); v2.push_back("E"); v2.push_back("F"); vector > result; result = g.bipartitemMatching(v1, v2); for (int i = 0; i < result.size(); i++){ cout << result[i].X << ' ' << result[i].Y << endl; } return 0; }```

Output

 2 1

Time Complexity

, for is number of edges and is total number of vertices.

 © The University of Hong Kong Algorithms Library - hkual@cs.hku.hk