Kruskal Algorithm Implementation in C/C++ - Revision history

Arjun Suresh at 16:37, 22 February 2014

2014-02-22T16:37:58Z

Arjun Suresh: Arjun Suresh moved page Kruskal Algorithm Implementation in C\C++ to Kruskal Algorithm Implementation in C/C++

2014-01-28T21:01:01Z

Arjun Suresh moved page Kruskal Algorithm Implementation in C\C++ to Kruskal Algorithm Implementation in C/C++

Arjun Suresh at 22:30, 18 December 2013

2013-12-18T22:30:28Z

Arjun Suresh at 21:49, 13 December 2013

2013-12-13T21:49:19Z

Arjun Suresh: Created page with " #include using namespace std; int vi=0; char vertex[20]; struct nod { char x; struct nod rep; struct nod next; }; ..."

2013-12-13T21:48:45Z

Created page with "<syntaxhighlight lang="C"> #include<iostream> using namespace std; int vi=0; char vertex[20]; struct nod { char x; struct nod *rep; struct nod *next; }; ..."

New page

<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]]

@@ Line 1: / Line 1: @@
-<syntaxhighlight lang="C">
+<syntaxhighlight lang="C" name="kruskal">
 #include<iostream>
 using namespace std;

← Older revision	Revision as of 21:01, 28 January 2014
(No difference)