Write a program to determine the minimum spanning tree of a graph For the algorithms at S.No 1 to 3 test run the algorithm on 100 different inputs of sizes varying from 30 to 1000. Count the number of comparisons and draw the graph. Compare it with a graph of nlogn

---

#include<stdio.h>

#include<conio.h>

int a,b,u,v,n,i,j,ne=1;

int visited[10]={0},min,mincost=0,cost[10][10];

void main()

{

 clrscr();

 printf("n Enter the number of nodes:");

 scanf("%d",&n);

 printf("n Enter the adjacency matrix:n");

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

  for(j=1;j<=n;j++)

  {

   scanf("%d",&cost[i][j]);

   if(cost[i][j]==0)

    cost[i][j]=999;

  }

 visited[1]=1;

 printf("n");

 while(ne<n)

 {

  for(i=1,min=999;i<=n;i++)

   for(j=1;j<=n;j++)

    if(cost[i][j]<min)

     if(visited[i]!=0)

     {

      min=cost[i][j];

      a=u=i;

      b=v=j;

     }

  if(visited[u]==0 || visited[v]==0)

  {

   printf("n Edge %d:(%d %d) cost:%d",ne++,a,b,min);

   mincost+=min;

   visited[b]=1;

  }

  cost[a][b]=cost[b][a]=999;

 }

 printf("n Minimun cost=%d",mincost);

 getch();

}

---

Output:-