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 in Python using Greedy Algorithm:
The greedy graph coloring algorithm works by assigning colors to vertices one at a time, starting from the first vertex. It checks if any neighboring vertices share the same color before coloring a vertex. If a color can be assigned without clashing with neighbors, it’s considered a valid part of the solution. The algorithm continues until all vertices are colored. If a vertex can’t be validly colored, the algorithm backtracks and concludes that the graph can’t be colored with the available colors.
Step-by-step algorithm:
- Initialize an array
result[]
to store the assigned colors for each vertex. Initially, all vertices are assigned-1
indicating no color. - Initialize an array
available[]
to keep track of available colors for each vertex. - Assign First Color:
- Assign the first color (let’s say
0
) to the first vertex (0
).
- Assign the first color (let’s say
- Coloring Remaining Vertices:
- For each remaining vertex
u
from1
toV-1
:- Mark colors of adjacent vertices of
u
as unavailable in theavailable[]
array. - Find the first available color for
u
that is not used by its adjacent vertices. - Assign the found color to vertex
u
.
- Mark colors of adjacent vertices of
- For each remaining vertex
- Print Result:
- Print the assigned colors for each vertex.
Here is the implementation of the above idea:
# Python Program of graph coloring using greedy algorithm
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[] for _ in range(vertices)]
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
def greedy_coloring(self):
# Initialize all vertices as unassigned
result = [-1] * self.V
# Assign the first color to the first vertex
result[0] = 0
# A temporary array to store the colors of the adjacent vertices
available = [False] * self.V
# Assign colors to remaining V-1 vertices
for u in range(1, self.V):
# Mark colors of adjacent vertices as unavailable
for v in self.graph[u]:
if result[v] != -1:
available[result[v]] = True
# Find the first available color
for color in range(self.V):
if not available[color]:
break
result[u] = color
# Reset the values back to false for the next iteration
for v in self.graph[u]:
if result[v] != -1:
available[result[v]] = False
# Print the result
for u in range(self.V):
print(f"Vertex {u} --> Color {result[u]}")
# Example usage:
if __name__ == "__main__":
# Create a graph with 5 vertices
graph = Graph(5)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 3)
graph.add_edge(3, 4)
print("Coloring of vertices:")
graph.greedy_coloring()
Output
Coloring of vertices: Vertex 0 --> Color 0 Vertex 1 --> Color 1 Vertex 2 --> Color 2 Vertex 3 --> Color 0 Vertex 4 --> Color 1
Time Complexity : O(V * (V + E)), where V is the number of vertices and E is the number of edges.
Auxiliary Space: O(V + E)
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 in Python using Branch & Bound Algorithm:
Graph coloring is a classic problem in computer science and graph theory, aiming to assign colors to vertices of a graph in such a way that no two adjacent vertices share the same color. One approach to solve this problem is the Branch and Bound algorithm. This algorithm systematically explores the search space of possible colorings while efficiently pruning branches of the search tree that are known to lead to suboptimal solutions.
Step-by-step algorithm:
- Initialization:
- Create a graph object with
vertices
number of vertices and an empty adjacency listself.graph
.
- Create a graph object with
- Adding Edges:
- Use
add_edge()
to add edges between vertices.
- Use
- Safety Check:
- Implement
is_safe()
to verify if assigning a color violates constraints.
- Implement
- Graph Coloring Util Function:
- Implement
graph_coloring_util()
to recursively color vertices. - Start at
v = 0
and assign colors. - Return
True
if successful, else backtrack.
- Implement
- Graph Coloring:
- Implement
graph_coloring()
as the main function. - Initialize
color
list. - Call
graph_coloring_util()
to color the graph. - Print colors if successful, else print message.
- Implement
Here is the implementation of the above idea:
# Python program for graph colouring using branch & bound
class Graph:
def __init__(self, vertices):
# Number of vertices
self.V = vertices
# Adjacency list representation of the graph
self.graph = [[] for _ in range(vertices)]
def add_edge(self, u, v):
# Function to add an edge between vertices u and v
self.graph[u].append(v)
# Since the graph is undirected
self.graph[v].append(u)
def is_safe(self, v, c, color):
# Function to check if assigning color c to vertex v is safe
# Iterate through adjacent vertices and check if any has the same color
for i in self.graph[v]:
if color[i] == c:
return False
return True
def graph_coloring_util(self, m, color, v):
# Utility function for graph coloring using backtracking
# m: Number of available colors
# color: List to store colors assigned to vertices
# v: Current vertex
if v == self.V:
# If all vertices are colored, return True (solution exists)
return True
for c in range(1, m + 1):
if self.is_safe(v, c, color):
# If assigning color c to vertex v is safe, assign it
color[v] = c
# Recur for next vertex
if self.graph_coloring_util(m, color, v + 1):
return True
# Backtrack if coloring is not possible
color[v] = 0
def graph_coloring(self, m):
# Main function to perform graph coloring
# m: Number of available colors
color = [0] * self.V # Initialize colors for all vertices to 0
if not self.graph_coloring_util(m, color, 0):
# If solution doesn't exist, print message and return False
print("Solution does not exist")
return False
# Print the colors assigned to each vertex
print("Solution exists. The vertex colors are:")
for c in color:
print(c, end=" ")
# Driver Code
if __name__ == "__main__":
# Create a graph with 5 vertices
graph = Graph(5)
# Add edges between vertices
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 3)
graph.add_edge(3, 4)
# Perform graph coloring with 3 available colors
print("Coloring of vertices:")
graph.graph_coloring(3)
Output
Coloring of vertices: Solution exists. The vertex colors are: 1 2 3 1 2
Time Complexity: O(mV), where V is the number of vertices and m is the number of available colors.
Auxiliary Space: O(V)