이분 그래프는 그래프 채색이 두 가지 색상, 즉, 세트의 꼭짓점은 같은 색으로 지정됩니다. 2색 알고리즘을 사용하여 그래프의 이분화 여부를 확인하는 C++ 프로그램입니다.
함수 및 의사코드
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