This is a Java Program to Implement Hopcroft Karp Algorithm. The Hopcroft–Karp algorithm is an algorithm that takes as input a bipartite graph and produces as output a maximum cardinality matching – a set of as many edges as possible with the property that no two edges share an endpoint.
Here is the source code of the Java Program to Implement Hopcroft Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/** ** Java Program to Implement Hopcroft Algorithm **/ import java.util.*; /** Class Hopcroft **/ public class Hopcroft { private final int NIL = 0; private final int INF = Integer.MAX_VALUE; private ArrayList<Integer>[] Adj; private int[] Pair; private int[] Dist; private int cx, cy; /** Function BFS **/ public boolean BFS() { Queue<Integer> queue = new LinkedList<Integer>(); for (int v = 1; v <= cx; ++v) if (Pair[v] == NIL) { Dist[v] = 0; queue.add(v); } else Dist[v] = INF; Dist[NIL] = INF; while (!queue.isEmpty()) { int v = queue.poll(); if (Dist[v] < Dist[NIL]) for (int u : Adj[v]) if (Dist[Pair[u]] == INF) { Dist[Pair[u]] = Dist[v] + 1; queue.add(Pair[u]); } } return Dist[NIL] != INF; } /** Function DFS **/ public boolean DFS(int v) { if (v != NIL) { for (int u : Adj[v]) if (Dist[Pair[u]] == Dist[v] + 1) if (DFS(Pair[u])) { Pair[u] = v; Pair[v] = u; return true; } Dist[v] = INF; return false; } return true; } /** Function to get maximum matching **/ public int HopcroftKarp() { Pair = new int[cx + cy + 1]; Dist = new int[cx + cy + 1]; int matching = 0; while (BFS()) for (int v = 1; v <= cx; ++v) if (Pair[v] == NIL) if (DFS(v)) matching = matching + 1; return matching; } /** Function to make graph with vertices x , y **/ public void makeGraph(int[] x, int[] y, int E) { Adj = new ArrayList[cx + cy + 1]; for (int i = 0; i < Adj.length; ++i) Adj[i] = new ArrayList<Integer>(); /** adding edges **/ for (int i = 0; i < E; ++i) addEdge(x[i] + 1, y[i] + 1); } /** Function to add a edge **/ public void addEdge(int u, int v) { Adj[u].add(cx + v); Adj[cx + v].add(u); } /** Main Method **/ public static void main (String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Hopcroft Algorithm Test\n"); /** Make an object of Hopcroft class **/ Hopcroft hc = new Hopcroft(); /** Accept number of edges **/ System.out.println("Enter number of edges\n"); int E = scan.nextInt(); int[] x = new int[E]; int[] y = new int[E]; hc.cx = 0; hc.cy = 0; System.out.println("Enter "+ E +" x, y coordinates "); for (int i = 0; i < E; i++) { x[i] = scan.nextInt(); y[i] = scan.nextInt(); hc.cx = Math.max(hc.cx, x[i]); hc.cy = Math.max(hc.cy, y[i]); } hc.cx += 1; hc.cy += 1; /** make graph with vertices **/ hc.makeGraph(x, y, E); System.out.println("\nMatches : "+ hc.HopcroftKarp()); } }
Hopcroft Algorithm Test Enter number of edges 11 Enter 11 x, y coordinates 0 0 0 3 1 0 1 2 1 4 2 1 3 0 3 2 3 3 3 4 4 2 Matches : 5
Related posts:
Comparing Strings in Java
Transaction Propagation and Isolation in Spring @Transactional
Guide to Mustache with Spring Boot
Java Program to Implement Min Heap
Guide to Selenium with JUnit / TestNG
Java Program to Implement Queue using Linked List
Java Program to Use Boruvka’s Algorithm to Find the Minimum Spanning Tree
The Registration Process With Spring Security
Spring Data Java 8 Support
Adding a Newline Character to a String in Java
Java Program to Implement Hash Tables Chaining with Doubly Linked Lists
Spring MVC Setup with Kotlin
Dockerizing a Spring Boot Application
Call Methods at Runtime Using Java Reflection
Summing Numbers with Java Streams
Rest Web service: Filter và Interceptor với Jersey 2.x (P2)
Java Program to Search for an Element in a Binary Search Tree
Guide to java.util.Formatter
Java Switch Statement
Redirect to Different Pages after Login with Spring Security
Mệnh đề Switch-case trong java
Java Program to Check Whether a Weak Link i.e. Articulation Vertex Exists in a Graph
Hướng dẫn Java Design Pattern – Strategy
Bootstrap a Web Application with Spring 5
Creating a Web Application with Spring 5
Java Program to Implement Find all Cross Edges in a Graph
Java Program to Solve any Linear Equation in One Variable
Introduction to Spring Data JDBC
Anonymous Classes in Java
Giới thiệu HATEOAS
Count Occurrences of a Char in a String
Java Program to Encode a Message Using Playfair Cipher