使用 2 色算法检查图是否为二分图的 C++ 程序

如果一个图可以用两种颜色进行着色即图的着色是可能的，则该图是二分图（例如：一组中顶点的颜色相同）。这是一个使用 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

Arjun Thakur

更新于： 30-Jul-2019

232 次浏览

启动你的职业

完成课程以获取认证

开始学习