ক্রুসকাল অ্যালগরিদম

Spanning Tree হল এমন একটি  সাবগ্রাফ যেখানে মূলগ্রাফের সবগুলো নোড থাকে এবং n-1 সংখ্যক এজ থাকে কিন্তু কোন সাইকেল থাকে না। n যেখানে হল নোডসংখ্যা।একটা গ্রাফের অনেকগুলো Spanning Tree হতে পারে,কিন্তু তাদের মধ্যে যে Spanning Tree এর এজগুলোর কস্ট/ওয়েট এর যোগফল সবচেয়ে কম সেটিই হল  Minimum Spanning Tree(MST)/Minimum Weight Spanning Tree.

Minimum Spanning Tree(MST) বের করার দুইটা অ্যালগরিদম আছে, ক্রুসকাল এবং প্রিমস অ্যালগরিদম।এখানে আমরা দেখব ক্রুসকাল অ্যালগরিদম দিয়ে কিভাবে Minimum Spanning Tree(MST) বের করা যায়। এ সম্পর্কে বিশদভাবে জানার জন্য শাফায়েত ভাইয়ের ব্লগের বিকল্প নাই।

Kruskal Algorithm(Minimum Spanning Tree):

প্রথমে সবগুলো এজ কে তাদের কস্ট/ওয়েট অনুযায়ী Non-decreasing অর্ডারে সর্ট করে ফেলতে হবে।তারপর সবচেয়ে কম কস্ট/ওয়েটের এজগুলো নেয়ে শুরু করতে হবে তবে কোন এজ নেয়ার সময় অবশ্যই চেক করতে হবে সংশ্লিষ্ট নোড দুটির মধ্যে আগে থেকেই কোন পথ/এজ আছে কি না। আগে থেকেই এজ থাকলে সেটি আর নেয়া যাবে না ,কারণ নিলেই সাইকেল ক্রিয়েট হয়ে যাবে।কোন দুটি নোডের মধ্যে আগে থেকেই এজ/পথ আছে কি না সেটা ডিসজয়েন্ট সেট এর কনসেপ্ট দিয়ে চেক করা যেতে পারে। এভাবে এজ নিতে নিতে n-1 সংখ্যক এজ নেয়া হলেই হলেই প্রোগ্রাম টারমিনেট করে দিতে হবে।

Sample Code:

	#include<bits/stdc++.h>
	using namespace std;
	struct Edge{
	int u,v,w;
	bool operator<(const Edge& p) const
	{
	return w < p.w;
	}
	};
	vector<Edge>e;
	int parent[100005];
	int find(int r)
	{
	if(parent[r] == r) return r;
	else return find(parent[r]);
	}
	int mst(int n){
	sort(e.begin(),e.end());
	for(int i=0;i<=n;i++)parent[i]=i;
	int cnt=0,s=0;
	for(int i=0;i<(int)e.size();i++){
	int u=find(e[i].u);
	int v=find(e[i].v);
	if(u!=v){
	parent[u]=v;
	cnt++;
	s+=e[i].w;
	if(cnt==n-1)break;
	}
	}
	return s;
	}
	int main()
	{
	int N,E,i,j,k,l,u,v,w;
	scanf("%d%d",&N,&E);
	for(i=0;i<E;i++){
	scanf("%d%d%d",&u,&v,&w);
	Edge get;
	get.u=u;
	get.v=v;
	get.w=w;
	e.push_back(get);
	}
	cout<<mst(N)<<endl;;
	return 0;
	}

view raw Kruskal.cpp hosted with ❤ by GitHub

Maximum Spanning Tree:

এক্ষেত্রে এজ গুলোকে শুধু Non-increasing অর্ডারে সর্ট করতে হবে।বাকি সবকিছুই  Minimum Spanning Tree এর মতই। 

Partial 'Minimum' Spanning Tree:

