数据结构-图的着色问题

硅谷探秘者 12432 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);
    }
}



评论区
请写下您的评论...
暂无评论...
猜你喜欢
数据结构与算法 1578 约瑟夫环描述有m个人,围成一个环,编号为1、2、3、、、m,从第一个人开始循环报(从1开始),假设到n那个人出局,然后从下一个人继续(从1开始),到n出列,以此循环,最后那个人为
前端(h5) 1475 h2h1----h2--------h3h1----h3----h2--------h42.案例如:本文就介绍如何使用js设计,巧妙利用双向链表实现将顺序目录,转换成树状目录。3.js代码scr
数据结构与算法 1809 原文链接:https://www.zhihu.com/question/23148377?sort=created算法基础 时间复杂度 空间复杂度基础 线性表 列表(必学) 链表(必学
数据结构与算法 4660 堆排序(英语:Heapsort)是指利用堆这种所设计一种排序算法。堆是一个近似完全二叉树,并同时满足堆积性质:即子键值或索引总是小于(或者大于)它父节点。以最小堆为例下沉操
数据结构与算法 5614 描述:思路:用组表示完全二叉树,用先序遍历方式遍历每一层节点,用一个组储存每一层和,因为规模小于100000所以用一个容量为17组即可。计算完每一层和,再比较层最小之和最大
数据结构与算法 2509 上一篇:广度优先搜索算法(bfs、广搜)java实现-和算法用邻接矩阵表示定点之间关系如下则用邻接矩阵表示为: privatestaticintmap
数据结构与算法 2321 广度优先搜索算法(dfs、深搜)java实现-和算法用邻接矩阵表示定点之间关系如下:则用邻接矩阵表示为: privatestaticintmap[][]={ {0,3,6
数据结构与算法 1465 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 2021-04  4 2021-05  4 2021-06  1 2021-07  7 2021-08  2 2021-09  8 2021-10  9 2021-11  16 2021-12  14 2022-01  7 2022-05  1 2022-08  3 2022-09  2 2022-10  2 2022-12  5 2023-01  3 2023-02  1 2023-03  4 2023-04  2 2023-06  3 2023-07  4 2023-08  1 2023-10  1 2024-02  1 2024-03  1
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job rabbitmq haproxy srs 音视频 webrtc javascript
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。