Graph Colouring Problem
Problem Statement
Given an undirected graph and a number M, determine if the graph can be coloured with at most M colours such that no two adjacent vertices share the same colour. If possible, print one valid colouring.
Example:
- Input:
graph = [[0,1,1,1],[1,0,1,0],[1,1,0,1],[1,0,1,0]],M = 3 - Output:
[1, 2, 3, 2](one valid colouring)
Noob-Friendly Explanation
Imagine you have a map with countries. Two countries that share a border can't have the same colour. You're given a limited number of crayons (M colours). Can you colour the whole map so no neighbouring countries look the same?
Each country is a vertex, each shared border is an edge. You try to assign colours one by one and check if neighbouring countries clash. If they do, you try a different colour. If no colour works, you backtrack.
Approach 1: Brute Force
Intuition
Try every possible combination of colours for all vertices. For each combination, check if it is a valid colouring (no two adjacent vertices share the same colour).
Algorithm
- Generate all M^V possible colour assignments.
- For each assignment, check every edge to see if adjacent vertices share a colour.
- If valid, return the assignment.
public class GraphColouringBrute {
static int V;
static int[][] graph;
public static boolean solve(int[][] g, int m) {
V = g.length;
graph = g;
int[] colours = new int[V];
return tryAll(colours, 0, m);
}
static boolean tryAll(int[] colours, int idx, int m) {
if (idx == V) {
return isValid(colours);
}
for (int c = 1; c <= m; c++) {
colours[idx] = c;
if (tryAll(colours, idx + 1, m)) return true;
}
colours[idx] = 0;
return false;
}
static boolean isValid(int[] colours) {
for (int i = 0; i < V; i++) {
for (int j = i + 1; j < V; j++) {
if (graph[i][j] == 1 && colours[i] == colours[j]) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
int[][] g = {
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 1},
{1, 0, 1, 0}
};
int m = 3;
if (solve(g, m)) {
System.out.println("Colouring is possible with " + m + " colours.");
} else {
System.out.println("Colouring is NOT possible with " + m + " colours.");
}
}
}Complexity Analysis
- Time Complexity: O(M^V) - we try M colours for each of V vertices
- Space Complexity: O(V) - for the colour array and recursion stack
Approach 2: Optimal (Backtracking with Pruning)
Intuition
Instead of generating all combinations and checking at the end, we check at each step whether the current colour assignment is safe. If assigning a colour to a vertex creates a conflict, we skip it immediately (pruning). This avoids exploring many invalid branches.
Algorithm
- Start with vertex 0. Try each colour from 1 to M.
- Before assigning a colour, check if any adjacent vertex already has that colour.
- If safe, assign and move to the next vertex.
- If no colour works for a vertex, backtrack to the previous vertex and try the next colour.
import java.util.*;
public class GraphColouringOptimal {
static int V;
static int[][] graph;
static int[] colour;
public static boolean solve(int[][] g, int m) {
V = g.length;
graph = g;
colour = new int[V];
if (backtrack(0, m)) {
System.out.println("Colours: " + Arrays.toString(colour));
return true;
}
return false;
}
static boolean isSafe(int node, int c) {
for (int i = 0; i < V; i++) {
if (graph[node][i] == 1 && colour[i] == c) {
return false;
}
}
return true;
}
static boolean backtrack(int node, int m) {
if (node == V) return true;
for (int c = 1; c <= m; c++) {
if (isSafe(node, c)) {
colour[node] = c;
if (backtrack(node + 1, m)) return true;
colour[node] = 0;
}
}
return false;
}
public static void main(String[] args) {
int[][] g = {
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 1},
{1, 0, 1, 0}
};
int m = 3;
if (!solve(g, m)) {
System.out.println("No valid colouring exists with " + m + " colours.");
}
}
}Complexity Analysis
- Time Complexity: O(M^V) - worst case still exponential, but pruning makes it much faster in practice
- Space Complexity: O(V) - for the colour array and recursion stack