এক্ষেত্রে কিছু ফিক্সড এজ দেয়া থাকে যেগুলো নিতেই হবে।তাই এটা আসলে MST থাকে না।সেই জন্যই ক্যাপশনে Minimum কে quotes এর মধ্যে রাখা হয়েছে😏। এর সল্যুশন অ্যাপ্রোচটা খুবই সিম্পল।প্রথমে ফিক্সড এজ গুলো নিয়ে নিতে হবে।তারপর বাকি গুলোর উপর MST রান করলেই হয়ে যাবে😝।ধরি N হল গ্রাফে নোড সংখ্যা,এবং F সংখ্যক ফিক্সড এজ দেয়া আছে। তাহলে Partial 'Minimum' Spanning Tree পেতে হলে প্রথমে ফিক্সড এজ গুলো কে নেয়ার পর বাকি গুলোর উপর MST রান করে  (N-1)-F  সংখ্যক এজ পেলেই প্রোগ্রাম টারমিনেট করে দিতে হবে।

Sample code:

	#include<bits/stdc++.h>
	using namespace std;
	struct Edge{
	int u,v,w;
	bool operator<(const Edge& p) const
	{
	return w < p.w;
	}
	};
	vector<Edge>e;
	int parent[100005];
	int find(int r)
	{
	if(parent[r] == r) return r;
	else return find(parent[r]);
	}
	int mst(int n,int fixed){
	sort(e.begin(),e.end());
	for(int i=0;i<=n;i++)parent[i]=i;
	int cnt=0,s=0;
	for(int i=0;i<(int)e.size();i++){
	int u=find(e[i].u);
	int v=find(e[i].v);
	if(u!=v){
	parent[u]=v;
	cnt++;
	s+=e[i].w;
	if(cnt==n-1-fixed)break;
	}
	}
	return s;
	}
	map<int,int>mark;
	int main()
	{
	int N,E,i,j,k,l,u,v,w,fixed,fixed_cost=0;
	scanf("%d%d%d",&N,&E,&fixed);
	for(i=0;i<fixed;i++){
	scanf("%d%d%d",&u,&v,&w);
	fixed_cost+=w;
	mark[u]=v;
	mark[v]=u;
	}
	for(i=0;i<E;i++){
	scanf("%d%d%d",&u,&v,&w);
	if(mark[u]==v or mark[v]==u)continue;
	Edge get;
	get.u=u;
	get.v=v;
	get.w=w;
	e.push_back(get);
	}
	cout<<mst(N,fixed)+fixed_cost<<endl;;
	return 0;
	}
	/*
	4 4 1
	1 2 25
	1 2 25
	1 4 10
	4 3 17
	3 2 13
	*/

view raw Partial MST.cpp hosted with ❤ by GitHub

Second Best Spanning Tree:

এক্ষেত্রে রান MST করে  MST  এর সবগুলো এজ সেভ করে রাখতে হবে। তারপর MST  এর প্রতিটা এজ একবার করে বাদ দিয়ে নতুন করে MST  রান করতে হবে।এভাবে মূল MST  এর প্রতিটা এজ একবার করে বাদ দিয়ে নতুন করে MST  রান করে যে MST এর ভাল্যু সবচেয়ে কম হবে সেটাই হল Second Best Spanning Tree। কোন একটি এজকে বাদ দেয়ার জন্য ঐ এজকে একটা Infinite ভ্যাল্যু অ্যাসাইন করে দিলেই হবে।

