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.
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.
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 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
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?
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).
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
+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 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?
+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.
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.
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.
+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.
+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.
Great video man! the clarity! the explanation! :D
such detail, much appreciation~
minor mistakes but you are a life savior man
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 )
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.
how can the diagnals be set as 1 of an adjacency matrix ..it is always 0..
Thanks Sir! Understood the solution in one go.💯
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.
A really good explanation as well as clean code
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 ?
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
yup. The magic happens at graphColor(k+1). if it returns to parent function, the parent function will try another color.
@@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
@@jinxblaze but in isSafe they check all the nodes from 0 to n.
very clear. organizing helps a lot.
thanks very much, such big help.
awesome dude, really cool explanation and the graphics were also pretty helpful. Thanks !!!
Superb explanation.!
loved the explanation , thnkuuu so much for the video, it was really helpful
Terrific explanation
What if I want to find out all possibilities of coloring ? all valid combinations ?
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?
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
right,
or add an AND i != k to that if statement bool condition in isSafe()
the node is adjacent to it self , you should consider that .
Why is this a backtracking problem? We are not making any changes in the previous node's color
thanks for this good video it helped me to understand programming logic more better
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?
This is amazing explanation. thanks :)
Great explanation... understood it in one go...keep up the good work!!
beautifully explained :)
tysm!
Best graph colouring video on youtube !
Awesome Explanation. Saved me
(Y)
you nailed it man!!!
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).
This one uses m. If it fails, you can try m+1
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
Helps in today's exam
Will the algorithm work for directed graphs as well ?
Thanks
how do we know m if they dont let you know
why 0,0 adjancy matrix 1
Thanks a lot
great video thnks
wouldn't it be m^n possible ways(since for each vertex we have m choices)?...correct me if I'm wrong.
You're right. And m^n is what is shown in the video. Look again
any videos on forward checking ?
It R was Really very Useful
Sir,, can this program work on scilab software??
But if I dont have the "m" before coloring the graph?
+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.
To add, this is a known NP-Complete problem meaning there does not exist a solution that is polynomial time for large enough n.
+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?
+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.
+CSBreakdown Can you say if I understood the idea?
pastebin.com/7KbaYKGF
link to the code?
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.
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.
doesn't work for larger graphs
Which part of the code shows the backtracking?
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.
(0,0) of adjacency matrix shud be 1.. similarle for 1,1 2,2 n 3,3
awesome
best graph coloring video :D
shouldnt it be m^n ways ?
can u please explain c==x[i] part?
+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.
Thant clears my doubt. Thanks for making time to reply to my comment. Do you have a Traveling Salesman Problem solution using Dynamic Programming?
+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.
Nice..
Is it possible to replace this recursion with for loop.
There's no backtracing in the code. :D
very nice !!!!!!!!!
Its greedy and not backtracking