C++ 程序演示 4 色问题的实现
c++server side programmingprogramming更新于 2024/10/25 1:36:00
这是一个 C++ 程序演示 4 色问题的实现。
算法
开始 开发函数 issafe() 来检查当前颜色分配 对于顶点 v 是否安全，即检查边是否存在。 如果存在， 然后接下来检查新顶点中要填充的颜色是否已被其相邻顶点使用。 结束 开始 函数 graphColoringtil(bool graph[V][V], int m, int col[], int v) 解决 4 个着色问题: 这里， g[V][V] = 它是一个 2D 数组，其中 V 是图中的顶点数 m = 可以使用的最大颜色数。 col[] = 一个颜色数组，其数字应从 1 到 m。 如果 v == V 返回 true 对于 c = 1 到 m if (isSafe(v, g, col, c)) col[v] = c if (graphColoringtil (g, k, col, v+1) == true) return true col[v] = 0 return false End Begin function graphColor(): 主要使用graphColoringUtil()来解决问题。 如果m个颜色无法分配，则返回false， 否则返回true。 End
示例
#include <iostream>
#include <cstdio>
#define V 5
using namespace std;
bool isSafe (int v, bool graph[V][V], int col[], int C) {
for (int i = 0; i < V; i++)
if (graph[v][i] && C == col[i])
return false;
return true;
}
bool graphColoringtil(bool g[V][V], int k, int col[], int v) {
if (v == V) //如果所有顶点都分配了颜色则
返回 true;
for (int c = 1; c <= k; c++) { //考虑这个顶点 v 并尝试不同的颜色
if (isSafe(v, g, col, c)) { //检查将颜色 c 分配给 v 是否可以
col[v] = c;
if (graphColoringtil (g, k, col, v+1) == true) //重复为其余顶点分配颜色
return true;
col[v] = 0; //如果分配颜色 c 不能得到解决方案，则将其删除
}
}
return false;
}
void solution(int color[]) {
cout<<"指定的颜色为:\n";
for (int i = 0; i < V; i++)
cout<<color[i];
cout<<"\n";
}
bool graphColor(bool graph[V][V], int k) {
int *color = new int[V];
//将所有颜色值初始化为 0
for (int i = 0; i < V; i++)
color[i] = 0;
if (graphColoringtil(graph, k, color, 0) == false) {
cout<<"解决方案不存在";
return false;
}
solution(color);
return true;
}
int main() {
bool g[V][V] = {
{0, 0, 1, 0,1},
{1, 1, 1, 0,0},
{1, 1, 0, 0,1},
{0, 1, 1, 0,0}
};
int k= 4;
graphColor(g, k);
return 0;
}
输出
指定的颜色为: 1 2 3 1 1
