C++ Code for Kruskal's Algorithm with explanation

C++ Code for Kruskal's Algorithm with explanation 


Example: Node numbers are 1 2 3 4 5
Weight is 3 between 1 and 3. 
Weight is 4 between 1 and 2.
Weight is 9 between 2 and 3.
Weight is 1 between 2 and 4.
Weight is 7 between 5 and 3.
Weight is 2 between 4 and 5.


At first sort the edge list according to weight.
Weight is 1 between 2 and 4.
Weight is 2 between 4 and 5.
Weight is 3 between 1 and 3. 
Weight is 4 between 1 and 2.
Weight is 7 between 5 and 3.
Weight is 9 between 2 and 3.

Take array for node's parent. And initialize parent value equal to node value.
parent[1]=1
parent[2]=2
parent[3]=3
parent[4]=4
parent[5]=5

Select the most small weighted edge. Here it is : Weight is 1 between 2 and 4.


check the parents of two nodes are equal or not. If parents are not equal, Then store it in answer container. And set 2nd's node parent is 1st node's parent.

parent of node 2 is 1.
parent of node 4 is 2.
parents are not equal. put this pair in answer container.
And set node 4's is 2. i.e parent[4]=2; 


Then take next sorted edge which is : Weight is 2 between 4 and 5.


Here, parent[4]=2 and parent[5]=5. parents are not equal. Then store it in answer container.
Set, parent[5]=2.


Then take next sorted edge which is : Weight is 3 between 1 and 3. 


Here, parent[1]=1 and parent[3]=3. parents are not equal. Then store it in answer container.
Set, parent[3]=1.

Then take next sorted edge which is : Weight is 4 between 1 and 2.

Here, parent[1]=1 and parent[2]=2. parents are not equal. Then store it in answer container.
Set, parent[2]=1.
Then take next sorted edge which is :  Weight is 7 between 5 and 3.
Here, parent[3]=1. parent[5]=parent[2]=1. parents are equal. So, it is not our answer. It creates circle. So, ignore it.


Then take next sorted edge which is : Weight is 9 between 2 and 3.

Here, parent[3]=1. parent[2]=1. parents are equal. So, it is not our answer. It creates circle. So, ignore it.

Traversing is completed. 


Code: 


#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef pair<int,int> Pair_Int_Int;
typedef pair<int,Pair_Int_Int> Pair_Int_Pair_Int_Int;
vector<Pair_Int_Pair_Int_Int> myvec,result;
int *parent;

bool mysort(Pair_Int_Pair_Int_Int p1, Pair_Int_Pair_Int_Int p2)
{
return p1.first<p2.first;
}

int getParent(int x)
{
int y;
if(parent[x]==x)
return x;
y=parent[x];
parent[y]=getParent(y);
return parent[y];
}

int main() 
{
freopen("file.txt","r",stdin);
int node,edge,i,u,v,w,parent_u,parent_v;
Pair_Int_Int p1;
Pair_Int_Pair_Int_Int p2;
cin>>node>>edge;
for(i=0;i<edge;i++)
{
cin>>u>>v>>w;
p1=pair<int,int>(u,v);
p2=pair<int,Pair_Int_Int>(w,p1);
myvec.push_back(p2);
}
sort(myvec.begin(),myvec.end(),mysort);
parent= new int[node+1];
for(i=1;i<=node;i++)
parent[i]=i;
for(i=0;i<edge;i++)
{
p2=myvec[i];
w=p2.first;
p1=p2.second;
u=p1.first;
v=p1.second;
parent[u]=getParent(u);
parent[v]=getParent(v);
if(parent[u]!=parent[v])
{
result.push_back(p2);
parent[parent[v]]=parent[u];
}
}
delete[] parent;
for(i=0;i<result.size();i++)
{
p2=myvec[i];
p1=p2.second;
cout<<p1.first<<" "<<p1.second<<endl;
}
return 0;
}

Input:

5
6
1 3 3
1 2 4
2 3 9
2 4 1
4 5 2
3 5 7

Output:

2 4
4 5
1 3
1 2



Comments

Post a Comment

Popular posts from this blog

uva 679 - Dropping Balls Solution

uva 679 - Dropping Balls Solution Algorithm: 1. convert (position-1)  to binary and store it to a string. 2. make the binary string length equal to the (depth-1) by adding zero(0) at start of the string. 3. reverse the binary string. 4. convert binary string to integer + power(2,depth-1). Example: depth=7; position=4; covert 4-1= 3 to binary. binary string is 11. make the string length 7-1=6 by adding 0. Updated string 000011. reverse the binary string and string is now 110000 convert binary string(110000) to integer. value is 48. calculate power_value=pow(2,7-1)=pow(2,6)=64. Answer is = 48 + 64=112. Code in C++: #include<iostream> #include<string> #include<algorithm> using namespace std; string convertDecimalToBinary(int num){ string result; while(num!=0){ if(num%2==1) result.insert(0,1,'1'); else result.insert(0,1,'0'); num=num/2; } return result; } int convertBinaryToDecimal(string &n...
Read more

uva 481 - What Goes Up Solution

uva 481 - What Goes Up Solution #include<iostream> #include<vector> using namespace std; void binary_search(int *arr, int search_value, int start, int end, int &index){ if (start == end){ index = start; return; } int mid = (start + end) / 2; if (arr[mid] == search_value){ index = mid; return; } else if (arr[mid + 1] == search_value){ index = mid + 1; return; } else if (arr[mid]<search_value && arr[mid + 1]>search_value){ index = mid + 1; return; } else if (arr[mid] > search_value){ binary_search(arr, search_value, start, mid, index); } else{ binary_search(arr, search_value, mid + 1, end, index); } } void calculate_lis(vector<int>&arr,vector<int>&result){ int *temp, i, max = 0, j, index, n = arr.size(), *res; temp = new int[n]; res = new int[n]; temp[0] = 0; for (i = 1; i < n; i++){ if (arr[temp[max]] < arr[i]){ res[i] = temp[max]; max++; ...
Read more

uva-10077 Solution --- The Stern-Brocot Number System

#include<iostream> using namespace std; int main(){ int input_num,input_den,left_num,left_den,right_num,right_den,cur_num,cur_den; while(cin>>input_num>>input_den){ if(input_num==1 && input_den==1) break; left_num=0; left_den=1; right_num=1; right_den=0; cur_num=cur_den=1; while(true){ if(cur_num== input_num && cur_den==input_den) break; if(cur_num*input_den < cur_den*input_num){ cout<<"R"; left_num=cur_num; left_den=cur_den; cur_num+=right_num; cur_den+=right_den; }else{ cout<<"L"; right_num=cur_num; right_den=cur_den; cur_num+=left_num; cur_den+=left_den; } } cout<<endl; } return 0; }
Read more