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
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
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).
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?
+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.
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.
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.
+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.
Very clear. Would be great if also made topic on tsp, vehicle routing, LP dual to make them clear as well ..
Great video man! the clarity! the explanation! :D
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.
minor mistakes but you are a life savior man
such detail, much appreciation~
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 )
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.
Why is this a backtracking problem? We are not making any changes in the previous node's color
A really good explanation as well as clean code
how can the diagnals be set as 1 of an adjacency matrix ..it is always 0..
loved the explanation , thnkuuu so much for the video, it was really helpful
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.
awesome dude, really cool explanation and the graphics were also pretty helpful. Thanks !!!
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
very clear. organizing helps a lot.
thanks very much, such big help.
Great explanation... understood it in one go...keep up the good work!!
thanks for this good video it helped me to understand programming logic more better
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 .
Superb explanation.!
What if I want to find out all possibilities of coloring ? all valid combinations ?
Terrific explanation
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
This is amazing explanation. thanks :)
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?
beautifully explained :)
tysm!
Helps in today's exam
Awesome Explanation. Saved me
(Y)
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?
why 0,0 adjancy matrix 1
you nailed it man!!!
Will the algorithm work for directed graphs as well ?
how do we know m if they dont let you know
any videos on forward checking ?
It R was Really very Useful
Sir,, can this program work on scilab software??
Thanks a lot
Thanks
doesn't work for larger graphs
Best graph colouring video on youtube !
(0,0) of adjacency matrix shud be 1.. similarle for 1,1 2,2 n 3,3
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
great video thnks
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?
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.
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.
shouldnt it be m^n ways ?
There's no backtracing in the code. :D
awesome
Nice..
best graph coloring video :D
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.
Is it possible to replace this recursion with for loop.
very nice !!!!!!!!!
Its greedy and not backtracking