Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/forumdisplay.php?f=100)
-   -   help!! kruskals algorithm using linked list (http://www.go4expert.com/showthread.php?t=21754)

hanann 14Apr2010 11:00
help!! kruskals algorithm using linked list
 
i have big problem in my code

my teacher asked us to write C++ code to solve kruskal algorithm i wrote the code using data structure Tree but she aske me to write it again using linked list

i don't know how?
i implement all things in tree

so i think i need i new one can anyone help me in linked list plz!!!!

virxen 15Apr2010 00:12
Re: help!! kruskals algorithm using linked list
 
and where is your code with the tree solution?

hanann 15Apr2010 05:11
Re: help!! kruskals algorithm using linked list
 
Code:
#include<iostream.h>
class kruskal
{
private:
int n; //no of nodes
int noe; //no edges in the graph
int graph_edge[100][4];

int tree[10][10];

int sets[100][10];
int top[100];
public:
void read_graph();
void initialize_span_t();
void sort_edges();
void algorithm();
int find_node(int );
void print_min_span_t();
};

void kruskal::read_graph()
{
cout<<"*************************************************\n"
<<"This program implements the kruskal algorithm\n"
<<"************************************************\n";
cout<<"Enter the no. of nodes in the undirected weighted graph ::";
cin>>n;

noe=0;

cout<<"enter the weights for the following edges ::\n";
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
cout<<" < "<<i<<" , "<<j<<" > ::";
int w;
cin>>w;
if(w!=0)
{
noe++;

graph_edge[noe][1]=i;
graph_edge[noe][2]=j;
graph_edge[noe][3]=w;
}
}
}

// print the graph edges

cout<<"\n\nThe edges in the given graph are::\n";
for(i=1;i<=noe;i++)
cout<<" < "<<graph_edge[i][1]
<<" , "<<graph_edge[i][2]
<<" > ::"<<graph_edge[i][3]<<endl;

}

void kruskal::sort_edges()
{
/**** Sort the edges using bubble sort in increasing order**************/

for(int i=1;i<=noe-1;i++)
{
for(int j=1;j<=noe-i;j++)
{
if(graph_edge[j][3]>graph_edge[j+1][3])
{
int t=graph_edge[j][1];
graph_edge[j][1]=graph_edge[j+1][1];
graph_edge[j+1][1]=t;

t=graph_edge[j][2];
graph_edge[j][2]=graph_edge[j+1][2];
graph_edge[j+1][2]=t;

t=graph_edge[j][3];
graph_edge[j][3]=graph_edge[j+1][3];
graph_edge[j+1][3]=t;
}
}
}

// print the graph edges

cout<<"\n\nAfter sorting the edges in the given graph are::\n";
for(i=1;i<=noe;i++)
cout<<" < "<<graph_edge[i][1]
<<" , "<<graph_edge[i][2]
<<" > ::"<<graph_edge[i][3]<<endl;
}

void kruskal::algorithm()
{
// ->make a set for each node
for(int i=1;i<=n;i++)
{
sets[i][1]=i;
top[i]=1;
}

cout<<"\nThe algorithm starts ::\n\n";

for(i=1;i<=noe;i++)
{
int p1=find_node(graph_edge[i][1]);
int p2=find_node(graph_edge[i][2]);

if(p1!=p2)
{
cout<<"The edge included in the tree is ::"
<<" < "<<graph_edge[i][1]<<" , "
<<graph_edge[i][2]<<" > "<<endl<<endl;

tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];

// Mix the two sets

for(int j=1;j<=top[p2];j++)
{
top[p1]++;
sets[p1][top[p1]]=sets[p2][j];
}

top[p2]=0;
}
else
{
cout<<"Inclusion of the edge "
<<" < "<<graph_edge[i][1]<<" , "
<<graph_edge[i][2]<<" > "<<"forms a cycle so it is removed\n\n";
}
}
}

int kruskal::find_node(int n)
{
for(int i=1;i<=noe;i++)
{
for(int j=1;j<=top[i];j++)
{
if(n==sets[i][j])
return i;
}
}
return -1;
}

int main()
{
kruskal obj;
obj.read_graph();
obj.sort_edges();
obj.algorithm();
return 0;
}


All times are GMT +5.5. The time now is 10:48.