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:
ExecutorService – Waiting for Threads to Finish
Spring Boot - Rest Controller Unit Test
Java Program to Implement Borwein Algorithm
Java Program to Implement Hash Tree
Hướng dẫn sử dụng lớp Console trong java
Spring Boot With H2 Database
Sử dụng CountDownLatch trong Java
Java Program to Find Strongly Connected Components in Graphs
Bootstrap a Web Application with Spring 5
Hướng dẫn Java Design Pattern – Strategy
Một số tính năng mới về xử lý ngoại lệ trong Java 7
Java Program to Implement vector
Java Program to Implement Min Heap
Immutable ArrayList in Java
Java Program to Implement PrinterStateReasons API
Java Program to Implement Ternary Search Tree
Các kiểu dữ liệu trong java
StringBuilder vs StringBuffer in Java
Loại bỏ các phần tử trùng trong một ArrayList như thế nào trong Java 8?
Java Program to Implement Stack using Two Queues
Custom HTTP Header with the HttpClient
Converting Between Byte Arrays and Hexadecimal Strings in Java
Java Program to Implement ConcurrentSkipListMap API
Java Program to Perform the Shaker Sort
Converting between an Array and a List in Java
Java Program to Find kth Largest Element in a Sequence
A Guide To UDP In Java
Reactive Flow with MongoDB, Kotlin, and Spring WebFlux
Case-Insensitive String Matching in Java
Java Perform to a 2D FFT Inplace Given a Complex 2D Array
LinkedList trong java
SOAP Web service: Authentication trong JAX-WS