একটি গ্রাফকে একটি দ্বিপক্ষীয় গ্রাফ বলা হয়, যখন সেই গ্রাফের শীর্ষবিন্দুগুলিকে দুটি স্বাধীন সেটে ভাগ করা যায় যেমন গ্রাফের প্রতিটি প্রান্ত হয় প্রথম সেট থেকে শুরু হয় এবং শেষ হয় দ্বিতীয় সেট, বা দ্বিতীয় সেট থেকে শুরু হয়, প্রথম সেটের সাথে সংযুক্ত, অন্য কথায়, আমরা বলতে পারি যে একই সেটে কোন প্রান্ত পাওয়া যাবে না।
শীর্ষবিন্দু রঙ ব্যবহার করে দ্বিপক্ষীয় গ্রাফ পরীক্ষা করা সম্ভব। যখন একটি শীর্ষবিন্দু একই সেটে থাকে, তখন তার রঙ একই থাকে, অন্য সেটের জন্য, রঙ পরিবর্তন হবে।
ইনপুট এবং আউটপুট
Input: The adjacency matrix. 0 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 Output: The graph is bipartite.
অ্যালগরিদম
isBipartite(source)
ইনপুট - উৎস শীর্ষবিন্দু।
আউটপু t :গ্রাফটি দ্বিপক্ষীয় হলে সত্য৷
Begin define an empty queue qu, and a color list coloArray initially any node is not colored with any color color the source vertex as color red add source in the qu when qu is not empty, do remove item from the qu and take in u if there is any self-loop, then return false for all vertices v, which is connected with u, do if v has no color, then if colorArray[u] = red, then colorArray[v] := blue else if colorArray[u] = blue, then colorArray[v] := red add v into the queue if colorArray[v] = colorArray[u], then return false done done return true End
উদাহরণ
#include<iostream>
#include<string>
#include<queue>
#define NODE 6
using namespace std;
/*int graph[NODE][NODE] = {
{0, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0},
{1, 0, 0, 1, 0, 1},
{1, 1, 1, 0, 1, 1},
{0, 1, 0, 1, 0, 1},
{0, 0, 1, 1, 1, 0}
}; */
int graph[NODE][NODE] = {
{0, 1, 0, 0, 0, 1},
{1, 0, 1, 0, 0, 0},
{0, 1, 0, 1, 0, 0},
{0, 0, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 1},
{1, 0, 0, 0, 1, 0}
};
bool isBipartite(int source) {
queue<int> qu;
string colorArray[NODE];
for(int i = 0; i< NODE; i++)
colorArray[i] = "No Color"; //initially no color is set for all vertices
colorArray[source] = "Red"; //assign red with the source vertex
qu.push(source); //add source into the queue.
while(!qu.empty()) {
int u = qu.front();
qu.pop();
if(graph[u][u] == 1) //there is a self loop
return false;
for(int v = 0; v < NODE; v++) {
if(graph[u][v] != 0 && colorArray[v] == "No Color") {
if(colorArray[u] == "Red") //assign adjacent list with alternate color
colorArray[v] = "Blue";
else if(colorArray[u] == "Blue")
colorArray[v] = "Red";
qu.push(v); //new adjacent node added to queue
} else if(graph[u][v] != 0 && colorArray[v] == colorArray[u]) {
return false; //when u and adjacent are of same color.
}
}
}
return true;
}
int main() {
bool check;
check = isBipartite(0);
if(check)
cout << "The graph is bipartite." << endl;
else
cout << "The graph is not bipartite." << endl;
} আউটপুট
The graph is bipartite.
