数据结构-图的着色问题

硅谷探秘者 11059 0 0

数据结构-图的着色问题

问题描述:

        图的m-着色判定问题——给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色,是否有一种着色法使G中任意相邻的2个顶点着不同颜色?


个人感觉图的着色问题类似与八皇后问题,使用回溯算法(试探法)解决


算法描述

       state[n]存储n个顶点的着色方案,可以选择的颜色为1到m。

        当t=1时,对当前第t个顶点开始着色:若t>n,则已求得一个解,输出着色方案即可。否则,依次对顶点t着色1-m, 若t与所有其它相邻顶点无颜色冲突,则继续为下一顶点着色;否则,回溯,测试下一颜色。

递归法:

package graph;

public class Graph2 {
    static int[][] e ;//图的邻接矩阵表示
    static int[] state ; //储存n个顶点的着色
    static int color = 6;//共有几种颜色
    static int count=0;
    static void sear(int index) {
        if (isOk(index)) {//判断当前状态能否着色
            if (index == e.length - 1) {//若全部着色输出
            	count++;
            } else {
                for (int i = 1; i <= color; i++) {//遍历所有的颜色 
                    state[index + 1] = i;
                    sear(index + 1);
                }
            }
        }
    }
    private static void show(int index) {
        for (int i = 1; i <= index; i++) {
            System.out.print(state[i]+" ");
        }
        System.out.println();
    }
    private static boolean isOk(int index) {
        for (int i = 1; i < index; i++) {
            if (e[index][i] == 1 && state[i] == state[index])//当两个节点是连同并且颜色一样则返回false
                return false;
        }
        return true;
    }
    public static void main(String[] args) {
    	e=new int[][] {{0,0,0,0,0,0,0,0,0,0,0,0,0,0},
			  {0,0,0,0,0,0,0,0,1,1,0,1,1,0},//1
			  {0,0,0,0,1,0,0,0,1,1,0,1,1,0},//2
			  {0,0,0,0,1,0,0,0,0,1,0,0,0,1},//3
			  {0,0,1,1,0,1,0,0,0,0,1,1,0,0},//4
			  {0,0,0,0,1,0,1,0,0,0,0,0,1,1},
			  {0,0,0,0,0,1,0,1,0,0,1,0,0,0},
			  {0,0,0,0,0,0,1,0,1,0,1,1,1,0},//7
			  {0,1,1,0,0,0,0,1,0,1,0,0,1,0},
			  {0,1,1,1,0,0,0,0,1,0,0,0,0,0},
			  {0,0,0,0,1,0,1,1,0,0,0,0,0,1},
			  {0,1,1,0,1,0,0,1,0,0,0,0,0,1},
			  {0,1,1,0,0,1,0,1,1,0,0,0,0,0},
			  {0,0,0,1,0,1,0,0,0,0,1,1,0,0}};;
    	state=new int[e.length];
    	long l=System.currentTimeMillis();
        sear(0);
    	long l2=System.currentTimeMillis();
    	System.out.println(count);
    	System.out.println(l2-l);
    }
}

非递归法(虽然能解决问题,但是效率太低,但是也贴出来)

package graph;

