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

Recommended Answers

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.