Using ANSI/ISO C++, Java, or Python write a program that implements a backtracki
ID: 3815509 • Letter: U
Question
Using ANSI/ISO C++, Java, or Python 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
Let us first understand the backtracking algorithm.
Backtracking algorithm tries different solutions until finds a solution that works. The problems which are solved using backtracking can only be solved by trying every possible attempt and each attempt is tried only once.
We have an undirected graph, a number m to find if the graph can be colored with at most m colors such that no two adjacent vertices of the graph are colored with same color. The coloring of a graph means assigning of colors to all vertices.
The C++ program is as follows-
#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;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.