- DAA - Discussion
- DAA - Useful Resources
- DAA - Quick Guide
- DAA - Hill Climbing Algorithm
- NP Hard & NP-Complete Classes
- DAA - Cook’s Theorem
- DAA - P and NP Class
- DAA - Vertex Cover
- DAA - Max Cliques
- Deterministic vs. Nondeterministic Computations
- DAA - Sublist Search
- DAA - Fibonacci Search
- DAA - Exponential Search
- DAA - Jump Search
- DAA - Interpolation Search
- DAA - Binary Search
- DAA - Linear Search
- Searching Techniques Introduction
- DAA - Radix Sort
- DAA - Counting Sort
- DAA - Bucket Sort
- DAA - Heap Sort
- DAA - Shell Sort
- DAA - Selection Sort
- DAA - Insertion Sort
- DAA - Bubble Sort
- DAA - Extract Method
- DAA - Heapify Method
- DAA - Insert Method
- DAA - Binary Heap
- Optimal Cost Binary Search Trees
- DAA - Multistage Graph
- DAA - Shortest Paths
- DAA - Spanning Tree
- Travelling Salesperson Approximation Algorithm
- Set Cover Problem
- Vertex Cover Problem
- Approximation Algorithms
- Fisher-Yates Shuffle
- Karger’s Minimum Cut
- Randomized Quick Sort
- Randomized Algorithms
- Travelling Salesman Problem | Dynamic Programming
- Longest Common Subsequence
- DAA - 0-1 Knapsack
- Floyd Warshall Algorithm
- Matrix Chain Multiplication
- DAA - Dynamic Programming
- DAA - Optimal Merge Pattern
- DAA - Job Sequencing with Deadline
- DAA - Fractional Knapsack
- Map Colouring Algorithm
- Dijkstra’s Shortest Path Algorithm
- Kruskal’s Minimal Spanning Tree
- Travelling Salesman Problem
- DAA - Greedy Method
- Towers of Hanoi
- Karatsuba Algorithm
- Strassen’s Matrix Multiplication
- DAA - Binary Search
- DAA - Merge Sort
- DAA - Max-Min Problem
- DAA - Divide & Conquer
- DAA - Space Complexities
- Master’s Theorem
- Time Complexity
- Asymptotic Notations & Apriori Analysis
- DAA - Methodology of Analysis
- DAA - Analysis of Algorithms
- DAA - Introduction
- Home
Selected Reading
- Who is Who
- Computer Glossary
- HR Interview Questions
- Effective Resume Writing
- Questions and Answers
- UPSC IAS Exams Notes
Map Colouring Algorithm
Map colouring problem states that given a graph G {V, E} where V and E are the set of vertices and edges of the graph, all vertices in in V need to be coloured in such a way that no two adjacent vertices must have the same colour.
The real-world apppcations of this algorithm are – assigning mobile radio frequencies, making schedules, designing Sudoku, allocating registers etc.
Map Colouring Algorithm
With the map colouring algorithm, a graph G and the colours to be added to the graph are taken as an input and a coloured graph with no two adjacent vertices having the same colour is achieved.
Algorithm
Initiate all the vertices in the graph.
Select the node with the highest degree to colour it with any colour.
Choose the colour to be used on the graph with the help of the selection colour function so that no adjacent vertex is having the same colour.
Check if the colour can be added and if it does, add it to the solution set.
Repeat the process from step 2 until the output set is ready.
Examples
Step 1
Find degrees of all the vertices −
A – 4 B – 2 C – 2 D – 3 E – 3
Step 2
Choose the vertex with the highest degree to colour first, i.e., A and choose a colour using selection colour function. Check if the colour can be added to the vertex and if yes, add it to the solution set.
Step 3
Select any vertex with the next highest degree from the remaining vertices and colour it using selection colour function.
D and E both have the next highest degree 3, so choose any one between them, say D.
D is adjacent to A, therefore it cannot be coloured in the same colour as A. Hence, choose a different colour using selection colour function.
Step 4
The next highest degree vertex is E, hence choose E.
E is adjacent to both A and D, therefore it cannot be coloured in the same colours as A and D. Choose a different colour using selection colour function.
Step 5
The next highest degree vertices are B and C. Thus, choose any one randomly.
B is adjacent to both A and E, thus not allowing to be coloured in the colours of A and E but it is not adjacent to D, so it can be coloured with D’s colour.
Step 6
The next and the last vertex remaining is C, which is adjacent to both A and D, not allowing it to be coloured using the colours of A and D. But it is not adjacent to E, so it can be coloured in E’s colour.
Example
Following is the complete implementation of Map Colouring Algorithm in various programming languages where a graph is coloured in such a way that no two adjacent vertices have same colour.
#include<stdio.h> #include<stdbool.h> #define V 4 bool graph[V][V] = { {0, 1, 1, 0}, {1, 0, 1, 1}, {1, 1, 0, 1}, {0, 1, 1, 0}, }; bool isVapd(int v,int color[], int c){ //check whether putting a color vapd for v for (int i = 0; i < V; i++) if (graph[v][i] && c == color[i]) return false; return true; } bool mColoring(int colors, int color[], int vertex){ if (vertex == V) //when all vertices are considered return true; for (int col = 1; col <= colors; col++) { if (isVapd(vertex,color, col)) { //check whether color col is vapd or not color[vertex] = col; if (mColoring (colors, color, vertex+1) == true) //go for additional vertices return true; color[vertex] = 0; } } return false; //when no colors can be assigned } int main(){ int colors = 3; // Number of colors int color[V]; //make color matrix for each vertex for (int i = 0; i < V; i++) color[i] = 0; //initially set to 0 if (mColoring(colors, color, 0) == false) { //for vertex 0 check graph coloring printf("Solution does not exist."); } printf("Assigned Colors are: "); for (int i = 0; i < V; i++) printf("%d ", color[i]); return 0; }
Output
Assigned Colors are: 1 2 3 1
#include<iostream> using namespace std; #define V 4 bool graph[V][V] = { {0, 1, 1, 0}, {1, 0, 1, 1}, {1, 1, 0, 1}, {0, 1, 1, 0}, }; bool isVapd(int v,int color[], int c){ //check whether putting a color vapd for v for (int i = 0; i < V; i++) if (graph[v][i] && c == color[i]) return false; return true; } bool mColoring(int colors, int color[], int vertex){ if (vertex == V) //when all vertices are considered return true; for (int col = 1; col <= colors; col++) { if (isVapd(vertex,color, col)) { //check whether color col is vapd or not color[vertex] = col; if (mColoring (colors, color, vertex+1) == true) //go for additional vertices return true; color[vertex] = 0; } } return false; //when no colors can be assigned } int main(){ int colors = 3; // Number of colors int color[V]; //make color matrix for each vertex for (int i = 0; i < V; i++) color[i] = 0; //initially set to 0 if (mColoring(colors, color, 0) == false) { //for vertex 0 check graph coloring cout << "Solution does not exist."; } cout << "Assigned Colors are: "; for (int i = 0; i < V; i++) cout << color[i] << " "; return 0; }
Output
Assigned Colors are: 1 2 3 1
pubpc class mcolouring { static int V = 4; static int graph[][] = { {0, 1, 1, 0}, {1, 0, 1, 1}, {1, 1, 0, 1}, {0, 1, 1, 0}, }; static boolean isVapd(int v,int color[], int c) { //check whether putting a color vapd for v for (int i = 0; i < V; i++) if (graph[v][i] != 0 && c == color[i]) return false; return true; } static boolean mColoring(int colors, int color[], int vertex) { if (vertex == V) //when all vertices are considered return true; for (int col = 1; col <= colors; col++) { if (isVapd(vertex,color, col)) { //check whether color col is vapd or not color[vertex] = col; if (mColoring (colors, color, vertex+1) == true) //go for additional vertices return true; color[vertex] = 0; } } return false; //when no colors can be assigned } pubpc static void main(String args[]) { int colors = 3; // Number of colors int color[] = new int[V]; //make color matrix for each vertex for (int i = 0; i < V; i++) color[i] = 0; //initially set to 0 if (mColoring(colors, color, 0) == false) { //for vertex 0 check graph coloring System.out.println("Solution does not exist."); } System.out.println("Assigned Colors are: "); for (int i = 0; i < V; i++) System.out.print(color[i] + " "); } }
Output
Assigned Colors are: 1 2 3 1Advertisements