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

such detail, much appreciation~

Thanks Sir! Understood the solution in one go.💯

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

minor mistakes but you are a life savior man

A really good explanation as well as clean code

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

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

Superb explanation.!

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

This is amazing explanation. thanks :)

beautifully explained :) tysm!

Terrific explanation

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?

Awesome Explanation. Saved me (Y)

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

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?

Will the algorithm work for directed graphs as well ?

you nailed it man!!!

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

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 )

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.

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.

any videos on forward checking ?

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

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

7 жыл бұрын

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

7 жыл бұрын

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

@mayankgupta2543

5 жыл бұрын

@@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

2 жыл бұрын

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

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

great video thnks

Thanks a lot

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

Thanks

It R was Really very Useful

Best graph colouring video on youtube !

how do we know m if they dont let you know

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

@constructor365

7 жыл бұрын

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

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

awesome

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

2 жыл бұрын

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

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

6 жыл бұрын

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

@mohamedberrimi4850

6 жыл бұрын

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

why 0,0 adjancy matrix 1

link to the code?

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

Helps in today's exam

Which part of the code shows the backtracking?

@prateekkej2506

7 жыл бұрын

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.

Nice..

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

@CSBreakdown

8 жыл бұрын

+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

8 жыл бұрын

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

8 жыл бұрын

+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

8 жыл бұрын

+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

8 жыл бұрын

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

best graph coloring video :D

Is it possible to replace this recursion with for loop.

doesn't work for larger graphs

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

@CSBreakdown

8 жыл бұрын

+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

8 жыл бұрын

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

8 жыл бұрын

+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.

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

7 жыл бұрын

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.

shouldnt it be m^n ways ?

There's no backtracing in the code. :D

very nice !!!!!!!!!

Its greedy and not backtracking