answersLogoWhite

0

/* Program for creating a minimum spanning tree from Kruskal's

algorithm */

#include

#define MAX 20

struct edge

{

int u;

int v;

int weight;

struct edge *link;

}*front = NULL;

int father[MAX]; /*Holds father of each node */

struct edge tree[MAX]; /* Will contain the edges of spanning tree */

int n; /*Denotes total number of nodes in the graph */

int wt_tree=0; /*Weight of the spanning tree */

int count=0; /* Denotes number of edges included in the tree */

/* Functions */

void make_tree();

void insert_tree(int i,int j,int wt);

void insert_pque(int i,int j,int wt);

struct edge *del_pque();

main()

{

int i;

create_graph();

make_tree();

printf("Edges to be included in spanning tree are :\n");

for(i=1;i<=count;i++)

{

printf("%d->",tree[i].u);

printf("%d\n",tree[i].v);

}

printf("Weight of this minimum spanning tree is : %d\n", wt_tree);

}/*End of main()*/

create_graph()

{

int i,wt,max_edges,origin,destin;

printf("Enter number of nodes : ");

scanf("%d",&n);

max_edges=n*(n-1)/2;

for(i=1;i<=max_edges;i++)

{

printf("Enter edge %d(0 0 to quit): ",i);

scanf("%d %d",&origin,&destin);

if( (origin==0) && (destin==0) )

break;

printf("Enter weight for this edge : ");

scanf("%d",&wt);

if( origin > n destin > n origin<=0 destin<=0)

{

printf("Invalid edge!\n");

i--;

}

else

insert_pque(origin,destin,wt);

}/*End of for*/

if(i

{

printf("Spanning tree is not possible\n");

exit(1);

}

}/*End of create_graph()*/

void make_tree()

{

struct edge *tmp;

int node1,node2,root_n1,root_n2;

while( count < n-1) /*Loop till n-1 edges included in the tree*/

{

tmp=del_pque();

node1=tmp->u;

node2=tmp->v;

printf("n1=%d ",node1);

printf("n2=%d ",node2);

while( node1 > 0)

{

root_n1=node1;

node1=father[node1];

}

while( node2 >0 )

{

root_n2=node2;

node2=father[node2];

}

printf("rootn1=%d ",root_n1);

printf("rootn2=%d\n",root_n2);

if(root_n1!=root_n2)

{

insert_tree(tmp->u,tmp->v,tmp->weight);

wt_tree=wt_tree+tmp->weight;

father[root_n2]=root_n1;

}

}/*End of while*/

}/*End of make_tree()*/

/*Inserting an edge in the tree */

void insert_tree(int i,int j,int wt)

{

printf("This edge inserted in the spanning tree\n");

count++;

tree[count].u=i;

tree[count].v=j;

tree[count].weight=wt;

}/*End of insert_tree()*/

/*Inserting edges in the priority queue */

void insert_pque(int i,int j,int wt)

{

struct edge *tmp,*q;

tmp = (struct edge *)malloc(sizeof(struct edge));

tmp->u=i;

tmp->v=j;

tmp->weight = wt;

/*Queue is empty or edge to be added has weight less than first edge*/

if( front NULL) /*Edge to be added at the end*/

tmp->link = NULL;

}/*End of else*/

}/*End of insert_pque()*/

/*Deleting an edge from the priority queue*/

struct edge *del_pque()

{

struct edge *tmp;

tmp = front;

printf("Edge processed is %d->%d %d\n",tmp->u,tmp->v,tmp->weight);

front = front->link;

return tmp;

}/*End of del_pque()*/

User Avatar

Wiki User

14y ago

What else can I help you with?

Related Questions

Write a program to implement prim's algorithm?

dfgbrgffee


Write an algorithm to implement any three operation of a queue?

8798797


Write a program in C language to implement the apriori algorithm?

JavaScript is one program that has been written in C to implement the Apriori algorithm. There are also several other known programs available on the Internet that implement it as well.


How do you write an Algorithm for a C plus plus Program?

You don't write an algorithm for a C++ program, unless you are documenting the C++ program after-the-fact. The normal procedure is to write the algorithm first, in a language independent fashion, and then translate that stated algorithm into C++ code, or into whatever language you wish.


What is algorithm to write algorithm to the program to access a pointer variable in structure?

Here is the algorithm of the algorithm to write an algorithm to access a pointer in a variable. Algorithmically.name_of_the_structure dot name_of_the _field,eg:mystruct.pointerfield


How do you write a Java program to implement weighted queue using circular doubly linked list?

Add weights to the elements of the queue and use an algorithm to sort the queue every time an element is added.


How do you write algorithms of java programs?

Write a program that graphically demonstrates the shortest path algorithm


What is algorithm write properties of algorithm?

An ALGORITHM is a sequence of steps that depicts the program logic independent of the language in which it is to be implemented. An algorithm should be designed with space and time complexities in mind.


How to write a java program that determines the number of prime numbers less than N which is given by the user?

where to start? do you have an algorithm and just want to implement it in java? depends on how big N is, as that will determine which method is most efficient


Write A program to implement insertion using AVL trees?

yes


How write the algorithm of a menu-driven C program?

To write the algorithm for a menu-driven C program, start by defining a loop that displays the menu options to the user. Use a switch-case structure to handle user input, allowing each case to correspond to a different option. Inside each case, implement the functionality for that option, and include a break statement to exit the case. Finally, provide an exit option to terminate the program cleanly when the user selects it.


Write a program to implement domain and referential integrity?

give me the program which can related on domain and referential integrity.