View source for Kruskal Algorithm Implementation in C/C++ ← Kruskal Algorithm Implementation in C/C++

<syntaxhighlight lang="C">
#include<iostream>
using namespace std;

int vi=0;
char vertex[20];

struct nod
 {
     char x;
     struct nod *rep;
     struct nod *next;
 };

struct list
{
    
    nod node; 
    struct nod *head;
    struct nod *tail;
};

class dsets
{
    list *s[20];
    int nlist;
public:
    dsets()
	{
	    nlist = 0;
	}
    void makeset(char a)
	{
	    s[nlist] = new list;
	    s[nlist]->node.x = a;
	    s[nlist]->head = s[nlist]->tail = s[nlist]->node.rep = &(s[nlist]->node);
	    s[nlist++]->node.next = NULL;
	}
	    
    
    list* findset(char a)
	{
	    int i;
	    nod *trav;
	    for(i = 0; i < nlist; i++)
	    {
		trav = s[i]->head;
		while(trav != NULL)
		{
		    if(trav->x == a)
			return s[i];
		    trav = trav->next;
		}
	    }
	    return NULL;
	}
    list* unin(list *a,list *b)
	{
	    nod* trav = b->head;
	    a->tail->next = b->head;   
	    a->tail = b->tail;	    
	    while(trav != NULL)
	    {
		trav->rep = a->head;
		trav = trav->next;
	    }
	    
	    b->head = b->tail = NULL;
	    return a;
	}
    void disp()
	{
	    nod *trav;
	    for(int i = 0; i < nlist; i++)
	    {
		trav = s[i]->head;
		while(trav != NULL)
		{
		    cout << trav->x << "\t";
		    trav = trav->next;
		}
		cout << endl;
	    }
	}
};
int main()
{
    char b, a, start;
    int forest[20];
    char edge [20][2];
    int cost[20];
    int ei = 0;
    dsets disset;
    int c, d, i, u, fi = 0, j, t;
	cout << "Enter the edges and cost\n0 to stop:\n ";
	while(1)
	{
		cin >> a;
		if(a == '0')
		    break;
		edge[ei][0] = a;
	       
		cin >> b;
		edge[ei][1] = b;
		cin >> cost[ei++];
		c = 0, d = 0;
		for(i = 0; i < vi; i++)
		{
		    if(a == vertex[i])
		    {
			c++;
			
		    }
		    if(b == vertex[i])
		    {
			d++;
		    }
		}
		if(c == 0)
		{
		    vertex[vi++] = a;
		    
		}
		if(d == 0)
		{
		    vertex[vi++] = b;
		    
		}
	}
	for(i = 0;  < ei; i++)
	    for(j = 0; j < ei-i-1; j++)
		if(cost[j] > cost[j+1])
		{
		    t = cost[j];
		    cost[j] = cost[j+1];
		    cost[j+1] = t;
		    for(int k = 0; k < 2; k++)
		    {
			t = edge[j][k];
			edge[j][k] = edge[j+1][k];
			edge[j+1][k] = t;
		    }
		}
	for(i = 0; i < vi; i++)
	    disset.makeset(vertex[i]);
	for(i = 0; i < ei; i++)
	{
	    
	    if(disset.findset(edge[i][0]) != disset.findset(edge[i][1]))
	    {
		forest[fi++] = i;
		disset.unin(disset.findset(edge[i][0]),disset.findset(edge[i][1]));
	    }
	}
	cout << "The minimum spanning tree of the entered graph is the one through the following edges\n";
	for(i = 0; i < fi; i++)
	{
	    cout << edge[forest[i]][0] << "\t"<<edge[forest[i]][1] << endl;
	}
}


</syntaxhighlight>



{{Template:FB}}


<disqus/>



[[Category:Graphs]]