This is a Java Program to Implement Graph Coloring Algorithm. Graph Coloring is a way of coloring the vertices of a undirected graph such that no two adjacent vertices share the same color.
Here is the source code of the Java Program to Implement Graph Coloring Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/** ** Java Program to Implement Graph Coloring Algorithm **/ import java.util.Scanner; /** Class GraphColoring **/ public class GraphColoring { private int V, numOfColors; private int[] color; private int[][] graph; /** Function to assign color **/ public void graphColor(int[][] g, int noc) { V = g.length; numOfColors = noc; color = new int[V]; graph = g; try { solve(0); System.out.println("No solution"); } catch (Exception e) { System.out.println("\nSolution exists "); display(); } } /** function to assign colors recursively **/ public void solve(int v) throws Exception { /** base case - solution found **/ if (v == V) throw new Exception("Solution found"); /** try all colours **/ for (int c = 1; c <= numOfColors; c++) { if (isPossible(v, c)) { /** assign and proceed with next vertex **/ color[v] = c; solve(v + 1); /** wrong assignement **/ color[v] = 0; } } } /** function to check if it is valid to allot that color to vertex **/ public boolean isPossible(int v, int c) { for (int i = 0; i < V; i++) if (graph[v][i] == 1 && c == color[i]) return false; return true; } /** display solution **/ public void display() { System.out.print("\nColors : "); for (int i = 0; i < V; i++) System.out.print(color[i] +" "); System.out.println(); } /** Main function **/ public static void main (String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Graph Coloring Algorithm Test\n"); /** Make an object of GraphColoring class **/ GraphColoring gc = new GraphColoring(); /** Accept number of vertices **/ System.out.println("Enter number of verticesz\n"); int V = scan.nextInt(); /** get graph **/ System.out.println("\nEnter matrix\n"); int[][] graph = new int[V][V]; for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) graph[i][j] = scan.nextInt(); System.out.println("\nEnter number of colors"); int c = scan.nextInt(); gc.graphColor(graph, c); } }
Graph Coloring Algorithm Test Enter number of vertices 10 Enter matrix 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 1 1 0 0 Enter number of colors 3 Solution exists Colors : 1 2 1 2 3 2 1 3 3 2
Related posts:
Java Program to Implement Counting Sort
OAuth2 for a Spring REST API – Handle the Refresh Token in AngularJS
The Order of Tests in JUnit
The Registration API becomes RESTful
Function trong Java 8
A Guide to BitSet in Java
Using a Mutex Object in Java
Hướng dẫn Java Design Pattern – DAO
Phương thức tham chiếu trong Java 8 – Method References
A Quick Guide to Spring MVC Matrix Variables
Iterable to Stream in Java
Java Program to Implement Quick Hull Algorithm to Find Convex Hull
Hướng dẫn sử dụng Java Reflection
Intro to Inversion of Control and Dependency Injection with Spring
Từ khóa this và super trong Java
Stack Memory and Heap Space in Java
REST Web service: HTTP Status Code và xử lý ngoại lệ RESTful web service với Jersey 2.x
Java Program to Find SSSP (Single Source Shortest Path) in DAG (Directed Acyclic Graphs)
An Intro to Spring Cloud Contract
Get the workstation name or IP
Using a Custom Spring MVC’s Handler Interceptor to Manage Sessions
Java Program to Implement RoleList API
JUnit 5 for Kotlin Developers
Check if a String is a Palindrome in Java
Java Program to Implement Caesar Cypher
Reactive Flow with MongoDB, Kotlin, and Spring WebFlux
Spring Cloud – Adding Angular
Disable Spring Data Auto Configuration
Cachable Static Assets with Spring MVC
Java Program to Check whether Graph is a Bipartite using 2 Color Algorithm
Java Program to Find Inverse of a Matrix
Comparing Two HashMaps in Java