একটি গ্রাফ Bipartite হবে যদি গ্রাফটির
ভার্টেক্স এর সেট V কে দুটি পৃথক disjoint set V1 and V2 তে ভাগ করা যায় যেখানে প্রত্যেক edge V1 and V2 এর সাথে কানেক্টেড থাকবে।
Bipartite গ্রাফ চেনার সহজ উপায় হল কালার করা। নোডগুলোকে সর্বোচ্চ দুটি কালার দিয়ে কালার
করা যাবে যেন পাশাপাশি কানেক্টেড দুটি নোডের কালার একই না হয়।
এখন Step by Step কোড এনালাইসিস করা যাক।
প্রথমে ইনপুট নিবো নোড এবং এজ নম্বর। তারপর গ্রাফ এর কোন নোড থেকে কোন নোড
কানেক্টেড সেটা ইনপুট নিবো। এজন্য edge array হবে 2d vector
২য় চিত্রটির ইনপুট নিলে এমনভাবে নিব
3 2
0 1 //edges[0][0]=1
0 2 //edges[0][0]=2
কোডঃ
cout<<"Enter
Total Nodes And Edges="<<endl;
cin>>tn>>e;
for(i=1;i<=e;i++)
{
cin>>u>>v;
edges[u].push_back(v);
}
এরপর bipartite(0) function এ প্রথম নোড 0 প্যারামিটার হিসেবে সেন্ড করব। যদি true রিটার্ন করে তাহলে bipartite নাহলে not bipartite.
Bipartite function এর কোড নিচে এনালাইসিস করা হল।
প্রথমে কিউ নিয়ে কিউ এর মধ্যে প্রথম নোড 0 পুশ
করে রাখব। color array এর সব ভ্যালু -1 করে রাখব কারন এখনো কালার করা হয় নি কোন নোড কে। এর সাথে visited array এর সব ভ্যালু 0 করে রাখব কারন কোন নোড এ
ভিজিটেড হয় নি।color এর মান 0 and 1 এর মধ্যে রাখার জন্য আমরা color[0]=1 করে রাখতে পারি।
int bipartite(int s)
{
int j,k,fr;
q.push(s);
memset(color,-1,sizeof color);
for(j=0;j<tn;j++)
{
visited[j]=0;
}
color[s]=1;
}
}
এবার আমরা কিউ যতক্ষন না খালি হচ্ছে ততক্ষন পর্যন্ত কিউ থেকে ফ্রন্ট নোড এর
ভ্যালু নিবো এবং সেই নোড এবং তার সাথে কানেক্টেড নোড গুলোকে ভিজিটেড ও কালার করব।
while(!q.empty())
{
fr=q.front();
for(k=0;k<edges[fr].size();k++)
{
if(visited[edges[fr][k]]==0
&& color[edges[fr][k]]==-1)
{
q.push(edges[fr][k]);
visited[edges[fr][k]]=1;
color[edges[fr][k]]=1-color[fr];
}
}
প্রথমে কিউ এর ফ্রন্ট হবে 0. এখন লুপ এর প্রথমে edge[0][0] নিয়ে
কাজ করব। তাহলে edge[0][0]=1 পুশ হবে কিউ
এ প্রথমে। এরপর edge[0][0]=1 তাই visited[edge[0][0]]
= visited[1]=0 (নট ভিজিটেড) এবং color[edge[0][0]]=color[1]=-1
(নট কালারড) তাই visited[1]=1 করে দিব এবং color[1]=1-color[0]=1-1=0 করে দিব । 1 থেকে
বিয়োগ করা হয়েছে কারন আমাদের দুটি কালার এর মধ্যেই রাখতে হবে প্রথম নোড 0 এর জন্য color[0]=1
করেছিলাম
তাই color[1] এর জন্য এর বিপরীত টাই করলাম 1 বিয়োগ করে।
এবার লুপ ঘুরে edge[0][1] এ আসবে।
তাই visited[edge[0][1]]=1 করে দিব এবং color[2]=0
হবে। এবার ২য় চিত্রে যেহেতু 0 এর সাথে আর কোন কানেক্টেড নোড নাই তাই লুপ শেষ হয়ে যাবে। এরপর
0 নোড এর সাথে 1 এবং 2 এর কালার ম্যাচ করে কি
না চেক করবে। যদি ম্যাচ করে তাহলে false রিটার্ন করবে।
for(k=0;k<edges[fr].size();k++)
{
if(color[edges[fr][k]]==color[fr])
{
return false;
}
}
q.pop();
}
return true;
}
color[edge[0][0]]=color[1]=0 but color[0]=1
color[edge[0][1]]=color[2]=0 but color[0]=1
যেহেতু ম্যাচ করে নি তাই কোন false রিটার্ন করবে না এবং নোড
0 পপ হবে। এবার কিউ এ যেহেতু 1 পুশ হয়ে আছে তাই ফ্রন্ট এ আবার 1 আসবে এবং যেহেতু 1 এর
সাথে আর কোন কিছু কানেক্টেড নাই তাই 1 ও পপ হবে এবং কিউ খালি
হয়ে যাবে। শেষ এ রিটার্ন true হবে। তাই ২য় গ্রাফটি bipartite.
নিচে পুরো সোর্স কোড এবং এর সাথে রিলেটেড প্রব্লেম এর লিঙ্ক দেয়া হল।
ফুল কোডঃ
#include <bits/stdc++.h>
using namespace std;
vector<int>edges[100];
queue<int>q;
vector<int>item;
int level[100],color[100],visited[100],tn;
int bipartite(int s)
{
int j,k,fr;
q.push(s);
memset(color,-1,sizeof color);
using namespace std;
vector<int>edges[100];
queue<int>q;
vector<int>item;
int level[100],color[100],visited[100],tn;
int bipartite(int s)
{
int j,k,fr;
q.push(s);
memset(color,-1,sizeof color);
color[s]=1;
for(j=0;j<tn;j++)
{
visited[j]=0;
}
while(!q.empty())
{
fr=q.front();
for(k=0;k<edges[fr].size();k++)
{
if(visited[edges[fr][k]]==0 && color[edges[fr][k]]==-1)
{
q.push(edges[fr][k]);
visited[edges[fr][k]]=1;
color[edges[fr][k]]=1-color[fr];
}
}
for(k=0;k<edges[fr].size();k++)
{
if(color[edges[fr][k]]==color[fr])
{
return false;
}
}
q.pop();
}
return true;
}
int main()
{
int i,e,p,n,u,v,f,m;
cout<<"Enter Total Nodes And Edges="<<endl;
cin>>tn>>e;
for(i=1;i<=e;i++)
{
cin>>u>>v;
edges[u].push_back(v);
}
cout<<endl;
if(bipartite(0))
{
cout<<"Input Graph Is Bipartite"<<endl;
}
else
{
cout<<"Input Graph Is Not Bipartite"<<endl;
}
return 0;
}
{
visited[j]=0;
}
while(!q.empty())
{
fr=q.front();
for(k=0;k<edges[fr].size();k++)
{
if(visited[edges[fr][k]]==0 && color[edges[fr][k]]==-1)
{
q.push(edges[fr][k]);
visited[edges[fr][k]]=1;
color[edges[fr][k]]=1-color[fr];
}
}
for(k=0;k<edges[fr].size();k++)
{
if(color[edges[fr][k]]==color[fr])
{
return false;
}
}
q.pop();
}
return true;
}
int main()
{
int i,e,p,n,u,v,f,m;
cout<<"Enter Total Nodes And Edges="<<endl;
cin>>tn>>e;
for(i=1;i<=e;i++)
{
cin>>u>>v;
edges[u].push_back(v);
}
cout<<endl;
if(bipartite(0))
{
cout<<"Input Graph Is Bipartite"<<endl;
}
else
{
cout<<"Input Graph Is Not Bipartite"<<endl;
}
return 0;
}
Related Problems
ধন্যবাদ ভাইয়া।
ReplyDeleteWelcome
Delete