图的m着色（回溯法）

Myth丶恋晨 2022-06-18 01:56 202阅读 0赞

//
    //Description:图的m着色问题(回溯法)
    //
    #include <iostream>
    using namespace std;
    
    int n;//图的顶点个数
    int m;//可用颜色数
    int a[21][21];//程序中使用时从下标1开始;程序中用于存储图的邻接矩阵
    int x[20];//用于存储当前解
    static  long sum;//当前已找到的可m着色方案数
    
    bool ok(int k)
    {
    	for (int j = 1; j <= n; j++)
    	{
    		if (a[k][j] && (x[j] == x[k]))
    			return 0;
    	}
    	return 1;
    }
    
    void backtrack(int t)
    {
    	if (t>n)
    	{
    		sum++;
    		cout << "        第" << sum << "种解决方案为 ：\n";
    		for (int i = 1; i <= n; i++)
    		{
    			cout << x[i] << " ";
    		}
    		cout << endl;
    	}
    	else
    	{
    		for (int i = 1; i <= m; i++)
    		{
    			x[t] = i;
    			if (ok(t))
    			{
    				backtrack(t + 1);
    			}
    			x[t] = 0;
    		}
    	}
    }
    
    
    long mColoring(int mm)
    {
    	m = mm;
    	sum = 0;
    	backtrack(1);
    	return sum;
    }
    
    void inputRenc(int  p[21][21])
    {
    	for (int i = 1; i <= n; i++)
    	{
    		for (int j = i + 1; j <= n; j++)  //**分析为什么如邻接矩阵中[1][1]为1？？？
    		{
    			cout << "请输图的邻接矩阵中[" << i << "][" << j << "]的值" << endl;
    			cin >> p[i][j];
    			p[j][i] = p[i][j];
    		}
    		cout << endl;
    	}
    }
    
    void  outputRenc(int  p[21][21])
    {
    	for (int i = 1; i <= n; i++)
    	{
    		for (int j = 1; j <= n; j++)
    		{
    			cout << p[i][j] << ' ';
    		}
    		cout << endl;
    	}
    
    }
    void main()
    {
    	cout << "\n\t==========图的m着色问题============\n";
    	cout << "Please enter the number of points and colors :\n";
    	cin >> n >> m;
    	cout << "\n==========(输入)图的邻接矩阵\n";
    	inputRenc(a);
    	cout << "\n==========(输出)图的邻接矩阵\n";
    	outputRenc(a);
    	cout << "\n==========判断可着色性\n";
    	mColoring(m);
    	if (sum == 0)
    		cout << "  无可行方案！" << endl;
    	cout << "-------------------------------------------------------------------------------" << endl;
    	cout << n << " 个顶点" << "按所给的邻接关系着 " << m << " 种颜色，总的着色方案有 " << sum << " 个\n";
    
    }