Graph Colouring Problem - Backtracking

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

[@dhananjaywithme]

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

[@pdzbw]

such detail, much appreciation~

[@starkendeavours7072]

Thanks Sir! Understood the solution in one go.💯

[@thedeependpsycho]

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

[@tirthjayswal9895]

A really good explanation as well as clean code

[@sairohit8201]

minor mistakes but you are a life savior man

[@AABB-fb4zy]

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

[@rajdesai2989]

Superb explanation.!

[@AkshathGrover]

beautifully explained :) tysm!

[@Nikhil7857]

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

[@debayanmitra3729]

This is amazing explanation. thanks :)

[@bakrgroningen]

Terrific explanation

[@DeveshSehdev]

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

[@prateekkej2506]

Awesome Explanation. Saved me (Y)

[@AnkitChoudhary-vh6gj]

Great explanation... understood it in one go...keep up the good work!!

[@CSBSIRIKIVENKATASIVASURYASAI]

you nailed it man!!!

[@saifulislamsalim9241]

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 )

[@ojaspandav258]

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?

[@YayaB]

great video thnks

[@aavashkuikel1341]

Thanks a lot

[@namanjain1474]

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.

[@ceciivanov6152]

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?

[@fs9050]

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

[@ShantanuShinde1]

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.

[@anweshkrishnanayak2561]

Will the algorithm work for directed graphs as well ?

[@joelnadar3194]

It R was Really very Useful

[@ivandrofly]

Thanks

[@giovanni.n]

any videos on forward checking ?

[@rahullakhotia402]

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

[@truongvanloc8275]

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 ?

[@jinxblaze]

when u backtrack at k'th node, k-1'th level will have x[k] = c but at k-1 we are limiting ourselves to only k-1 nodes so it doesnt matter what x[k] is coz we will replace it with another color later

[@prateekkej2506]

yup. The magic happens at graphColor(k+1). if it returns to parent function, the parent function will try another color.

[@mayankgupta2543]

@@prateekkej2506 i think that return statement at last wont allow backtracking/looping for another color. If the return statement is written outside of the safecheck, then only it will backtrack and try for another color

[@mingzhouyang7925]

@@jinxblaze but in isSafe they check all the nodes from 0 to n.

[@soothingexperience7611]

awesome

[@yamini9612]

Sir,, can this program work on scilab software??

[@guruprasadc5257]

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

[@joseph_hieunguyen]

how do we know m if they dont let you know

[@manishmaithani398]

Nice explanation. But I think in graph coloring problem, we do not have the value 'm' from start. Our algorithm should compute the value of m and as well as x[] (that ur algorithm is computing).

[@user-bb9lx9gu7c]

This one uses m. If it fails, you can try m+1

[@aaratimounika6834]

Nice..

[@datawarehouse5961]

Best graph colouring video on youtube !

[@AdityaPratapsingh9125]

wouldn't it be m^n possible ways(since for each vertex we have m choices)?...correct me if I'm wrong.

[@constructor365]

You're right. And m^n is what is shown in the video. Look again

[@harshilsaini3081]

why 0,0 adjancy matrix 1

[@duydangdroid]

link to the code?

[@rameshpal8762]

Helps in today's exam

[@VC-kj9yx]

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

[@brianpeterson5529]

right, or add an AND i != k to that if statement bool condition in isSafe()

[@mohamedberrimi4850]

the node is adjacent to it self , you should consider that .

[@21stcenturydigitalje]

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

[@sudeshnaC]

Which part of the code shows the backtracking?

[@prateekkej2506]

when we call graphColor(k+1) if it fails then it will return to the next iteration in its parent graphColor()'s for loop where it will continue to try other colors and if its does not returns that means its color was right from the first call.

[@farahuzma3920]

(0,0) of adjacency matrix shud be 1.. similarle for 1,1 2,2 n 3,3

[@anubhavgupta2831]

best graph coloring video :D

[@milenamacedo2066]

doesn't work for larger graphs

[@ilmeroliveira238]

But if I dont have the "m" before coloring the graph?

[@CSBreakdown]

+Ilmer Oliveira Good question. It becomes a much more computationally challenging problem this way, and you have to try the problem with m = 1, m = 2, m = 3... until you find the min value for m where all of the nodes can take colour.

[@CSBreakdown]

To add, this is a known NP-Complete problem meaning there does not exist a solution that is polynomial time for large enough n.

[@ilmeroliveira238]

+CSBreakdown If I make a function that travels the entire array seeking for blank nodes and make my looop runs until it's false(therefore all the nodes are colored)... Might work?

[@CSBreakdown]

+Ilmer Oliveira With the backtracking algorithm, isSafe will return false if there aren't enough m (colours) to satisfy. The algorithm will reach the very end without colouring all of the nodes. In the 'if' statement for isSafe on the left block of code, add an else block and check to see if c = m. So if 'isSafe' = false, and c = m, you know that you don't have enough colours for m. Run the algorithm again, but this time make m 1 bigger.

[@ilmeroliveira238]

+CSBreakdown Can you say if I understood the idea? pastebin.com/7KbaYKGF

[@TusharYadav-es1bq]

shouldnt it be m^n ways ?

[@majedulislam187]

very nice !!!!!!!!!

[@shobhitaagarwal8242]

There is no backtracking step in the graphColor() method. x[k] should be set to 0 and tried for the next color c in the for loop.

[@prateekkej2506]

actually there is .when we call graphColor(k+1) if it fails then it will return to the next iteration in its parent graphColor()'s for loop where it will continue to try other colors and if its does not returns that means its color was right from the first call.

[@lquqpgqr]

Is it possible to replace this recursion with for loop.

[@SarbotamChatterje]

can u please explain c==x[i] part?

[@CSBreakdown]

+Sarbottam Chatterjee Hi, so x[i] is an array that holds colors if the nodes that have already been colored. So c == x[i] is checking if the current color that you are trying to place (c) is equal to the color value at x[i] (the already colored nodes). If 2 nodes are adjacent (meaning if G[k][i] == 1 AND the adjacent node at x[i] has the same color, then it returns false because we can't place the same colour next to it.

[@SarbotamChatterje]

Thant clears my doubt. Thanks for making time to reply to my comment. Do you have a Traveling Salesman Problem solution using Dynamic Programming?

[@CSBreakdown]

+Sarbottam Chatterjee I don't unfortunately. The travelling salesman problem is NP-Complete. If I had a true solution to the problem, I would be the worlds richest man! Travelling salesman is best done with approximation algorithms using current technologies. With a large enough value of N, travelling salesman cannot be accurately solved. Maybe there are solutions out there for small enough values of N, but I'm not aware of one and haven't attempted the problem.

[@ZiiiP2142]

There's no backtracing in the code. :D

[@NS-gr9cy]

Its greedy and not backtracking