Understanding Bipartite Graphs and Matching Problems in DSA

What are Bipartite Graphs?

A bipartite graph is a special kind of graph where the set of vertices can be divided into two distinct and independent subsets. In simple terms, no two vertices within the same subset are adjacent.

Visualizing Bipartite Graphs

Imagine a scenario where you have two groups: Group A (representing jobs) and Group B (representing applicants). Each job is connected to the applicants that can take it. This forms a bipartite structure where:

• Group A = Jobs
• Group B = Applicants

Vertices from Group A only connect to vertices in Group B, exemplifying the bipartite property.

      Jobs (Group A)
       A1 ----- A2
        |       |
        |       |
      Applicants (Group B)
       B1      B2

Properties of Bipartite Graphs

1. Graph Coloring: A bipartite graph can be colored using two colors such that no two adjacent vertices share the same color.
2. No Odd Cycles: If a graph contains an odd-length cycle, it's not bipartite.
3. Matching: Finding pairs of vertices where each vertex connects and belongs to different subsets is a key operation.

Matching in Bipartite Graphs

Matching refers to a set of edges that do not share any vertices. Finding a maximum matching (largest matching possible) in a bipartite graph is a common problem. There are several algorithms to achieve this, notably the Hungarian Algorithm and the Hopcroft-Karp Algorithm.

Example Problem: Maximum Matching

Consider the following bipartite graph:

• Group A (Jobs): {J1, J2, J3}
• Group B (Applicants): {A, B, C}

Connections:

• J1 ↔ A
• J1 ↔ B
• J2 ↔ B
• J2 ↔ C
• J3 ↔ C

  J1 -- A
   | \
   |  \
  J2 -- B
   | \  
   |  \
  J3 -- C

Steps to Solve Using the Hopcroft-Karp Algorithm

1. Initialization: Start with an empty matching. For each vertex in Group A, find a match in Group B.
2. BFS for Augmenting Paths: Use Breadth-First Search to find an augmenting path.
3. DFS to Augment: After identifying an augmenting path, use Depth-First Search to update the matching.
4. Repeat: Continue searching for augmenting paths until no further possible matches can be found.

Java Implementation

Here’s a simple sketch in Java demonstrating the DFS and BFS approach to solve a matching problem in a bipartite graph:

import java.util.*;

public class BipartiteMatching {
    static final int MAX = 100;

    static int[][] graph = new int[MAX][MAX];
    static boolean[] visited;
    static int[] matchR;

    // DFS to find an augmenting path
    static boolean bpm(int u) {
        for (int v = 0; v < graph[0].length; v++) {
            if (graph[u][v] == 1 && !visited[v]) {
                visited[v] = true;
                if (matchR[v] == -1 || bpm(matchR[v])) {
                    matchR[v] = u;
                    return true;
                }
            }
        }
        return false;
    }

    public static int maxBPM() {
        matchR = new int[graph[0].length];
        Arrays.fill(matchR, -1);
        int result = 0;
        for (int u = 0; u < graph.length; u++) {
            visited = new boolean[graph[0].length];
            if (bpm(u)) {
                result++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        // Example graph initialization
        graph[0][0] = 1; graph[0][1] = 1; // J1 with A, B
        graph[1][1] = 1; graph[1][2] = 1; // J2 with B, C
        graph[2][2] = 1; // J3 with C
        
        System.out.println("Maximum number of applicants that can get jobs: " + maxBPM());
    }
}

Explanation of the Code

• Data Structure: The adjacency matrix represents the bipartite graph where graph[u][v] = 1 indicates a connection.
• BPM Function: This function uses a recursive DFS approach to find an augmenting path.
• MaxBPM Function: Initiates the matching process and counts the maximum matched pairs.

Complexity Analysis

The Hopcroft-Karp algorithm runs in O(E√V) time, making it efficient for large bipartite graphs. With E being the number of edges and V the number of vertices, this method remains practical for competitive programming and technical interviews.

By understanding the core principles of bipartite graphs and matching problems, you can better prepare yourself for advanced graph-related interview questions in Java.