Question

write a c or c++ program to write a prims algorithm and for problem 2(b) use kruskal algorithm.

Problem 2 (A) (Prim's Algorithm): Apply Prim's algorithm to the following graph. Include in the priority queue only the fringe vertices (the vertices not in the current tree which are adjacent to at least one tree vertex) Problem 2 (B) (Kruskal Algorithm): Apply Kruskaľ's algorithm to find a minimum spanning tree of the following graphs. 4 3 2 2 4 3 6

Answer 1

Please upvote if you like this answer.

ANSWER:

kruSkai's methed Step Setect min Cast ene seep 2:ー Select next rvin Cost edge which no nt y to Convecteed with visted Sepf Selected esfo Cycle o not nciudet Seppeet Step 2,3 untiu Ou vevties visited After apptin kuskai's aaerithn to find min San e-a @y_1ー:@ 5 5 Total Cost3+3+ +3+5+6+5

PRIMS ALGOROTHM IN C:

CODE:

#include<stdio.h>
#include<stdlib.h>
#define infinity 9999
#define MAX 20
int G[MAX][MAX],spanning[MAX][MAX],n;
int prims();
int main()
{
   int i,j,total_cost;
   printf("Enter no. of vertices:");
   scanf("%d",&n);
   printf("\nEnter the adjacency matrix:\n");
   for(i=0;i<n;i++)
       for(j=0;j<n;j++)
           scanf("%d",&G[i][j]);
   total_cost=prims();
   printf("\nspanning tree matrix:\n");  
   for(i=0;i<n;i++)
   {
       printf("\n");
       for(j=0;j<n;j++)
           printf("%d\t",spanning[i][j]);
   }  
   printf("\nTotal cost of spanning tree=%d",total_cost);
   return 0;
}
int prims()
{
   int cost[MAX][MAX];
   int u,v,min_distance,distance[MAX],from[MAX];
   int visited[MAX],no_of_edges,i,min_cost,j;  
   //create cost[][] matrix,spanning[][]
   for(i=0;i<n;i++)
       for(j=0;j<n;j++)
       {
           if(G[i][j]==0)
               cost[i][j]=infinity;
           else
               cost[i][j]=G[i][j];
               spanning[i][j]=0;
       }      
   //initialise visited[],distance[] and from[]
   distance[0]=0;
   visited[0]=1;  
   for(i=1;i<n;i++)
   {
       distance[i]=cost[0][i];
       from[i]=0;
       visited[i]=0;
   }  
   min_cost=0;       //cost of spanning tree
   no_of_edges=n-1;       //no. of edges to be added  
   while(no_of_edges>0)
   {
       //find the vertex at minimum distance from the tree
       min_distance=infinity;
       for(i=1;i<n;i++)
           if(visited[i]==0&&distance[i]<min_distance)
           {
               v=i;
               min_distance=distance[i];
           }      
       u=from[v];  
       //insert the edge in spanning tree
       spanning[u][v]=distance[v];
       spanning[v][u]=distance[v];
       no_of_edges--;
       visited[v]=1;
       //updated the distance[] array
       for(i=1;i<n;i++)
           if(visited[i]==0&&cost[i][v]<distance[i])
           {
               distance[i]=cost[i][v];
               from[i]=v;
           }
       min_cost=min_cost+cost[u][v];
   }
   return(min_cost);
}