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:
Introduction to Spring Data REST
Introduction to Spring Cloud Rest Client with Netflix Ribbon
Java Program to do a Depth First Search/Traversal on a graph non-recursively
Shuffling Collections In Java
Custom JUnit 4 Test Runners
JUnit5 @RunWith
ETL with Spring Cloud Data Flow
Comparing Strings in Java
Spring Boot - Twilio
Java Program to Implement wheel Sieve to Generate Prime Numbers Between Given Range
Introduction to Spring Data JDBC
Java Program to Implement VList
Java Program to Decode a Message Encoded Using Playfair Cipher
Remove HTML tags from a file to extract only the TEXT
Java Program to Implement Stack
Java Program to Generate Random Numbers Using Middle Square Method
An Example of Load Balancing with Zuul and Eureka
Java Program to Implement Johnson’s Algorithm
Guava Collections Cookbook
Java Program to Implement Dijkstra’s Algorithm using Priority Queue
Thực thi nhiều tác vụ cùng lúc như thế nào trong Java?
Spring Boot - Build Systems
Using a Custom Spring MVC’s Handler Interceptor to Manage Sessions
Lập trình hướng đối tượng (OOPs) trong java
A Guide to the Java LinkedList
LinkedList trong java
Spring @RequestMapping New Shortcut Annotations
Java Program to Implement EnumMap API
Java 8 and Infinite Streams
Java Program to Find kth Smallest Element by the Method of Partitioning the Array
Lập trình đa luồng với Callable và Future trong Java
Configure a RestTemplate with RestTemplateBuilder