Hello every one!
i write an implementation for kruskal's algorithm but i think it doesn't work properly!
The final tree has loop! this is my problem. Can you tell me how i can solve this problem?
here is the code:
#include <stdio.h>
#include <conio.h>
#include <iostream>
using namespace std;
int kruskal_mst(int set[],struct krus edge[],int n,int m);
void sort(struct krus ed[],int m);
struct krus{
int v1;
int v2;
int weight;
};
int main()
{
system("cls");
int n,m;
cout<<"Input Num Vertex : ";
cin>>n;
int set[n];
for (int i=0;i<n;i++)
set[i]=i;
cout<<"Input Num Yal : ";
cin>>m;
struct krus edge[m];
for (int i=0;i<m;i++)
{
cout<<"Num V1 : "; cin>>edge[i].v1;
cout<<"Num V2 : "; cin>>edge[i].v2;
cout<<"Weight : "; cin>>edge[i].weight;
}
sort(edge,m);
for (int i=0;i<m;i++)
cout<<"("<<edge[i].v1<<","<<edge[i].v2<<") => W :"<<edge[i].weight<<"\n";
cout<<"Weight Is : "<<kruskal_mst(set,edge,n,m);
getch();
}
//***********************************************
void sort(struct krus ed[],int m)
{
struct krus temp;
for (int i=0;i<m;i++)
for (int j=i+1;j<m;j++)
if (ed[j].weight<ed[i].weight)
{
temp=ed[i];
ed[i]=ed[j];
ed[j]=temp;
}
}
//**************************************************
int kruskal_mst(int set[],struct krus edge[],int n,int m)
{
int g=0;
int fe=0;
int p=0;
struct krus e;
while (fe<n-1 && g<m)
{
e=edge[g++];
if (set[e.v1] != set[e.v2])
{
p+=e.weight;
int k=set[e.v1];
for (int i=0;i<n;i++)
if (set[i]==k)
set[i]=set[e.v2];
fe++;
}
}
if(fe==n-1) return p;
else
return -1;
}