代码之家 › 专栏 › 技术社区 › CMPS

使用深度优先遍历为图形着色

graph-coloring brute-force depth-first-search graph

0

CMPS · 技术社区 · 12 年前

我知道,对于着色图节点,回溯/暴力是一种常见的解决方案。但我想知道,使用DFS是否也可以实现解决方案?

回溯为您提供了返回并尝试其他颜色可能性的机会,以便使用N种颜色绘制所有节点

DFS将从一个节点开始并对其进行着色,然后跳到其邻居并将其着色为与邻居不同的颜色等。。。

我搜索了一下使用这种方法,但没有找到使用这种方法的算法。

问题:是否可以使用DFS为图节点着色。如果是,它是否比回溯更有效?

非常感谢。

1 回复 | 直到 12 年前

1

chesslover 12 年前

我认为在比较回溯和DFS相关顶点着色时存在一些混淆。图的DFS遍历给出了与其结构相关的序列中其顶点的完整枚举。然而,它并不构成顶点着色问题的完整枚举,这需要考虑顶点的可能颜色。

因此,如果我理解正确的话,您所实现的是DFS指导的图的贪婪启发式着色。另一方面,如您所称的回溯/暴力解决方案(例如 [Randall-Brown 72] )将为最小着色问题提供精确的解决方案,因为它考虑了每个可能的顶点着色。请注意,DFS遍历可用于最初对顶点进行排序(拓扑排序),并将该顺序提供给精确的解算器。