秒懂算法 | 满m叉树模型——图的m可着色问题的回溯算法

实例图解该问题回溯算法求解过程。

01、实例构造

给定如图5-43所示的无向连通图和m=3。

图5-43 无向连通图

图的m着色问题的搜索过程如图5-44~图5-49所示。从根节点A开始，节点A是当前的活节点，也是当前的扩展节点，它代表的状态是给定无向连通图中任何一个顶点还没有着色，如图5-44(a)所示。沿着x1=1分支扩展，满足约束条件，生成的节点B成为活节点，并且成为当前的扩展节点，如图5-44(b)所示。扩展节点B沿着x2=1分支扩展，不满足约束条件，生成的节点被剪掉。然后沿着x2=2分支扩展，满足约束条件，生成的节点C成为活节点，并且成为当前的扩展节点，如图5-44(c)所示。扩展节点C沿着x3=1，2分支扩展，均不满足约束条件，生成的节点被剪掉。然后沿着x3=3分支扩展，满足约束条件，生成的节点D成为活节点，并且成为当前的扩展节点，如图5-44(d)所示。