Maximum Bipartite Matching in C++
Introduction:
If there are no two edges that share an endpoint in a bipartite graph, the arrangement of edges is called a matching. A matching with the greatest possible size (number of edges) is referred to as a maximum matching. Whenever an edge is added to a maximum matching, the matching disappears from existence. For each given bipartite graph, there may be more than one maximum matching.
The basic graph theory issue of Maximum Bipartite Matching has a wide range of practical applications. With each edge having a distinct set of vertex positions, the largest set of edges in a bipartite graph must be identified. A graph with the ability to divide its vertices into two distinct sets and where no edge connects vertices in the same set is known as a bipartite graph. The goal of maximal bipartite matching is to locate a matching that covers as many vertices as is allowed.
Bipartite Graph: A bipartite graph is a graph in which the collection of vertices can be split into two disjoint subsets. It is frequently written as U and V, such that every edge in the graph connects a vertex from set U to a vertex in set V. Bipartite graphs are used to simulate a variety of actual events, including marriage, task scheduling, and job allocations.
- Matching: A matching is a group of edges in a graph where no two edges have a common vertex. In the context of a bipartite graph, a matching is an edge set that connects every vertex while providing that no two edges connect the same vertex.
- Maximum bipartite matching: Find the greatest matching within a given bipartite graph to solve the challenge of finding the maximum bipartite matching. This matching should encompass the greatest number of vertices with the requirement that there be no shared vertices between edges.
- Hopcroft Karp Algorithm: The Hopcroft-Karp algorithm is a well-known method for determining the greatest bipartite matching. The most effective way to locate the most matching is by combining alternate pathways and breadth-first search (BFS). The algorithm is implemented in C++ using data structures like queues, queues, and vectors.
The usual process flow for determining the maximum bipartite matching in C++ is as follows:
- Use data structures like matrices or adjacency lists to represent the bipartite graph in your program.
- Begin by initializing an array to keep track of the matching vertices. Beginning with a mismatched set of vertices.
- Use the Hopcroft-Karp algorithm to locate augmenting pathways in a graph. A path that can make the matching size larger by one is known as an augmenting path.
- Up until no other enhancing pathways can be uncovered, repeat the operation.
- The maximum bipartite matching size is represented by the number of matched vertices at the algorithm's conclusion.
Example:
![Maximum Bipartite Matching in C++](https://static.tutorialandexample.com/cpp/maximum-bipartite-matching-in-cpp1.png)
When the maximum match is discovered, we are unable to add another edge. A matching is no longer present if one edge is added to the maximum matched graph. Multiple maximum matching is feasible for a bipartite graph.
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
Example:
Let's take an example to demonstrate the maximum bipartite matching in C++:
#include#define NUM_LEFT_VERTICES 6 #define NUM_RIGHT_VERTICES 6 using namespace std; bool bipartiteGraph[NUM_LEFT_VERTICES][NUM_RIGHT_VERTICES] = { {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 findAugmentingPath(int u, bool visited[], int match[]) { for (int v = 0; v < NUM_RIGHT_VERTICES; v++) { if (bipartiteGraph[u][v] && !visited[v]) { visited[v] = true; if (match[v] < 0 || findAugmentingPath(match[v], visited, match)) { match[v] = u; return true; } } } return false; } int findMaximumMatching() { int match[NUM_RIGHT_VERTICES]; for (int i = 0; i < NUM_RIGHT_VERTICES; i++) match[i] = -1; int matchingCount = 0; for (int u = 0; u < NUM_LEFT_VERTICES; u++) { bool visited[NUM_RIGHT_VERTICES]; for (int i = 0; i < NUM_RIGHT_VERTICES; i++) visited[i] = false; if (findAugmentingPath(u, visited, match)) matchingCount++; } return matchingCount; } int main() { cout << "Maximum matching size: " << findMaximumMatching() << endl; }
Output:
Maximum number of applicants matching for job: 5
Conclusion:
The basic graph theory issue of bipartite matching has a number of real-world applications. We can implement techniques like the Hopcroft-Karp algorithm in C++ to effectively identify the maximum bipartite matching in a bipartite graph. Since no two edges in this matching share a vertex, it indicates a set of edges that join two groups of vertices that are not adjacent to one another. How to handle this issue in C++ is demonstrated by the prior offered code examples. We may address practical issues like employment distribution, marriage assignment, and other optimization tasks by building the bipartite graph, running the matching algorithm, and evaluating the results. Understanding how to construct bipartite matching in C++ can be helpful for resolving a variety of matching and allocation issues because it is a flexible tool in combinatorial optimization.