Using ANSI/ISO C++, Java write a program that implements a backtracking algorith
ID: 3820300 • Letter: U
Question
Using ANSI/ISO C++, Java write a program that implements a backtracking algorithm that solves the m-Coloring Problem as presented in class and given in your text. Your program should conform to the following specifications.
Write the pre and post condition.
Prompt the user for the number of vertices in the graph.
Prompt the user to enter the adjacency matrix of the graph one row at a time.
Print the adjacency matrix of the graph.
Prompt the user for the maximum number of colors to be used.
Print the first solution and ask the user if they want the rest of the solutions.
If the user indicates they want the rest of the solutions, print them without any additional prompts.
Explanation / Answer
Java Program to Implement Graph Coloring Algorithm
import java.util.Scanner; // declare the header files
public class MWayGrColor //declare a class for m way graph coloring
{
/*G is graph's adjacency matrix and x is solution vector */
private int G[][],x[],n,m,soln;
public void mColoring(int k) //backtracking function
{
for(int i=1;i<=n;i++)
{
next_color(k); //coloring kth vertex
if(x[k]==0)
return; //if unsuccessful then backtrack
if(k==n) //if all colored then show
write();
else
mColoring(k+1); /* successful but still left to color */
}
}
private void next_color(int k)
{
do
{
int i=1;
x[k]=(x[k]+1)%(m+1);
if(x[k]==0)
return;
for(i=1;i<=n;i++)
if(G[i][k]!=0 && x[k]==x[i]) // checking adjacency and not same color
break;
if(i==n+1) return; //new color found
}while(true);
}
private void write() //method write() displays solution
{
System.out.print(" Coloring(V C) # "+(++soln)+"-->");
for(int i=1;i<=n;i++)
System.out.print(" ("+i+" "+x[i]+")"); //solution vector
}
public void input()
{
java.util.Scanner sc=new java.util.Scanner(System.in);
System.out.println("Graph Coloring Algorithm Test ");
// Input the number of vertices
System.out.print("Enter no. of vertices : ");
n=sc.nextInt();
G=new int[n+1][n+1];
x=new int[n+1];
// Input the number of colors
System.out.print("Enter no. of colors : ");
m=sc.nextInt();
// get graph
System.out.println("Enter adjacency matrix-->");
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
G[i][j]=sc.nextInt();
}
/** Main function **/
public static void main (String[] args)
{
MWayGrColor obj=new MWayGrColor(); / /Make an object of MWayGrColor class
obj.input(); //invoking the method input() as object
obj.mColoring(1); //invoking the method mcolouring as object
if(obj.soln==0)
System.out.println(" No Solution.Need more than "+obj.m+" colors");
else
System.out.print(" TOTAL SOLN : "+obj.soln); // Displays the solution
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.