着色问题 -- 多种颜色

着色问题 -- 多种颜色

着色问题 -- 多种颜色

• • 1.邻接表 深搜 暴力做法
  • • 1.1问1
    • • 1.1.1c++
      • 1.1.2Java
    • 1.2问2
    • • 1.2.1c++
      • 1.2.2Java

下图是为了解释DFS()函数中的color[v] = 0语句;

题目:
输入无向图的_case个数,指定每个图的顶点个数N，边数E，图着色的颜色数量M,
以及边的具体情况.
问1:图中相连的点不是同色的.有多少中可能.

或
输入无向图的个数,指定每个图的顶点个数N，边数E,以及边的具体情况.
问2:图中相连的点不是同色的,至少要多少种颜色,并输出所有结果.

1.邻接表 深搜 暴力做法 1.1问1 1.1.1c++

#include 
#include 
#include 
#include 

using namespace std;

int _case;				   // 图数,边的起点,终点
int N, E, M;			   // 顶点数,边数和颜色数；
vector > Graph; // 存放图的结构；
vector color;		   // 所图的颜色
int resCnt = 0;			   // 结果的总数

bool ok(int k)
{
	for (int j = 1; j <= N; j++)
		if (Graph[j][k] == 1 && color[k] == color[j])
			return false; // 点j与点k相连,且同色返回false
	return true;		  // 有两种可能:
						  // ①点k与其他点都不相连,说明这个颜色可以图
						  // ②相连但不同色,说明这个颜色可以图
						  // 于是就可以涂下一个点的颜色
}

void DFS(int v)
{
	if (v > N)
	{								 //满足条件说明前N个顶点都确定了颜色
		for (int i = 1; i <= N; i++) //依次所有顶点涂的颜色
			cout << color[i] << " ";
		resCnt++; //涂的方法数+1;
		cout << endl;
		return;
	}
	else
	{
		for (int i = 1; i <= M; i++)
		{					//访问每一种涂法方法；
			color[v] = i;	//涂上颜色；
			if (ok(v))		//返回true说明,满足涂色的规则；
				DFS(v + 1); //n那么就进行下一个顶点的涂色；
			color[v] = 0;	//回溯,避免后面的点影响前面的点着色,
		}
	}
}

int main()
{

	cin >> _case;
	while (_case--)
	{
		cin >> N >> E >> M; //顶点数,边数,颜色数

		//防止上一个图的遗留数据影响到这个图
		Graph.clear();
		Graph.resize(N + 2);
		for (int k = 0; k < N + 2; ++k)
		{
			Graph[k].resize(N + 2); //每行为c列
		}
		int a, b;
		while (E--)
		{ //输入边
			cin >> a >> b;
			Graph[a][b] = Graph[b][a] = 1; //1表示两个点相连
		}
		resCnt = 0; //结果数
		color.clear();
		color.resize(N + 2);
		DFS(1); //从第一个顶点开始
		cout << "Total=" << resCnt << endl
			 << endl;
	}

	return 0;
}

1.1.2Java

import java.util.Scanner;


public class Main{
    static int _case, n, e, m;//图,点,边,颜色
    static int[][] q;//邻接表存图结构
    static int[] col;//结点涂色情况(什么色)
    static int a, b, res;//边的起点,边的终点,涂色方案总数

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("请输入图的数量:");
        _case = in.nextInt();
        while (_case-- > 0) {
        		//点数,边数,颜色数
            n = in.nextInt();
            e = in.nextInt();
            m = in.nextInt();
            //根据上面数据设置邻接表大小
            q = new int[n + 2][n + 2];
            while (e-- > 0) {
            		//输入边
                a = in.nextInt();
                b = in.nextInt();
                q[a][b] = q[b][a] = 1;
            }
            //同上
            col = new int[n + 2];
            res=0;
            dfs(1);
            System.out.println("一共有"+res+"种可能.");
        }
    }

    private static void dfs(int v) {
        if (v > n) {
            res++;
            for (int i = 1; i <= n; i++) {
                System.out.print(col[i]);
                System.out.print(' ');
            }
            System.out.println();
        }else{
            for (int i = 1; i <= m; i++) {
                col[v]=i;
                if(ok(v)){
                    dfs(v+1);
                }
                col[v]=0;
            }

        }
    }

    private static boolean ok(int v) {
        for (int i = 1; i <=n ; i++) {
            if(q[i][v]==1&&col[i]==col[v])return false;
        }
        return true;
    }
}

