Graph Coloring in Python using Backtracking
Assign colors one by one to different vertices, starting from vertex 0. Before assigning a color, check if the adjacent vertices have the same color or not. If there is any color assignment that does not violate the conditions, mark the color assignment as part of the solution. If no assignment of color is possible then backtrack and return false.
Step-by-step algorithm:
- Create a recursive function that takes the graph, current index, number of vertices, and color array.
- If the current index is equal to the number of vertices. Print the color configuration in the color array.
- Assign a color to a vertex from the range (1 to m).
- For every assigned color, check if the configuration is safe, (i.e. check if the adjacent vertices do not have the same color) and recursively call the function with the next index and number of vertices else return false
- If any recursive function returns true then break the loop and return true
- If no recursive function returns true then return false
Here is the implementation of the above idea:
# Python Program for graph coloring using Backtracking
V = 4
def print_solution(color):
print("Solution Exists: Following are the assigned colors")
print(" ".join(map(str, color)))
def is_safe(v, graph, color, c):
# Check if the color 'c' is safe for the vertex 'v'
for i in range(V):
if graph[v][i] and c == color[i]:
return False
return True
def graph_coloring_util(graph, m, color, v):
# Base case: If all vertices are assigned a color, return true
if v == V:
return True
# Try different colors for the current vertex 'v'
for c in range(1, m + 1):
# Check if assignment of color 'c' to 'v' is fine
if is_safe(v, graph, color, c):
color[v] = c
# Recur to assign colors to the rest of the vertices
if graph_coloring_util(graph, m, color, v + 1):
return True
# If assigning color 'c' doesn't lead to a solution, remove it
color[v] = 0
# If no color can be assigned to this vertex, return false
return False
def graph_coloring(graph, m):
color = [0] * V
# Call graph_coloring_util() for vertex 0
if not graph_coloring_util(graph, m, color, 0):
print("Solution does not exist")
return False
# Print the solution
print_solution(color)
return True
# Driver code
if __name__ == "__main__":
graph = [
[0, 1, 1, 1],
[1, 0, 1, 0],
[1, 1, 0, 1],
[1, 0, 1, 0],
]
m = 3
# Function call
graph_coloring(graph, m)
Output
Solution Exists: Following are the assigned colors 1 2 3 2
Time Complexity: O(mV), where V is the number of vertices and m is the number of available colors.
Auxiliary Space: O(V)
Graph Coloring Algorithm in Python
Given an undirected graph represented by an adjacency matrix. The graph has n nodes, labeled from 1 to n. The task is to assign colors to each node in such a way that no two adjacent nodes have the same color. The challenge is to solve this problem using the minimum number of colors.
Graph Coloring Algorithm in Python