请教Graph Coloring的问题

题目描述：给一个graph（用二维0/1矩阵表示它里面vertex是否相连）和一个数字k，判断这个graph的所有vertex是否能用k种不同的颜色标记并且确保任意两个相连的vertex的颜色不同。

geeks for geeks上有这道题的详细说明：http://www.geeksforgeeks.org/backttracking-set-5-m-coloring-problem/，里面使用了backtracking的思路，但有一点很不解的是，我感觉backtracking那一块没有必要，不知道是不是考虑欠佳。


在geeks for geeks提供的Java代码中有下面这一块：

1. /* Check if assignment of color c to v
   
2.                is fine*/
   
3.             if (isSafe(v, graph, color, c))
   
4.             {
   
5.                 color[v] = c;
   
6. 
   
7.                 /* recur to assign colors to rest
   
8.                    of the vertices */
   
9.                 if (graphColoringUtil(graph, m,
   
10.                                       color, v + 1))
    
11.                     return true;
    
12. 
    
13.                 /* If assigning color c doesn't lead
    
14.                    to a solution then remove it */

复制代码

其中

1. color[v] = 0;

复制代码

代表backtracking. 但我将这句改成直接return false，然后测试了很多graph都没有发现问题。所以不知道是不是自己哪里理解不对。

OK，发现自己之前想错了。return false就成了greedy方法，而greedy在graph coloring上会有问题。。。