图着色问题的回溯算法
- 格式：doc
- 大小：22.50 KB
- 文档页数：4
● 图着色问题的回溯算法：(非递归算法，求一个解)
非递归算法：
算法 m-COLORING
输入：正整数m, n和含n个顶点的无向连通图G的邻
接矩阵graph。
输出: 图G的m着色问题的一个解x[1..n], 若无解，则
输出no。solution。
flag=false //用flag标记问题是否有解。
k=1 ; x[1]=0
while k>=1 and not flag
while x[k]
色。
if color(k) then //第k个顶点的当前颜色合
法。
if k=n then flag=true //x[1..n]是一个解
else //x[1..k]是部分解
k=k+1 //准备对下一个顶点着色。
x[k]=0
end if
end if //否则，剪枝
end while
k=k-1 //回溯
end while
if flag then output x //输出一个解
else output “no solution” //输出无解
end m-COLORING
过程 color (k)
//在前k-1个顶点已着色的情况下，判断第k个
顶点是否可
//着颜色x[k], 是则返回true, 否则返回false。
j=1
while j
return false
else j=j+1
end while
return true
end color
递归算法：
算法 m-COLORING
输入：正整数m, n和含n个顶点的无向连通图G的邻
接矩阵graph。
输出: 图G的m着色问题的一个解x[1..n], 若无解，
则输出no。
flag=coloring( 1 )
if flag then output x //输出一个解
else output “No solution” //输出无解
end NQUEENREC1
过程 coloring(k)
//在前k-1个顶点已着色且满足着色条件的情况
下，求图的
// m着色问题的一个解，有解则返回true, 否则返
回false。
for i=1 to m
x[k]=i //试将第k个顶点着第i种颜色。
if color(k) then //第k个顶点的当前颜色合法。
if k=n then return true //x[1..n]是一个解
else //x[1..k]是部分解
t=coloring(k+1) //递归
if t then return true
end if
end if
end for
return false //无解
end coloring
