Graph Colouring Problem - Backtracking

We go over the infamous graph colouring problem, and go over the backtracking solution!

[namanjain]

Can't see how the code will backtrack as there is no resetting of color. It seems more of a greedy approach that we always try to color the graph with minimum color possible.

[saifulislamsalim]

I think it would be m^n possible ways to color n nodes with m colors.
(From the video it is in 2:10 to 2:25 )

[dhananjaywithme]

Great video man! the clarity! the explanation! :D

[sairohit]

minor mistakes but you are a life savior man

[ShantanuShinde]

But the algorithm will check all the colors for each vertex even if all nodes are colored. because on returning from last node, the for loop of calling function is still running.

[rahullakhotia]

how can the diagnals be set as 1 of an adjacency matrix ..it is always 0..

[truongvanloc]

In the code, you set x[k] = c;
But I don't see the step of backtracking, I don't see where you reset the color if you want to go back ?

[starkendeavours]

Thanks Sir! Understood the solution in one go.💯

[tirthjayswal]

A really good explanation as well as clean code

[guruprasadc]

Why is this a backtracking problem? We are not making any changes in the previous node's color

[stcenturydigitalje]

In the future you could use 'a', 'b', 'c', 'd' for node names and 'red', 'green', 'blue' for color names so you don't have to use 0, 1, 2, 3 for everything - it would make this video even easier to understand

[DeveshSehdev]

loved the explanation, thnkuuu so much for the video, it was really helpful

[VC-kjyx]

your adjacency matrix is wrong from 0 to 0 there is no edge so it should be 0 not 1 and similarly for 1 to 1 and others

[AABB-fbzy]

very clear. organizing helps a lot.
thanks very much, such big help.

[thedeependpsycho]

awesome dude, really cool explanation and the graphics were also pretty helpful. Thanks !!!

[ceciivanov]

does this solution work for big and more complex graphs lets say for example if we want to color the map of Europe with no more than 4 colors ?
i know that Europe can be colored with 4 colors but does that recursive method would make it possible?

[Nikhil]

thanks for this good video it helped me to understand programming logic more better

[fs]

What if I want to find out all possibilities of coloring ? all valid combinations ?

[debayanmitra]

This is amazing explanation. thanks :)

[ojaspandav]

Would the time complexity of this algorithm be (m*n)^n ? Since the for loop in the isSafe function would run n times in every iteration?