C ++程序演示四色问题的实现
这是一个演示4色问题实现的C++程序。
算法
Begin
Develop function issafe() to check if the current color assignment
is safe for vertex v i.e. checks whether the edge exists or not.
If it exists,
then next check whether the color to be filled in the new vertex is already used by its adjacent vertices.
End
Begin
Function graphColoringtil(bool graph[V][V], int m, int col[], int v)
solve 4 coloring problem:
Here,
g[V][V] = It is a 2D array where V is the number of vertices in graph
m = maximum number of colors that can be used.
col[] = an color array that should have numbers from 1 to m.
if v == V
return true
For c = 1 to 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():
It mainly uses graphColoringUtil() to solve the problem.
It returns false if the m colors cannot be assigned,
otherwise return 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) //If all vertices are assigned a color then
return true;
for (int c = 1; c <= k; c++) { //Consider this vertex v and try different colors
if (isSafe(v, g, col, c)) { //Check if assignment of color c to v is fine
col[v] = c;
if (graphColoringtil (g, k, col, v+1) == true) //recur to assign colors to rest of the vertices
return true;
col[v] = 0; //If assigning color c doesn't lead to a solution then remove it
}
}
return false;
}
void solution(int color[]) {
cout<<"The assigned colors are: \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<<"Solution does not exist";
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;
}输出结果
The assigned colors are: 1 2 3 1 1
热门推荐
10 新年门口花束祝福语简短
11 盘锦结婚祝福语大全简短
12 父母生日祝福语 简短独特
13 家庭恩爱祝福语简短英文
14 高考俄语祝福语大全简短
15 虎年祝福语 诗句唯美简短
16 生日婚礼祝福语简短精辟
17 虎年喝酒拜年祝福语简短
18 教师闺蜜祝福语简短