Sample Code:

	#include<bits/stdc++.h>
	using namespace std;
	#define inf 0x3f3f3f3f
	struct Edge{
	int u,v,w;
	bool operator<(const Edge& p) const
	{
	return w < p.w;
	}
	};
	vector<Edge>sTree;
	int parent[100005];
	int find(int r)
	{
	if(parent[r] == r) return r;
	else return find(parent[r]);
	}
	int mst(int n,vector<Edge> e){
	sort(e.begin(),e.end());
	for(int i=0;i<=n;i++)parent[i]=i;
	int cnt=0,s=0;
	for(int i=0;i<(int)e.size();i++){
	int u=find(e[i].u);
	int v=find(e[i].v);
	if(u!=v){
	parent[u]=v;
	cnt++;
	s+=e[i].w;
	Edge get;
	get.u=e[i].u;
	get.v=e[i].v;
	get.w=e[i].w;
	sTree.push_back(get);
	if(cnt==n-1)break;
	}
	}
	return s;
	}
	int main()
	{
	int N,E,i,j,k,l,u,v,w;
	vector<Edge>e;
	scanf("%d%d",&N,&E);
	for(i=0;i<E;i++){
	scanf("%d%d%d",&u,&v,&w);
	Edge get;
	get.u=u;
	get.v=v;
	get.w=w;
	e.push_back(get);
	}
	cout<<"Minimum spanning tree cost="<<mst(N,e)<<endl;
	int sz=sTree.size();
	int mn=inf;
	for(i=0;i<sz;i++){
	vector<Edge>tmp=e;
	int x=sTree[i].u; int y=sTree[i].v; int z=sTree[i].w;
	for(j=0;j<E;j++){
	int a=tmp[j].u;int b=tmp[j].v;
	if((x==a&&y==b)||(x==b&&y==a))tmp[j].w=inf;
	}
	int gg=mst(N,tmp);
	mn=min(mn,gg);
	}
	cout<<"Second best Minimum spanning tree cost="<<mn<<endl;
	return 0;
	}
	/*
	5 8
	1 2 9
	1 3 75
	2 3 95
	2 5 42
	2 4 19
	3 4 51
	5 4 31
	3 5 66
	*/

view raw Second Best MST.cpp hosted with ❤ by GitHub

Minimum Spanning Forest:

এক্ষেত্রে সব গুলো নোড কিছু সংখ্যক এজ দিয়ে ভিজিটেড হয়ে গেলেই প্রোগ্রাম টারমিনেট করে দিব,যদি Spanning Tree ফর্ম না হয় তবুও।Spanning Tree ফর্ম না করেই কিছু সংখ্যক এজ দিয়েই সব গুলো নোড ভিজিট করা পসিবল হবে যদি গ্রাফে একটা Spanning 'Forest' থাকে।সাধারণত কত সংখ্যক এজ(Number of Components)  দিয়ে সব গুলো নোড ভিজিট করতে হবে তা বলে দেয়া থাকে,তাই তত সংখ্যক এজ নেয়া হয়ে গেলেই প্রোগ্রাম টারমিনেট করে দিতে হবে।

Sample Code:

	#include<bits/stdc++.h>
	using namespace std;
	struct Edge{
	int u,v,w;
	bool operator<(const Edge& p) const
	{
	return w < p.w;
	}
	};
	vector<Edge>e;
	int parent[100005];
	int find(int r)
	{
	if(parent[r] == r) return r;
	else return find(parent[r]);
	}
	int mst(int n,int number_of_component){
	sort(e.begin(),e.end());
	for(int i=0;i<=n;i++)parent[i]=i;
	int cnt=0,s=0;
	for(int i=0;i<(int)e.size();i++){
	int u=find(e[i].u);
	int v=find(e[i].v);
	if(u!=v){
	parent[u]=v;
	cnt++;
	s+=e[i].w;
	if(cnt==number_of_component)break;
	}
	}
	return s;
	}
	int main()
	{
	int N,E,i,j,k,l,u,v,w,number_of_component;
	scanf("%d%d%d",&N,&E,&number_of_component);
	for(i=0;i<E;i++){
	scanf("%d%d%d",&u,&v,&w);
	Edge get;
	get.u=u;
	get.v=v;
	get.w=w;
	e.push_back(get);
	}
	cout<<mst(N,number_of_component)<<endl;;
	return 0;
	}
	/*
	4 4 2
	1 2 25
	2 3 13
	3 4 17
	4 1 10
	*

view raw Minimum Spanning Forest.cpp hosted with ❤ by GitHub

References:

→http://www.shafaetsplanet.com/planetcoding/?p=825

→Competitive Programming By Steven & Felix Halim

→Competitive Programmer's Handbook By Antti Laaksonen