資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時裝研究
法律研究使用 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
更新於： 30-Jul-2019
232 次瀏覽
廣告