Hello everyone :) I have a problem with Kraskal's algorithm. :sad: How it is possible to choose the node I want to start with to build minimmum spanning tree?
Thank you for ansvering :)
//implemented using sets concept
#include<iostream.h>
class kruskal
{
private:
int n;
int graph[10][10];
int tree[10][10];
int noe;
int edges[100][4];
int sets[100][10];
int top[100];
public:
void read_graph();
void initialize_span_t();
void sort_edges();
void algorithm();
int find_node(int );
void print_min_span_t();
};
void kruskal::read_graph()
{
cout<<”Enter the no. of nodes in the graph ::”;
cin>>n;
cout<<”Enter the adjacency matrix of the graph ::\n”;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>graph[i][j];
}
void kruskal::sort_edges()
{
int i,j;
/******* Initialize the edges *************/
noe=0;
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j++)
{
if(graph[i][j]!=0)
{
noe++;
edges[noe][1]=i;
edges[noe][2]=j;
edges[noe][3]=graph[i][j];
}
}
}
/*********** Sort the edges **************/
for(i=1;i<=noe;i++)
{
for(j=i;j<=noe-1;j++)
{
if(edges[j][3]>edges[j+1][3])
{
int t=edges[j][1];
edges[j][1]=edges[j+1][1];
edges[j+1][1]=t;
t=edges[j][2];
edges[j][2]=edges[j+1][2];
edges[j+1][2]=t;
t=edges[j][3];
edges[j][3]=edges[j+1][3];
edges[j+1][3]=t;
}
}
}
/*********** Print the edges **************/
cout<<endl;
for(i=1;i<=noe;i++)
cout<<edges[i][1]<<’\t’<<edges[i][2]<<’\t’<<edges[i][3]<<endl;
}
void kruskal::initialize_span_t()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
tree[i][j]=0;
}
void kruskal::algorithm()
{
// ->make a set for each node
for(int i=1;i<=n;i++)
{
sets[i][1]=i;
top[i]=1;
}
for(i=1;i<=noe;i++)
{
int p1=find_node(edges[i][1]);
int p2=find_node(edges[i][2]);
cout<<p1<<”\t”<<p2<<endl;
if(p1!=p2)
{
tree[edges[i][1]][edges[i][2]]=edges[i][3];
tree[edges[i][2]][edges[i][1]]=edges[i][3];
// Mix the two sets
for(int j=1;j<=top[p2];j++)
{
top[p1]++;
sets[p1][top[p1]]=sets[p2][j];
}
top[p2]=0;
}
}
}
int kruskal::find_node(int n)
{
for(int i=1;i<=noe;i++)
{
for(int j=1;j<=top[i];j++)
{
if(n==sets[i][j])
return i;
}
}
return -1;
}
void kruskal:: print_min_span_t()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<tree[i][j]<<’\t’;
cout<<endl;
}
}
int main()
{
kruskal obj;
obj.read_graph();
obj.sort_edges();
obj.initialize_span_t();
obj.algorithm();
obj.print_min_span_t();
return 0;
}