回溯法求解K图染色问题(java版)
问题描述:
对如图 1 所示的图,采用局部搜索算法,求其对应的 3 着色方案。
问题分析:
题目的目标是用3种颜色,将图1中的每个节点着色,且保证相邻节点间颜色不同;
a) 首先我们可以建立一个颜色集合
c
o
l
o
r
[
9
]
color[9]
color[9],存储每个节点的颜色
b) 从前向后遍历每个节点,让每个节点从3种颜色中选择一种颜色,判断是否与其相邻节点冲突;若冲突,则选则下一种颜色,没有颜色可选时,回溯至上一节点,更改其颜色
c) 当所有节点都着色,则结束程序
伪代码:
i
n
p
u
t
:
g
[
9
]
[
9
]
←
N
o
d
e
S
e
t
,
K
=
3
input:g[9][9]←Node Set,K=3
input:g[9][9]←NodeSet,K=3
o
u
t
p
u
t
:
c
o
l
o
r
[
9
]
output:color[9]
output:color[9]
f
o
r
e
a
c
h
foreach
foreach
n
o
d
e
node
node
i
n
in
in
N
N
N
c
h
o
o
s
e
choose
choose
a
a
a
c
o
l
o
r
color
color
f
o
r
for
for
n
o
d
e
node
node
i
f
:
c
h
e
c
k
(
n
o
d
e
)
if:check(node)
if:check(node)
g
o
t
o
:
n
e
x
t
N
o
d
e
goto:nextNode
goto:nextNode
e
l
s
e
else
else
c
h
o
o
s
e
choose
choose
a
n
o
t
h
e
r
another
another
c
o
l
o
r
color
color
f
o
r
for
for
n
o
d
e
node
node
i
f
if
if
n
o
no
no
c
o
l
o
r
color
color
c
a
n
can
can
c
h
o
o
s
e
choose
choose
t
h
e
n
then
then
b
a
c
k
T
r
a
c
e
backTrace
backTrace
f
r
o
n
t
N
o
d
e
frontNode
frontNode
局限性
回溯法求解K图着色问题,只能用于图节点个数较小的场景,当节点个数上百个时,回溯法的解空间过大,时间复杂度高;因此,对于上百个图节点的着色问题可以使用局部搜索法求解。
局部搜索法求解K图着色问题(java版)
具体实现
import java.util.Scanner;
public class KGraphColor{
static final int num=9;
static int[] color =new int[num];
public static void main(String [] args){
int m = 3;
int[][] g= {{0,1,1,1,0,0,0,0,0},
{1,0,0,0,1,0,0,0,1},
{1,0,0,0,0,0,0,1,0},
{1,0,0,0,0,0,1,1,0},
{0,1,0,0,0,1,0,1,0},
{0,0,0,0,1,0,0,0,0},
{0,0,0,1,0,0,0,1,1},
{0,0,1,1,1,0,1,0,0},
{0,1,0,0,1,0,1,0,0}};
graphColor(num,m,g);
}
public static boolean check(int k, int[][] g){
for(int i=0;i<k;++i){
if(g[k][i]==1 && color[i] == color[k]){
return false;
}
}
return true;
}
public static boolean graphColor(int n,int m,int[][] g){
int k=1;
while(k>=1){
while(color[k]<m){
if(check(k,g)){
break;
}
else{
++color[k];
}
}
if(color[k]<m&&k==n-1){
for(int i=0;i<n;++i){
System.out.print(color[i]+",");
}
System.out.println();
return false;
}else if(color[k]<m && k<n-1){
++k;
}else{
color[k]=0;
--k;
++color[k];
}
}
return true;
}
}
本文地址:https://blog.csdn.net/shiaiao/article/details/110245971
上一篇: 对如今网赚行业的常见几个问题的思考
下一篇: 草根站长工具:平时用的站长工具有哪些呢?