M-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. Return true if possible and print one valid assignment.
Example:
- Input:
V = 4, edges = [(0,1),(1,2),(2,3),(3,0),(0,2)], M = 3 - Output:
true, Colouring:[1, 2, 3, 1]
Noob-Friendly Explanation
Imagine you're colouring a map. Countries that share a border can't have the same colour. You have M crayons. Can you colour every country so that no two neighbouring countries are the same colour?
This is the M-Colouring problem! Each country is a node, each border is an edge. You try assigning colours one by one. If you run into a conflict, you backtrack and try a different colour.
Approach 1: Brute Force (Generate All Assignments)
Intuition
Generate every possible colour assignment for all vertices (M^V possibilities). For each assignment, check if it's valid (no two adjacent vertices share the same colour).
Algorithm
- Generate all possible colour arrays of length V, each value from 1 to M.
- For each assignment, verify no edge has same-coloured endpoints.
- If valid, print it and return true.
public class MColouringBrute {
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 generate(colours, 0, m);
}
static boolean generate(int[] colours, int idx, int m) {
if (idx == V) {
// Validate
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;
}
}
}
printColours(colours);
return true;
}
for (int c = 1; c <= m; c++) {
colours[idx] = c;
if (generate(colours, idx + 1, m)) return true;
}
return false;
}
static void printColours(int[] colours) {
System.out.print("Colours: [");
for (int i = 0; i < colours.length; i++) {
System.out.print(colours[i]);
if (i < colours.length - 1) System.out.print(", ");
}
System.out.println("]");
}
public static void main(String[] args) {
int[][] g = {
{0,1,1,1,0},
{1,0,1,0,0},
{1,1,0,1,0},
{1,0,1,0,0},
{0,0,0,0,0}
};
if (!solve(g, 3)) {
System.out.println("No valid colouring found.");
}
}
}Complexity Analysis
- Time Complexity: O(M^V) - we generate all possible colour assignments
- Space Complexity: O(V) - for the colour array and recursion stack
Approach 2: Optimal (Backtracking)
Intuition
Instead of generating all assignments and validating at the end, validate at each step. Before assigning colour c to vertex v, check if any adjacent vertex already has colour c. If so, skip this colour (prune). This dramatically reduces the search space.
Algorithm
- Process vertices one by one.
- For each vertex, try colours 1 to M.
- Check if the colour is safe (no adjacent vertex has it).
- If safe, assign and move to the next vertex.
- If no colour works, backtrack.
import java.util.*;
public class MColouringOptimal {
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,0},
{1,0,1,0,0},
{1,1,0,1,0},
{1,0,1,0,0},
{0,0,0,0,0}
};
int m = 3;
if (!solve(g, m)) {
System.out.println("No valid colouring with " + m + " colours.");
}
}
}Complexity Analysis
- Time Complexity: O(M^V) - worst case is still exponential, but pruning greatly reduces average time
- Space Complexity: O(V) - for colour array and recursion stack