本文共 2624 字，大约阅读时间需要 8 分钟。

算法——四处碰壁回溯法02图解回溯

一.图着色问题

问题描述:

给定无向连通图G=(V,E),求最小的整数m,用m种颜色是的对G中任意相连的顶点颜色不一致。

算法过程:

初始化定义数组color[n],其值全为0,同时将color[0]赋值1，表示节点涂上颜色1，设一个计数器k=1；表示已经有一个节点涂上颜色。

while(k<n)

①对color[k]开始颜色搜索，如果找到第一个没有颜色冲突的颜色(当然这个颜色值必然是小于m的)就为其赋值,进入②，否则进入③。

②k=k+1;处理下一个节点

③color[k]=0;k=k-1,进行回溯

循环结束返回true

算法复杂度分析:

用m种颜色来涂n节点的连通图，那么我们这里举一个例子，如图(m=3,n=5)：

import org.junit.Test;/** * @author jackTan */public class AlgrithimTest {
       @Test    public void Test(){
           int edges[][] = {
                   {
   0,1,1,0,0},                {
   1,0,1,1,1},                {
   1,1,0,0,1},                {
   0,1,0,0,1},                {
   0,1,1,1,0}        };        int[] ints = GraphColor(edges, 3);        for (int anInt : ints) {
               System.out.print(anInt+" ");        }    }    int[] GraphColor(int [][]edges,int m){
           int n = edges.length;        int []color = new int[n];        color[0]=1;        int k=1;        while(k

输出:

二.哈密顿回路问题

这个问题也可以用动态规划来解决，可以参见这篇文章:

问题描述: 给定无向连通图G,邱一条从顶点0出发经过所有城市再回到0的哈密顿回路。

算法过程:

初始化数组visited[n];赋值全为0表示都未被访问过。利用x[n]来存储哈密顿回路的节点顺序,x[n]全为0。

从顶点0出发，那么visited[0]=1;x[0]=0;k=1(记录下一个要标记的顶点)

while(k<=n-1）{

x[k]++;

{循环,若x[k]未被访问过且x[k-1]到x[k]有边且k<n就跳出,否则就x[k]++}

{若k==n则,k–,x[k]=0;

否则k++;}

}

下面代码演示的是下面这张图:

import org.junit.Test;/** * @author jackTan */public class AlgrithimTest {
       @Test    public void Test(){
           int edges[][] = {
                   {
   0,1,0,1,0},                {
   1,0,1,0,1},                {
   0,1,0,1,1},                {
   1,0,1,0,1},                {
   0,1,1,1,0}        };        int[] ints = Hamiton(edges);        for (int anInt : ints) {
               System.out.print(anInt+1+" ");        }    }    int[] Hamiton(int [][]edges){
           int n = edges.length;        int []visited = new int[n];        int []x = new int[n];        visited[0]=1;        x[0]=0;        int k=1;        while(k<=n-1){
               x[k]++;            while(x[k]<=n-1&&!IsOK(edges,x,visited,k)){
                 x[k]++;            }            if(x[k]==n){
                   visited[x[k-1]]=0;                x[k]=0;                k--;            }else{
                   visited[x[k]]=1;                k++;            }            if(k==n&&edges[x[k-1]][0]==0){
                   visited[x[k-1]]=0;                k--;            }        }        return x;    }    boolean IsOK(int [][]edges,int x[],int []visited,int k){
           if(edges[x[k-1]][x[k]]==1&&visited[x[k]]==0){
               return  true;        }else {
               return false;        }    }}

转载地址：http://ztlzi.baihongyu.com/