import java.util.Stack;
public class Graph {
	static int[][] e ;//图的邻接矩阵表示
    static int[] state ; //储存n个顶点的着色
    static int color = 6;//共有几种颜色
    static int count=0;
    public static int setColor() {
    	Stack<Integer> s=new Stack<Integer>();//用于保存之前的着色颜色
    	int tindex=1;//当前节点
    	int tc=1;//当前颜色
    	state[tindex]=tc;
    	while(!s.isEmpty()||tc<=color) {
    		if(tindex>=e.length) {
    			tc=s.pop()+1;
    			tindex--;
    			state[tindex]=0;
    		}
    		if(tc>color) {
    			tc=s.pop()+1;
    			tindex--;
    			state[tindex]=0;
    			continue;
    		}
    		if(isOk(tindex,tc)) {//能着色
    			s.push(tc);
    			tindex++;
    			tc=1;
    			if(tindex==e.length) {
    				count++;
    			}
    		}else {//不能着色-遍历下一个颜色
    			tc++;
    		}
    	}
    	return 1;
    }
    private static boolean isOk(int index,int tc) {
    	state[index]=tc;
        for (int i = 1; i < index; i++) {
            if (e[index][i] == 1 && state[i] == state[index]) {//当两个节点是连同并且颜色一样则不满足返回false
            	state[index]=0;
                return false;
            }
        }
        return true;
    }
    private static void show(int index) {
        for (int i = 1; i <= index; i++) {
            System.out.print(state[i]+" ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
    	e=new int[][] {{0,0,0,0,0,0,0,0,0,0,0,0,0,0},
			  {0,0,0,0,0,0,0,0,1,1,0,1,1,0},//1
			  {0,0,0,0,1,0,0,0,1,1,0,1,1,0},//2
			  {0,0,0,0,1,0,0,0,0,1,0,0,0,1},//3
			  {0,0,1,1,0,1,0,0,0,0,1,1,0,0},//4
			  {0,0,0,0,1,0,1,0,0,0,0,0,1,1},
			  {0,0,0,0,0,1,0,1,0,0,1,0,0,0},
			  {0,0,0,0,0,0,1,0,1,0,1,1,1,0},//7
			  {0,1,1,0,0,0,0,1,0,1,0,0,1,0},
			  {0,1,1,1,0,0,0,0,1,0,0,0,0,0},
			  {0,0,0,0,1,0,1,1,0,0,0,0,0,1},
			  {0,1,1,0,1,0,0,1,0,0,0,0,0,1},
			  {0,1,1,0,0,1,0,1,1,0,0,0,0,0},
			  {0,0,0,1,0,1,0,0,0,0,1,1,0,0}};;
    	state=new int[e.length];
    	long l=System.currentTimeMillis();
    	setColor();
    	long l2=System.currentTimeMillis();
    	System.out.println(count);
    	System.out.println(l2-l);
    }
}


猜你喜欢
数据结构与算法 442 约瑟夫环描述有m个人,围成一个环,编号为1、2、3、、、m,从第一个人开始循环报(从1开始),假设到n那个人出局,然后从下一个人继续(从1开始),到n出列,以此循环,最后那个人为
前端(h5) 514 h2h1----h2--------h3h1----h3----h2--------h42.案例如:本文就介绍如何使用js设计,巧妙利用双向链表实现将顺序目录,转换成树状目录。3.js代码scr
数据结构与算法 497 原文链接:https://www.zhihu.com/question/23148377?sort=created算法基础 时间复杂度 空间复杂度基础 线性表 列表(必学) 链表(必学
数据结构与算法 3855 堆排序(英语:Heapsort)是指利用堆这种所设计一种排序算法。堆是一个近似完全二叉树,并同时满足堆积性质:即子键值或索引总是小于(或者大于)它父节点。以最小堆为例下沉操
数据结构与算法 799 广度优先搜索算法(dfs、深搜)java实现-和算法用邻接矩阵表示定点之间关系如下:则用邻接矩阵表示为: privatestaticintmap[][]={ {0,3,6
数据结构与算法 835 上一篇:广度优先搜索算法(bfs、广搜)java实现-和算法用邻接矩阵表示定点之间关系如下则用邻接矩阵表示为: privatestaticintmap
数据结构与算法 4699 描述:思路:用组表示完全二叉树,用先序遍历方式遍历每一层节点,用一个组储存每一层和,因为规模小于100000所以用一个容量为17组即可。计算完每一层和,再比较层最小之和最大
数据结构与算法 496 prim(普里姆)算法求出。对于任何一个或算法,理解和实现只是一个方面,更重要是要明白它应用范围或应用场景,最小生成树算法应用非常广泛,例如:假设要在n个城市之间建立通信联络网,则连接n个
归档
2018年11月  12 2018年12月  33 2019年01月  28 2019年02月  28 2019年03月  32 2019年04月  27 2019年05月  33 2019年06月  6 2019年07月  12 2019年08月  12 2019年09月  21 2019年10月  8 2019年11月  15 2019年12月  25 2020年01月  9 2020年02月  5 2020年03月  16 2020年04月  4 2020年06月  1 2020年07月  7 2020年08月  13 2020年09月  9 2020年10月  5 2020年12月  3 2021年01月  1 2021年02月  5 2021年03月  7
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo
目录