fork download
copy 
  1. #include<stdio.h>
  2. int cost[10][10],n;
  3. void prim()
  4. {
  5. int vt[10]={0};
  6. int a=0,b=0,min, mincost = 0, ne = 0;
  7. //start from the first vertex
  8. vt[0] = 1;
  9. while(ne < n-1)
  10. {
  11. //Find the nearest neighbour
  12. min = 999;
  13. for (int i = 0; i<n; i++)
  14. {
  15. if(vt[i]==1)
  16. for(int j = 0;j <n; j++)
  17. if(cost[i][j] < min && vt[j]==0)
  18. {
  19. min = cost[i][j];
  20. a = i;
  21. b = j;
  22. }
  23. }
  24. //Include nearest neighbour 'b' into MST
  25. printf("Edge from vertex %d to vertex %d and the cost %d\n",a,b,min);
  26. vt[b] = 1;
  27. ne++;
  28. mincost += min;
  29. cost[a][b] = cost[b][a] = 999;
  30. }
  31. printf("minimum spanning tree cost is %d",mincost);
  32. }
  33.  
  34.  
  35. int main()
  36. {
  37. printf("Enter the no. of vertices: ");
  38. scanf("%d",&n);
  39. printf("Enter the cost matrix\n");
  40. for(int i=0;i<n;i++)
  41. for(int j=0;j<n;j++)
  42. scanf("%d",&cost[i][j]);
  43. prim();
  44. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4
999 2 3 1
2 999 4 999
3 4 999 5 
1 999 5 999
stdout
copy 
Enter the no. of vertices: Enter the cost matrix
Edge from vertex 0 to vertex 3 and the cost 1
Edge from vertex 0 to vertex 1 and the cost 2
Edge from vertex 0 to vertex 2 and the cost 3
minimum spanning tree cost is 6
https://ideone.com/0beBh0
language:
C (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!