1.2问2 1.2.1c++

#include 
#include 
#include 
#include 

using namespace std;

int _case;				   // 图数,边的起点,终点
int N, E, M;			   // 顶点数,边数和颜色数；
vector> Graph; // 存放图的结构；
vector color;		   // 所图的颜色
int resCnt = 0;			   // 结果的总数

bool ok(int k)
{
	for (int j = 1; j <= N; j++)
		if (Graph[j][k] == 1 && color[k] == color[j])
			return false; // 点j与点k相连,且同色返回false
	return true;		  // 有两种可能:
						// ①点k与其他点都不相连,说明这个颜色可以图
						// ②相连但不同色,说明这个颜色可以图
						// 于是就可以涂下一个点的颜色
}

void DFS(int v)
{
	if (v > N)
	{								 //满足条件说明前N个顶点都确定了颜色
		for (int i = 1; i <= N; i++) //依次所有顶点涂的颜色
			cout << color[i] << " ";
		resCnt++; //涂的方法数+1;
		cout << endl;
		return;
	}
	else
	{
		for (int i = 1; i <= M; i++)
		{					//访问每一种涂法方法；
			color[v] = i;	//涂上颜色；
			if (ok(v))		//返回true说明,满足涂色的规则；
				DFS(v + 1); //n那么就进行下一个顶点的涂色；
			color[v] = 0;	//回溯,避免后面的点影响前面的点着色,
		}
	}
}

int main()
{

	cin >> _case;
	while (_case--)
	{
		cin >> N >> E; //顶点数,边数,颜色数
		M = 2;
		//防止上一个图的遗留数据影响到这个图
		Graph.clear();
		Graph.resize(N + 2);
		for (int k = 0; k < N + 2; ++k)
		{
			Graph[k].resize(N + 2); //每行为c列
		}
		int a, b;
		while (E--)
		{ //输入边
			cin >> a >> b;
			Graph[a][b] = Graph[b][a] = 1; //1表示两个点相连
		}
		while (true)
		{
			resCnt = 0; //结果数
			color.clear();
			color.resize(N + 2);
			DFS(1); //从第一个顶点开始
			if (resCnt > 0)
			{
				cout << "至少要" << M << "种颜色" << endl;
				cout << "Total=" << resCnt << endl
					<< endl;
				break;
			}
			M++;
		}
	}

	return 0;
}

1.2.2Java

import java.util.Scanner;


public class Main {
    static int _case, n, e, m;//图,点,边,颜色
    static int[][] q;//邻接表存图结构
    static int[] col;//结点涂色情况(什么色)
    static int a, b, res;//边的起点,边的终点,涂色方案总数

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("请输入图的数量:");
        _case = in.nextInt();
        while (_case-- > 0) {
            //点数,边数,颜色数
            n = in.nextInt();
            e = in.nextInt();
            m = 2;
            //根据上面数据设置邻接表大小
            q = new int[n + 2][n + 2];
            while (e-- > 0) {
                //输入边
                a = in.nextInt();
                b = in.nextInt();
                q[a][b] = q[b][a] = 1;
            }
            //同上
            while (true) {
                col = new int[n + 2];
                res = 0;
                dfs(1);
                if (res > 0) {
                    System.out.println("至少"+m+"种颜色.");
                    System.out.println("一共有" + res + "种可能.");
                    break;
                }
                m++;
            }
        }
    }

    private static void dfs(int v) {
        if (v > n) {
            res++;
            for (int i = 1; i <= n; i++) {
                System.out.print(col[i]);
                System.out.print(' ');
            }
            System.out.println();
        } else {
            for (int i = 1; i <= m; i++) {
                col[v] = i;
                if (ok(v)) {
                    dfs(v + 1);
                }
                col[v] = 0;
            }

        }
    }

    private static boolean ok(int v) {
        for (int i = 1; i <= n; i++) {
            if (q[i][v] == 1 && col[i] == col[v]) return false;
        }
        return true;
    }
}