M-Coloring Problem

preview_player
Показать описание
** Approach **
* Create an array of N sizes to keep track of the vertex color
* call function with the initial node as 0
* The base condition will check if we are at of bounds node or not, if yes that means we are able to color all the nodes,
thus return true
* now we will try all the colors till color_limit & check if there is an adjacent vertex that has the same color or not
* if not, then place that color in node_color & call the recursive function with the next node
* now if you are not able to place any color then return false, which means we can't place any color
* Time Complexity:- M^N(because we have M choices, for N vertex)* N (for checking the color for each vertex)
* Space Complexity:- N + N , for recursion & for storing the vertex color array
Рекомендации по теме
Комментарии
Автор

TIme Complexity is M^N, not N^M in the video, why? Read the Description.

showmeyourcode