Graph Coloring Pattern
What is the Graph Coloring Problem?
The Graph Coloring problem asks us to assign colors to each vertex of a graph such that no two adjacent vertices have the same color.
The goal is to use the minimum number of colors possible, but often we're asked if a graph can be colored using at most m colors.
Example:
Can we color a graph with 3 vertices forming a triangle using 2 colors?
Answer: No, we need at least 3 colors.
Backtracking Approach
The Graph Coloring problem can be solved using backtracking:
- Start with the first vertex
- Try assigning each available color to the vertex
- Check if the color assignment is valid (no adjacent vertices have the same color)
- If valid, recursively color the next vertex
- If the recursive call fails, backtrack and try a different color
- If all colors have been tried and none work, backtrack to the previous vertex
Implementation
Here's how we can implement the Graph Coloring solution using backtracking:
Time and Space Complexity
Time Complexity:
O(m^n), where m is the number of colors and n is the number of vertices. In the worst case, we need to try all possible color combinations.
Space Complexity:
O(n) for the colors array and the recursion stack.
Pattern 4: Graph Coloring
Learn how to solve graph coloring problems using backtracking.
The Graph Coloring Problem
The Graph Coloring problem asks us to assign colors to each vertex of a graph such that no two adjacent vertices have the same color.
The goal is to use the minimum number of colors possible, but often we're asked if a graph can be colored using at most m colors.
Example:
Input: A graph with 4 vertices forming a square, m = 2 colors
Output: [1, 2, 1, 2] (vertices 0 and 2 have color 1, vertices 1 and 3 have color 2)
Explanation: Since a square can be colored with 2 colors (alternating colors), this is a valid solution.
Why Backtracking?
The Graph Coloring problem is a perfect candidate for backtracking because:
Constraint Satisfaction
We need to satisfy the constraint that no adjacent vertices have the same color.
Incremental Coloring
We can color the graph one vertex at a time, checking constraints as we go.
Early Pruning
We can quickly identify and abandon invalid colorings without exploring all possibilities.
Decision Problem
We're often asked if a valid coloring exists, which is a classic decision problem.
Backtracking Approach
1Start First Vertex
Begin with the first vertex of the graph.
2Try Colors
Try assigning each available color to the vertex.
3Check Valid
Check if the color assignment is valid (no adjacent vertices have the same color).
4Recurse
If valid, recursively color the next vertex.
5Backtrack
If the recursive call fails, backtrack and try a different color.
6Complete
Continue until all vertices are colored or no valid coloring exists.
Implementation
Here's how we can implement the Graph Coloring solution using backtracking:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051function graphColoring(graph, m) { const n = graph.length; // Number of vertices const colors = Array(n).fill(0); // Color of each vertex (0 means uncolored) // Try to color the graph starting from vertex 0 if (colorGraph(0)) { return colors; } // No valid coloring found return null; function colorGraph(vertex) { // Base case: all vertices are colored if (vertex === n) { return true; } // Try each color for the current vertex for (let color = 1; color <= m; color++) { // Check if it's safe to color the vertex with this color if (isSafe(vertex, color)) { // Assign the color colors[vertex] = color; // Recursively color the rest of the graph if (colorGraph(vertex + 1)) { return true; } // Backtrack: remove the color if it doesn't lead to a solution colors[vertex] = 0; } } // No valid coloring found for this vertex return false; } function isSafe(vertex, color) { // Check if any adjacent vertex has the same color for (let i = 0; i < n; i++) { if (graph[vertex][i] === 1 && colors[i] === color) { return false; } } // The color is safe to use return true; }}Time and Space Complexity
Time Complexity
O(m^n), where m is the number of colors and n is the number of vertices.
In the worst case, we need to try all possible color combinations. For each vertex, we have m color choices, leading to m^n possible colorings in total.
Space Complexity
O(n) for the colors array and the recursion stack.
We need an array of size n to store the color of each vertex, and the recursion stack can go up to depth n in the worst case.