Minimum number of colors required to color a graph
Given a graph with N vertices and E edges. The edges are given as U[] and V[] such that for each index i, U[i] is connected to V[i]. The task is to find the minimum number of colors needed to color the given graph.
Examples
Input: N = 5, M = 6, U[] = { 1, 2, 3, 1, 2, 3 }, V[] = { 3, 3, 4, 4, 5, 5 };
Output: 3
Explanation:
For the above graph node 1, 3, and 5 cannot have the same color. Hence the count is 3.
Approach:
We will keep two array count[] and colors[]. The array count[] will store the count of edges for each node and colors[] will store the colors of each node. Initialize count for every vertex to 0 and color for every vertex to 1.
Steps:
- Make a adjacency list for the given set of edges and keep the count of edges for each node
- Iterate over all nodes and insert the node in the queue Q which has no edge.
- While Q is not empty, do the following:
- Pop the element from the queue.
- For all the nodes connected to popped node:
- Decrease the count of current edge for popped node.
- If color of current is less than or equals to color of it’s parent(the node which was popped) then, Update the color of current node = 1 + color of popped node
- If count is zero then insert this node in the queue Q.
- The maximum element in colors[] array will give the minimum number of colors required to color the given graph.
Below is the implementation of the above approach:
C++
// C++ program to find the minimum // number of colors needed to color // the graph #include <bits/stdc++.h> using namespace std; // Function to count the minimum // number of color required void minimumColors( int N, int E, int U[], int V[]) { // Create array of vectors // to make adjacency list vector< int > adj[N]; // Initialise colors array to 1 // and count array to 0 vector< int > count(N, 0); vector< int > colors(N, 1); // Create adjacency list of // a graph for ( int i = 0; i < N; i++) { adj[V[i] - 1].push_back(U[i] - 1); count[U[i] - 1]++; } // Declare queue Q queue< int > Q; // Traverse count[] and insert // in Q if count[i] = 0; for ( int i = 0; i < N; i++) { if (count[i] == 0) { Q.push(i); } } // Traverse queue and update // the count of colors // adjacent node while (!Q.empty()) { int u = Q.front(); Q.pop(); // Traverse node u for ( auto x : adj[u]) { count[x]--; // If count[x] = 0 // insert in Q if (count[x] == 0) { Q.push(x); } // If colors of child // node is less than // parent node, update // the count by 1 if (colors[x] <= colors[u]) { colors[x] = 1 + colors[u]; } } } // Stores the minimumColors // requires to color the graph. int minColor = -1; // Find the maximum of colors[] for ( int i = 0; i < N; i++) { minColor = max(minColor, colors[i]); } // Print the minimum no. of // colors required. cout << minColor << endl; } // Driver function int main() { int N = 5, E = 6; int U[] = { 1, 2, 3, 1, 2, 3 }; int V[] = { 3, 3, 4, 4, 5, 5 }; minimumColors(N, E, U, V); return 0; } |
Java
// Java program to find the minimum // number of colors needed to color // the graph import java.util.*; class GFG { // Function to count the minimum // number of color required static void minimumColors( int N, int E, int U[], int V[]) { // Create array of vectors // to make adjacency list Vector<Integer> []adj = new Vector[N]; // Initialise colors array to 1 // and count array to 0 int []count = new int [N]; int []colors = new int [N]; for ( int i = 0 ; i < N; i++) { adj[i] = new Vector<Integer>(); colors[i] = 1 ; } // Create adjacency list of // a graph for ( int i = 0 ; i < N; i++) { adj[V[i] - 1 ].add(U[i] - 1 ); count[U[i] - 1 ]++; } // Declare queue Q Queue<Integer> Q = new LinkedList<>(); // Traverse count[] and insert // in Q if count[i] = 0; for ( int i = 0 ; i < N; i++) { if (count[i] == 0 ) { Q.add(i); } } // Traverse queue and update // the count of colors // adjacent node while (!Q.isEmpty()) { int u = Q.peek(); Q.remove(); // Traverse node u for ( int x : adj[u]) { count[x]--; // If count[x] = 0 // insert in Q if (count[x] == 0 ) { Q.add(x); } // If colors of child // node is less than // parent node, update // the count by 1 if (colors[x] <= colors[u]) { colors[x] = 1 + colors[u]; } } } // Stores the minimumColors // requires to color the graph. int minColor = - 1 ; // Find the maximum of colors[] for ( int i = 0 ; i < N; i++) { minColor = Math.max(minColor, colors[i]); } // Print the minimum no. of // colors required. System.out.print(minColor + "\n" ); } // Driver function public static void main(String[] args) { int N = 5 , E = 6 ; int U[] = { 1 , 2 , 3 , 1 , 2 , 3 }; int V[] = { 3 , 3 , 4 , 4 , 5 , 5 }; minimumColors(N, E, U, V); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to find the minimum # number of colors needed to color # the graph from collections import deque # Function to count the minimum # number of color required def minimumColors(N, E, U, V): # Create array of vectors # to make adjacency list adj = [[] for i in range (N)] # Initialise colors array to 1 # and count array to 0 count = [ 0 ] * N colors = [ 1 ] * (N) # Create adjacency list of # a graph for i in range (N): adj[V[i] - 1 ].append(U[i] - 1 ) count[U[i] - 1 ] + = 1 # Declare queue Q Q = deque() # Traverse count[] and insert # in Q if count[i] = 0 for i in range (N): if (count[i] = = 0 ): Q.append(i) # Traverse queue and update # the count of colors # adjacent node while len (Q) > 0 : u = Q.popleft() # Traverse node u for x in adj[u]: count[x] - = 1 # If count[x] = 0 # insert in Q if (count[x] = = 0 ): Q.append(x) # If colors of child # node is less than # parent node, update # the count by 1 if (colors[x] < = colors[u]): colors[x] = 1 + colors[u] # Stores the minimumColors # requires to color the graph. minColor = - 1 # Find the maximum of colors[] for i in range (N): minColor = max (minColor, colors[i]) # Print the minimum no. of # colors required. print (minColor) # Driver function N = 5 E = 6 U = [ 1 , 2 , 3 , 1 , 2 , 3 ] V = [ 3 , 3 , 4 , 4 , 5 , 5 ] minimumColors(N, E, U, V) # This code is contributed by mohit kumar 29 |
C#
// C# program to find the minimum // number of colors needed to color // the graph using System; using System.Collections.Generic; class GFG { // Function to count the minimum // number of color required static void minimumColors( int N, int E, int []U, int []V) { // Create array of vectors // to make adjacency list List< int > []adj = new List< int >[N]; // Initialise colors array to 1 // and count array to 0 int []count = new int [N]; int []colors = new int [N]; for ( int i = 0; i < N; i++) { adj[i] = new List< int >(); colors[i] = 1; } // Create adjacency list of // a graph for ( int i = 0; i < N; i++) { adj[V[i] - 1].Add(U[i] - 1); count[U[i] - 1]++; } // Declare queue Q List< int > Q = new List< int >(); // Traverse []count and insert // in Q if count[i] = 0; for ( int i = 0; i < N; i++) { if (count[i] == 0) { Q.Add(i); } } // Traverse queue and update // the count of colors // adjacent node while (Q.Count!=0) { int u = Q[0]; Q.RemoveAt(0); // Traverse node u foreach ( int x in adj[u]) { count[x]--; // If count[x] = 0 // insert in Q if (count[x] == 0) { Q.Add(x); } // If colors of child // node is less than // parent node, update // the count by 1 if (colors[x] <= colors[u]) { colors[x] = 1 + colors[u]; } } } // Stores the minimumColors // requires to color the graph. int minColor = -1; // Find the maximum of colors[] for ( int i = 0; i < N; i++) { minColor = Math.Max(minColor, colors[i]); } // Print the minimum no. of // colors required. Console.Write(minColor + "\n" ); } // Driver function public static void Main(String[] args) { int N = 5, E = 6; int []U = { 1, 2, 3, 1, 2, 3 }; int []V = { 3, 3, 4, 4, 5, 5 }; minimumColors(N, E, U, V); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to find the minimum // number of colors needed to color // the graph // Function to count the minimum // number of color required function minimumColors(N,E,U,V) { // Create array of vectors // to make adjacency list let adj = new Array(N); // Initialise colors array to 1 // and count array to 0 let count = new Array(N); let colors = new Array(N); for (let i = 0; i < N; i++) { adj[i] = []; colors[i] = 1; count[i]=0; } // Create adjacency list of // a graph for (let i = 0; i < N; i++) { adj[V[i] - 1].push(U[i] - 1); count[U[i] - 1]++; } // Declare queue Q let Q = []; // Traverse count[] and insert // in Q if count[i] = 0; for (let i = 0; i < N; i++) { if (count[i] == 0) { Q.push(i); } } // Traverse queue and update // the count of colors // adjacent node while (Q.length!=0) { let u = Q.shift(); // Traverse node u for (let x=0;x<adj[u].length;x++) { count[adj[u][x]]--; // If count[x] = 0 // insert in Q if (count[adj[u][x]] == 0) { Q.push(adj[u][x]); } // If colors of child // node is less than // parent node, update // the count by 1 if (colors[adj[u][x]] <= colors[u]) { colors[adj[u][x]] = 1 + colors[u]; } } } // Stores the minimumColors // requires to color the graph. let minColor = -1; // Find the maximum of colors[] for (let i = 0; i < N; i++) { minColor = Math.max(minColor, colors[i]); } // Print the minimum no. of // colors required. document.write(minColor + "\n" ); } // Driver function let N = 5, E = 6; let U = [ 1, 2, 3, 1, 2, 3 ]; let V = [ 3, 3, 4, 4, 5, 5 ]; minimumColors(N, E, U, V); // This code is contributed by unknown2108 </script> |
3
Time Complexity: O(N+E), where N = number of vertices and E = Number of edges
Contact Us