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:
Easy Ways to Write a Java InputStream to an OutputStream
Java Program to Sort an Array of 10 Elements Using Heap Sort Algorithm
Rest Web service: Filter và Interceptor với Jersey 2.x (P1)
Giới thiệu Swagger – Công cụ document cho RESTfull APIs
Lập trình đa luồng với CompletableFuture trong Java 8
Split a String in Java
Java Program to Remove the Edges in a Given Cyclic Graph such that its Linear Extension can be Found
Bootstrapping Hibernate 5 with Spring
Creating a Web Application with Spring 5
Java Program to Implement Min Heap
Introduction to Spring Boot CLI
Exploring the Spring Boot TestRestTemplate
Java Program to Implement Strassen Algorithm
Life Cycle of a Thread in Java
Java Program to Implement Warshall Algorithm
Java Program to Implement Levenshtein Distance Computing Algorithm
Phân biệt JVM, JRE, JDK
Spring Boot - File Handling
Java Program to Delete a Particular Node in a Tree Without Using Recursion
Tips for dealing with HTTP-related problems
Quick Guide to Spring Controllers
Primitive Type Streams in Java 8
Giới thiệu SOAP UI và thực hiện test Web Service
Introduction to Netflix Archaius with Spring Cloud
Using a Spring Cloud App Starter
Optional trong Java 8
A Guide to BitSet in Java
Jackson JSON Views
Java Program to Implement Max-Flow Min-Cut Theorem
String Joiner trong Java 8
Java Program to Implement Segment Tree
Java Program to Generate Random Numbers Using Probability Distribution Function