数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言程序设计
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 程序演示 4 色问题的实现
这是一个 C++ 程序，演示 4 色问题的实现。
算法
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];
//initialize all colors value as 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
更新于:30-Jul-2019
551 次浏览
广告