Graph coloring
Graph coloring is a fundamental problem in graph theory where the goal is to assign colors to the vertices of a graph such that no two adjacent vertices share the same color. This article provides an in-depth explanation of the graph coloring problem and presents a C code implementation of the Backtracking Algorithm to solve it.
Problem Statement
Given an undirected graph, the task is to color its vertices in such a way that no two adjacent vertices have the same color while using the minimum number of colors.
Description with Example
Imagine you have a map of countries with borders representing the edges of a graph. The graph coloring problem can be likened to coloring the map such that no two adjacent countries share the same color, and you want to use the least number of colors possible.
Idea to Solve
The Backtracking Algorithm is a common approach to solving the graph coloring problem. It starts by assigning colors to vertices one by one, backtracking whenever it finds a conflict (two adjacent vertices with the same color), and exploring different color options.
Pseudocode
function graphColor(graph, max_color):
initialize color array with 0
if fillColor(graph, color, max_color, 1, 0):
print "Graph Color"
for each vertex v:
print "Node [v]->color [color[v]]"
else:
print "Given colors [max_color] are not enough"
function fillColor(graph, color, max_color, node_color, node):
if node_color > max_color:
return false
if node == N:
return true
if color[node] == 0:
for each color_option from 1 to max_color:
if isSafe(graph, color, color_option, node):
color[node] = color_option
if fillColor(graph, color, max_color, 1, node + 1):
return true
color[node] = 0
return false
function isSafe(graph, color, node_color, node):
for each adjacent_vertex to node:
if color[adjacent_vertex] == node_color:
return false
return trueAlgorithm Explanation
- Initialize the
colorarray to keep track of colors assigned to vertices. - Call the
fillColorfunction, which iterates through each vertex and tries to assign a color. - Inside the
fillColorfunction: a. If the current node_color exceeds max_color, return false. b. If all vertices are colored, return true. c. If the current vertex has not been colored:- Iterate through color options from 1 to max_color.
- If a color_option is safe for the current vertex (no adjacent vertex has the same color):
- Assign the color_option to the current vertex.
- Recursively call
fillColorfor the next vertex. - If successful, return true. Otherwise, backtrack by resetting color[node]. d. Return false if no color_option is suitable for the current vertex.
Program Solution
// C program
// Graph coloring
#include <stdio.h>
// Define size of adjacency matrix
#define N 6
// Sets the default color of each vertex in graph
void defult_color(int color[N])
{
for (int i = 0; i < N; ++i)
{
color[i] = 0;
}
}
// This function is assigning node color,
// And check adjacent node color are valid or not
int fill_color(int graph[N][N], int color[N], int max_color, int node_color, int node)
{
if (node_color > max_color)
{
return 0;
}
if (node == N)
{
//When color are vaild
return 1;
}
if (color[node] == 0)
{
//When need to set color
int status = 1;
//Check neighbors
for (int i = 0; i < N && status == 1; ++i)
{
if (graph[node][i] == 1 && color[i] == node_color)
{
// When need to change color
if (fill_color(graph, color, max_color, node_color + 1, node))
{
return 1;
}
else
{
status = 0;
}
}
}
if (status == 1)
{
//When color is valid to node
color[node] = node_color;
//Visit to next node
if (fill_color(graph, color, max_color, 1, node + 1))
{
return 1;
}
//reset node color
color[node] = 0;
}
}
return 0;
}
// Handles the request of find given graph node color
void graph_color(int graph[N][N], int max_color)
{
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
int color[N];
defult_color(color);
if (fill_color(graph, color, max_color, 1, 0))
{
//When given color are suitable
printf("\n Graph Color");
for (int i = 0; i < N; ++i)
{
//Display node color
printf("\n Node [%d]->color [%d]", i, color[i]);
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
printf("\n Given colors [%d] are not enough\n", max_color);
}
}
int main()
{
//Define node relation in adjacency matrix
int graph[N][N] = {
{
0 , 1 , 0 , 1 , 0 , 1
} ,
{
1 , 0 , 1 , 0 , 1 , 0
} ,
{
0 , 1 , 0 , 1 , 1 , 1
} ,
{
1 , 0 , 1 , 0 , 1 , 0
} ,
{
0 , 1 , 1 , 1 , 0 , 1
} ,
{
1 , 0 , 1 , 0 , 1 , 0
} , };
//Define number of possible color
int max_color = 3;
graph_color(graph, max_color);
return 0;
}Output
Graph Color
Node [0]->color [1]
Node [1]->color [2]
Node [2]->color [1]
Node [3]->color [2]
Node [4]->color [3]
Node [5]->color [2]/*
Java program
Graph coloring
*/
class MyGraph
{
// Sets the default color of each vertex in graph
public void defult_color(int[] color,int size)
{
for (int i = 0; i < size; ++i)
{
color[i] = 0;
}
}
// This function is assigning node color,
// And check adjacent node color are valid or not
public boolean fill_color(int [][]graph, int[] color, int max_color, int node_color, int node,int size)
{
if (node_color > max_color)
{
return false;
}
if (node == size)
{
//When color are vaild
return true;
}
if (color[node] == 0)
{
//When need to set color
boolean status = true;
//Check neighbors
for (int i = 0; i < size && status == true; ++i)
{
if (graph[node][i] == 1 && color[i] == node_color)
{
// When need to change color
if (fill_color(graph, color, max_color, node_color + 1, node, size))
{
return true;
}
else
{
status = false;
}
}
}
if (status == true)
{
//When color is valid to node
color[node] = node_color;
//Visit to next node
if (fill_color(graph, color, max_color, 1, node + 1,size))
{
return true;
}
//reset node color
color[node] = 0;
}
}
return false;
}
// Handles the request of find given graph node color
public void graph_color(int[][] graph, int max_color,int size)
{
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
int[] color = new int[size];
defult_color(color,size);
if (fill_color(graph, color, max_color, 1, 0,size))
{
//When given color are suitable
System.out.print("\n Graph Color");
for (int i = 0; i < size; ++i)
{
//Display node color
System.out.print("\n Node [" + i + "]->color [" + color[i] + "]");
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
System.out.print("\n Given colors [" + max_color + "] are not enough\n");
}
}
public static void main(String[] args)
{
MyGraph obj = new MyGraph();
//Define node relation in adjacency matrix
int [][] graph =
{
{
0 , 1 , 0 , 1 , 0 , 1
} ,
{
1 , 0 , 1 , 0 , 1 , 0
} ,
{
0 , 1 , 0 , 1 , 1 , 1
} ,
{
1 , 0 , 1 , 0 , 1 , 0
} ,
{
0 , 1 , 1 , 1 , 0 , 1
} ,
{
1 , 0 , 1 , 0 , 1 , 0
} ,
};
// Get size of adjacency matrix
int size = graph.length;
//Define number of possible color
int max_color = 3;
//Test
obj.graph_color(graph, max_color,size);
}
}Output
Graph Color
Node [0]->color [1]
Node [1]->color [2]
Node [2]->color [1]
Node [3]->color [2]
Node [4]->color [3]
Node [5]->color [2]//Include header file
#include <iostream>
#define N 6
using namespace std;
/*
C++ program
Graph coloring
*/
class MyGraph
{
public:
// Sets the default color of each vertex in graph
void defult_color(int color[], int size)
{
for (int i = 0; i < size; ++i)
{
color[i] = 0;
}
}
// This function is assigning node color,
// And check adjacent node color are valid or not
bool fill_color(int graph[N][N], int color[], int max_color, int node_color, int node, int size)
{
if (node_color > max_color)
{
return false;
}
if (node == size)
{
//When color are vaild
return true;
}
if (color[node] == 0)
{
//When need to set color
bool status = true;
//Check neighbors
for (int i = 0; i < size && status == true; ++i)
{
if (graph[node][i] == 1 && color[i] == node_color)
{
// When need to change color
if (this->fill_color(graph, color, max_color, node_color + 1, node, size))
{
return true;
}
else
{
status = false;
}
}
}
if (status == true)
{
//When color is valid to node
color[node] = node_color;
//Visit to next node
if (this->fill_color(graph, color, max_color, 1, node + 1, size))
{
return true;
}
//reset node color
color[node] = 0;
}
}
return false;
}
// Handles the request of find given graph node color
void graph_color(int graph[N][N], int max_color, int size)
{
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
int color[size];
this->defult_color(color, size);
if (this->fill_color(graph, color, max_color, 1, 0, size))
{
//When given color are suitable
cout << "\n Graph Color";
for (int i = 0; i < size; ++i)
{
//Display node color
cout << "\n Node [" << i << "] -> color [" << color[i] << "]";
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
cout << "\n Given colors [" << max_color << "] are not enough\n";
}
}
};
int main()
{
MyGraph obj = MyGraph();
//Define node relation in adjacency matrix
int graph[N][N] = {
{
0 , 1 , 0 , 1 , 0 , 1
} , {
1 , 0 , 1 , 0 , 1 , 0
} , {
0 , 1 , 0 , 1 , 1 , 1
} , {
1 , 0 , 1 , 0 , 1 , 0
} , {
0 , 1 , 1 , 1 , 0 , 1
} , {
1 , 0 , 1 , 0 , 1 , 0
} };
// Get size of adjacency matrix
int size = N;
//Define number of possible color
int max_color = 3;
//Test
obj.graph_color(graph, max_color, size);
return 0;
}Output
Graph Color
Node [0] -> color [1]
Node [1] -> color [2]
Node [2] -> color [1]
Node [3] -> color [2]
Node [4] -> color [3]
Node [5] -> color [2]//Include namespace system
using System;
/*
C# program
Graph coloring
*/
class MyGraph
{
// Sets the default color of each vertex in graph
public void defult_color(int[] color, int size)
{
for (int i = 0; i < size; ++i)
{
color[i] = 0;
}
}
// This function is assigning node color,
// And check adjacent node color are valid or not
public Boolean fill_color(int[,] graph, int[] color, int max_color, int node_color, int node, int size)
{
if (node_color > max_color)
{
return false;
}
if (node == size)
{
//When color are vaild
return true;
}
if (color[node] == 0)
{
//When need to set color
Boolean status = true;
//Check neighbors
for (int i = 0; i < size && status == true; ++i)
{
if (graph[node,i] == 1 && color[i] == node_color)
{
// When need to change color
if (fill_color(graph, color, max_color, node_color + 1, node, size))
{
return true;
}
else
{
status = false;
}
}
}
if (status == true)
{
//When color is valid to node
color[node] = node_color;
//Visit to next node
if (fill_color(graph, color, max_color, 1, node + 1, size))
{
return true;
}
//reset node color
color[node] = 0;
}
}
return false;
}
// Handles the request of find given graph node color
public void graph_color(int[,] graph, int max_color, int size)
{
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
int[] color = new int[size];
defult_color(color, size);
if (fill_color(graph, color, max_color, 1, 0, size))
{
//When given color are suitable
Console.Write("\n Graph Color");
for (int i = 0; i < size; ++i)
{
//Display node color
Console.Write("\n Node [" + i + "] -> color [" + color[i] + "]");
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
Console.Write("\n Given colors [" + max_color + "] are not enough\n");
}
}
public static void Main(String[] args)
{
MyGraph obj = new MyGraph();
//Define node relation in adjacency matrix
int[,] graph = {
{
0 , 1 , 0 , 1 , 0 , 1
} , {
1 , 0 , 1 , 0 , 1 , 0
} , {
0 , 1 , 0 , 1 , 1 , 1
} , {
1 , 0 , 1 , 0 , 1 , 0
} , {
0 , 1 , 1 , 1 , 0 , 1
} , {
1 , 0 , 1 , 0 , 1 , 0
}
};
// Get size of adjacency matrix
int size = graph.GetLength(0);
//Define number of possible color
int max_color = 3;
//Test
obj.graph_color(graph, max_color, size);
}
}Output
Graph Color
Node [0] -> color [1]
Node [1] -> color [2]
Node [2] -> color [1]
Node [3] -> color [2]
Node [4] -> color [3]
Node [5] -> color [2]<?php
/*
Php program
Graph coloring
*/
class MyGraph
{
// This function is assigning node color,
// And check adjacent node color are valid or not
public function fill_color( & $graph, & $color, $max_color, $node_color, $node, $size)
{
if ($node_color > $max_color)
{
return false;
}
if ($node == $size)
{
//When color are vaild
return true;
}
if ($color[$node] == 0)
{
//When need to set color
$status = true;
//Check neighbors
for ($i = 0; $i < $size && $status == true; ++$i)
{
if ($graph[$node][$i] == 1 && $color[$i] == $node_color)
{
// When need to change color
if ($this->fill_color($graph, $color, $max_color, $node_color + 1, $node, $size))
{
return true;
}
else
{
$status = false;
}
}
}
if ($status == true)
{
//When color is valid to node
$color[$node] = $node_color;
//Visit to next node
if ($this->fill_color($graph, $color, $max_color, 1, $node + 1, $size))
{
return true;
}
//reset node color
$color[$node] = 0;
}
}
return false;
}
// Handles the request of find given graph node color
public function graph_color( & $graph, $max_color, $size)
{
if ($max_color <= 0)
{
return;
}
// This are used to store vertex color
$color = array_fill(0, $size, 0);
if ($this->fill_color($graph, $color, $max_color, 1, 0, $size))
{
//When given color are suitable
echo "\n Graph Color";
for ($i = 0; $i < $size; ++$i)
{
//Display node color
echo "\n Node [". $i ."] -> color [". $color[$i] ."]";
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
echo "\n Given colors [". $max_color ."] are not enough\n";
}
}
}
function main()
{
$obj = new MyGraph();
//Define node relation in adjacency matrix
$graph = array(array(0, 1, 0, 1, 0, 1), array(1, 0, 1, 0, 1, 0), array(0, 1, 0, 1, 1, 1), array(1, 0, 1, 0, 1, 0), array(0, 1, 1, 1, 0, 1), array(1, 0, 1, 0, 1, 0));
// Get size of adjacency matrix
$size = count($graph);
//Define number of possible color
$max_color = 3;
//Test
$obj->graph_color($graph, $max_color, $size);
}
main();Output
Graph Color
Node [0] -> color [1]
Node [1] -> color [2]
Node [2] -> color [1]
Node [3] -> color [2]
Node [4] -> color [3]
Node [5] -> color [2]/*
Node Js program
Graph coloring
*/
class MyGraph
{
// This function is assigning node color,
// And check adjacent node color are valid or not
fill_color(graph, color, max_color, node_color, node, size)
{
if (node_color > max_color)
{
return false;
}
if (node == size)
{
//When color are vaild
return true;
}
if (color[node] == 0)
{
//When need to set color
var status = true;
//Check neighbors
for (var i = 0; i < size && status == true; ++i)
{
if (graph[node][i] == 1 && color[i] == node_color)
{
// When need to change color
if (this.fill_color(graph, color, max_color, node_color + 1, node, size))
{
return true;
}
else
{
status = false;
}
}
}
if (status == true)
{
//When color is valid to node
color[node] = node_color;
//Visit to next node
if (this.fill_color(graph, color, max_color, 1, node + 1, size))
{
return true;
}
//reset node color
color[node] = 0;
}
}
return false;
}
// Handles the request of find given graph node color
graph_color(graph, max_color, size)
{
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
var color = Array(size).fill(0);
if (this.fill_color(graph, color, max_color, 1, 0, size))
{
//When given color are suitable
process.stdout.write("\n Graph Color");
for (var i = 0; i < size; ++i)
{
//Display node color
process.stdout.write("\n Node [" + i + "] -> color [" + color[i] + "]");
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
process.stdout.write("\n Given colors [" + max_color + "] are not enough\n");
}
}
}
function main()
{
var obj = new MyGraph();
//Define node relation in adjacency matrix
var graph = [
[0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0]
];
// Get size of adjacency matrix
var size = graph.length;
//Define number of possible color
var max_color = 3;
//Test
obj.graph_color(graph, max_color, size);
}
main();Output
Graph Color
Node [0] -> color [1]
Node [1] -> color [2]
Node [2] -> color [1]
Node [3] -> color [2]
Node [4] -> color [3]
Node [5] -> color [2]# Python 3 program
# Graph coloring
class MyGraph :
# This function is assigning node color,
# And check adjacent node color are valid or not
def fill_color(self, graph, color, max_color, node_color, node, size) :
if (node_color > max_color) :
return False
if (node == size) :
# When color are vaild
return True
if (color[node] == 0) :
# When need to set color
status = True
# Check neighbors
i = 0
while (i < size and status == True) :
if (graph[node][i] == 1 and color[i] == node_color) :
# When need to change color
if (self.fill_color(graph, color, max_color, node_color + 1, node, size)) :
return True
else :
status = False
i += 1
if (status == True) :
# When color is valid to node
color[node] = node_color
# Visit to next node
if (self.fill_color(graph, color, max_color, 1, node + 1, size)) :
return True
# reset node color
color[node] = 0
return False
# Handles the request of find given graph node color
def graph_color(self, graph, max_color, size) :
if (max_color <= 0) :
return
# This are used to store vertex color
color = [0] * (size)
if (self.fill_color(graph, color, max_color, 1, 0, size)) :
# When given color are suitable
print("\n Graph Color", end = "")
i = 0
while (i < size) :
# Display node color
print("\n Node [", i ,"] -> color [", color[i] ,"]", end = "")
i += 1
else :
# In case if, given color are not suitable to fill all adjacent vertices.
# (violation of color) Then
print("\n Given colors [", max_color ,"] are not enough\n", end = "")
def main() :
obj = MyGraph()
# Define node relation in adjacency matrix
graph = [
[0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0]
]
# Get size of adjacency matrix
size = len(graph)
# Define number of possible color
max_color = 3
# Test
obj.graph_color(graph, max_color, size)
if __name__ == "__main__": main()Output
Graph Color
Node [ 0 ] -> color [ 1 ]
Node [ 1 ] -> color [ 2 ]
Node [ 2 ] -> color [ 1 ]
Node [ 3 ] -> color [ 2 ]
Node [ 4 ] -> color [ 3 ]
Node [ 5 ] -> color [ 2 ]# Ruby program
# Graph coloring
class MyGraph
# This function is assigning node color,
# And check adjacent node color are valid or not
def fill_color(graph, color, max_color, node_color, node, size)
if (node_color > max_color)
return false
end
if (node == size)
# When color are vaild
return true
end
if (color[node] == 0)
# When need to set color
status = true
# Check neighbors
i = 0
while (i < size && status == true)
if (graph[node][i] == 1 && color[i] == node_color)
# When need to change color
if (self.fill_color(graph, color, max_color, node_color + 1, node, size))
return true
else
status = false
end
end
i += 1
end
if (status == true)
# When color is valid to node
color[node] = node_color
# Visit to next node
if (self.fill_color(graph, color, max_color, 1, node + 1, size))
return true
end
# reset node color
color[node] = 0
end
end
return false
end
# Handles the request of find given graph node color
def graph_color(graph, max_color, size)
if (max_color <= 0)
return
end
# This are used to store vertex color
color = Array.new(size) {0}
if (self.fill_color(graph, color, max_color, 1, 0, size))
# When given color are suitable
print("\n Graph Color")
i = 0
while (i < size)
# Display node color
print("\n Node [", i ,"] -> color [", color[i] ,"]")
i += 1
end
else
# In case if, given color are not suitable to fill all adjacent vertices.
# (violation of color) Then
print("\n Given colors [", max_color ,"] are not enough\n")
end
end
end
def main()
obj = MyGraph.new()
# Define node relation in adjacency matrix
graph = [
[0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0]
]
# Get size of adjacency matrix
size = graph.length
# Define number of possible color
max_color = 3
# Test
obj.graph_color(graph, max_color, size)
end
main()Output
Graph Color
Node [0] -> color [1]
Node [1] -> color [2]
Node [2] -> color [1]
Node [3] -> color [2]
Node [4] -> color [3]
Node [5] -> color [2]/*
Scala program
Graph coloring
*/
class MyGraph
{
// This function is assigning node color,
// And check adjacent node color are valid or not
def fill_color(graph: Array[Array[Int]], color: Array[Int], max_color: Int, node_color: Int, node: Int, size: Int): Boolean = {
if (node_color > max_color)
{
return false;
}
if (node == size)
{
//When color are vaild
return true;
}
if (color(node) == 0)
{
//When need to set color
var status: Boolean = true;
//Check neighbors
var i: Int = 0;
while (i < size && status == true)
{
if (graph(node)(i) == 1 && color(i) == node_color)
{
// When need to change color
if (fill_color(graph, color, max_color, node_color + 1, node, size))
{
return true;
}
else
{
status = false;
}
}
i += 1;
}
if (status == true)
{
//When color is valid to node
color(node) = node_color;
//Visit to next node
if (fill_color(graph, color, max_color, 1, node + 1, size))
{
return true;
}
//reset node color
color(node) = 0;
}
}
return false;
}
// Handles the request of find given graph node color
def graph_color(graph: Array[Array[Int]], max_color: Int, size: Int): Unit = {
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
var color: Array[Int] = Array.fill[Int](size)(0);
if (fill_color(graph, color, max_color, 1, 0, size))
{
//When given color are suitable
print("\n Graph Color");
var i: Int = 0;
while (i < size)
{
//Display node color
print("\n Node [" + i + "] -> color [" + color(i) + "]");
i += 1;
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
print("\n Given colors [" + max_color + "] are not enough\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyGraph = new MyGraph();
//Define node relation in adjacency matrix
var graph: Array[Array[Int]] = Array(Array(0, 1, 0, 1, 0, 1), Array(1, 0, 1, 0, 1, 0), Array(0, 1, 0, 1, 1, 1), Array(1, 0, 1, 0, 1, 0), Array(0, 1, 1, 1, 0, 1), Array(1, 0, 1, 0, 1, 0));
// Get size of adjacency matrix
var size: Int = graph.length;
//Define number of possible color
var max_color: Int = 3;
//Test
obj.graph_color(graph, max_color, size);
}
}Output
Graph Color
Node [0] -> color [1]
Node [1] -> color [2]
Node [2] -> color [1]
Node [3] -> color [2]
Node [4] -> color [3]
Node [5] -> color [2]/*
Swift 4 program
Graph coloring
*/
class MyGraph
{
// This function is assigning node color,
// And check adjacent node color are valid or not
func fill_color(_ graph: [[Int]],
_ color: inout[Int],
_ max_color: Int,
_ node_color: Int,
_ node: Int,
_ size: Int) -> Bool
{
if (node_color > max_color)
{
return false;
}
if (node == size)
{
//When color are vaild
return true;
}
if (color[node] == 0)
{
//When need to set color
var status: Bool = true;
//Check neighbors
var i: Int = 0;
while (i < size && status == true)
{
if (graph[node][i] == 1 && color[i] == node_color)
{
// When need to change color
if (self.fill_color(graph, &color, max_color, node_color + 1, node, size))
{
return true;
}
else
{
status = false;
}
}
i += 1;
}
if (status == true)
{
//When color is valid to node
color[node] = node_color;
//Visit to next node
if (self.fill_color(graph, &color, max_color, 1, node + 1, size))
{
return true;
}
//reset node color
color[node] = 0;
}
}
return false;
}
// Handles the request of find given graph node color
func graph_color(_ graph: [[Int]], _ max_color: Int, _ size: Int)
{
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
var color: [Int] = Array(repeating: 0, count: size);
if (self.fill_color(graph, &color, max_color, 1, 0, size))
{
//When given color are suitable
print("\n Graph Color", terminator: "");
var i: Int = 0;
while (i < size)
{
//Display node color
print("\n Node [", i ,"] -> color [", color[i],"]", terminator: "");
i += 1;
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
print("\n Given colors [", max_color ,"]are not enough\n", terminator: "");
}
}
}
func main()
{
let obj: MyGraph = MyGraph();
//Define node relation in adjacency matrix
let graph: [[Int]] = [[0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0]];
// Get size of adjacency matrix
let size: Int = graph.count;
//Define number of possible color
let max_color: Int = 3;
//Test
obj.graph_color(graph, max_color, size);
}
main();Output
Graph Color
Node [ 0 ] -> color [ 1 ]
Node [ 1 ] -> color [ 2 ]
Node [ 2 ] -> color [ 1 ]
Node [ 3 ] -> color [ 2 ]
Node [ 4 ] -> color [ 3 ]
Node [ 5 ] -> color [ 2 ]Output Explanation
The output demonstrates the successful coloring of the graph's vertices using the Backtracking Algorithm. Each line indicates the color assigned to a vertex. If the given colors are not sufficient to color the graph without conflicts, a message is printed indicating the insufficiency of colors.
Time Complexity
The time complexity of the Backtracking Algorithm for graph coloring depends on the branching factor (max_color) and the number of vertices (N) in the graph. In the worst case, the algorithm explores all possible color combinations for each vertex, resulting in an exponential time complexity of O(max_color^N).
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment