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;
}

All 3 Replies

Oh! sorry! the code doesn't have that problem and it is a correct kruskal's algorithm implementation :)

So do you still have a problem about the code?

So do you still have a problem about the code?

no! thanks :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.