C ++程序使用2色算法检查图是否为二分图
二分图是其中可以使用两种颜色进行着色的图形，即：一组顶点的颜色相同。这是一个C++程序，使用2色算法检查图形是否为二分图。
函数和伪代码
Begin
1. 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.
2. function graphColoringtil(bool g[V][V], int k, int col[], int v) :
g[V][V] = It is a 2D array where V is the number of vertices in graph
k = 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 k
if (isSafe(v, g, col, c))
col[v] = c
if (graphColoringtil (g, k, col, v+1) == true)
return true
col[v] = 0
return false
3.function graphColoring(bool g[V][V], int k):
for i = 0 to V-1
color[i] = 0
if (graphColoringtil(g, k, color, 0) == false)
return false
return true示例
#include <iostream>
#include <cstdio>
#define V 4
using namespace std;
bool isSafe (int v, bool g[V][V], int col[], int C) //to solve m coloring //problem
{
for (int i = 0; i < V; i++)
if (g[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;
}输出结果
The graph is Bipartite
热门推荐
10 小侄过生日祝福语简短
11 小店营业的祝福语简短
12 担任老师的祝福语简短
13 饮料吧台祝福语简短大气
14 公司新春搞笑祝福语简短
15 高情商敬酒祝福语简短
16 婚礼祝福语新郎妹妹简短
17 教师答辩通过祝福语简短
18 生女孩红包简短祝福语
