Using ANSI/ISO C++, Java, Python, or Swift write a program that implements a bac

Question

Using ANSI/ISO C++, Java, Python, or Swift write a program that implements a backtracking algorithm that solves the Hamilton Circuits Problem . Your program should conform to the following specifications.

Give the pre condition 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.

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

Solution:

JAva code:

import java.util.Scanner;

public class mColoringProblem {
final int V = 4;
int color[];

boolean SafeNode(int v, int g[][], int color[],
int c)
{
for (int i = 0; i < V; i++)
if (g[v][i] == 1 && c == color[i])
return false;
return true;
}

boolean colorGraphUtil(int g[][], int m,
int color[], int v)
{
if (v == V)
return true;

for (int c = 1; c <= m; c++)
{
if (SafeNode(v, g, color, c))
{
color[v] = c;
if (colorGraphUtil(g, m,
color, v + 1))
return true;
color[v] = 0;
}
}
return false;
}

boolean colorGraph(int g[][], int m)
{
color = new int[V];
for (int i = 0; i < V; i++)
color[i] = 0;

if (!colorGraphUtil(g, m, color, 0))
{
System.out.println("Solution does not exist");
return false;
}
PrintFinalNodes(color);
return true;
}

void PrintFinalNodes(int color[])
{
System.out.println("Following" +
" are the assigned colors");
for (int i = 0; i < V; i++)
System.out.print(" " + color[i] + " ");
System.out.println();
}

public static void main(String args[])
{
mColoringProblem Coloring = new mColoringProblem();
Scanner sc = new Scanner(System.in);
  
System.out.println("Enter the number of colors to be used ");
int colors = sc.nextInt();
  
System.out.println("Enter the number of vertices of the graph");
int vertices = sc.nextInt();
  
int graph[][] = new int[vertices][vertices];
  
System.out.println("Enter the adjacency matrx");
  
for(int i=0;i<vertices;i++){
   for(int j=0;j<vertices;j++){
       graph[i][j] = sc.nextInt();
   }
}
  
System.out.println("The entered adjacency matrx is ");
  
for(int i=0;i<colors;i++){
   for(int j=0;j<vertices;j++){
       System.out.print(graph[i][j] +" ");
   }
   System.out.println();
}
  
Coloring.colorGraph(graph, colors);
}
}

C code:

#include<stdio.h>

void printSolution(int color[]);

bool isSafe (int v, bool graph[V][V], int color[], int c)

{

    for (int i = 0; i < V; i++)

        if (graph[v][i] && c == color[i])

            return false;

    return true;

}

    if (v == V)

        return true;

for (int c = 1; c <= m; c++)

    {

        if (isSafe(v, graph, color, c))

        {

           color[v] = c;

           if (graphColoringUtil (graph, m, color, v+1) == true)

             return true;

           color[v] = 0;

        }

    }

    return false;

}

//This function solves the m Coloring problem using Backtracking. It mainly uses graphColoringUtil() to solve the problem. It returns false if the m colors cannot be assigned, otherwise return true and prints assignments of colors to all vertices.

bool graphColoring(bool graph[V][V], int m)

{

    int *color = new int[V];

    for (int i = 0; i < V; i++)

       color[i] = 0;

    if (graphColoringUtil(graph, m, color, 0) == false)

    {

      printf("Solution does not exist");

      return false;

    }

    printSolution(color);

    return true;

}

void printSolution(int color[])

{

    printf("Solution Exists:"

            " Following are the assigned colors ");

    for (int i = 0; i < V; i++)

      printf(" %d ", color[i]);

    printf(" ");

}

int main()

{

    bool graph[V][V] = {{0, 1, 1, 1},

        {1, 0, 1, 0},

        {1, 1, 0, 1},

        {1, 0, 1, 0},

    };

    int m = 3; // number of colors

    graphColoring (graph, m);

    return 0;

}

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.