Difference between revisions of "Kruskal Algorithm Implementation in C/C++"

Revision as of 21:48, 13 December 2013

<syntaxhighlight lang="C">

1. 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>