登录
  • #刷题

请教‌‌‍‍‌‍‍‌‍‌‍‍‌‌‌‍‌‌‌‌‌‌‍‍‍‌‍‍‍‌‌‌Graph Coloring的问题

googlerr
1316
1
题目描述:给一个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代码中有下面这一块:
/* Check if assignment of color c to v[br][/br][br][/br]               is fine*/[br][/br][br][/br]            if (isSafe(v, graph, color, c))[br][/br][br][/br]            {[br][/br][br][/br]                color[v] = c;[br][/br][br][/br] [br][/br][br][/br]                /* recur to assign colors to rest[br][/br][br][/br]                   of the vertices */[br][/br][br][/br]                if (graphColoringUtil(graph, m,[br][/br][br][/br]                                      color, v + 1))[br][/br][br][/br]                    return true;[br][/br][br][/br] [br][/br][br][/br]                /* If assigning color c doesn't lead[br][/br][br][/br]                   to a solution then remove it */
其中
color[v] = 0;
代表backtracking. 但我将这句改成直接return false,然后测试了很多graph都没有发现问题。所以不知道是不是自己哪里理解不对。
1条回复
热度排序

发表回复