fork download
copy 
  1. #include<stdio.h>
  2. int cost[10][10],n;
  3. void kruskal()
  4. {
  5. int par[n];
  6. int a=0,b=0,u=0,v=0,min, mincost = 0, ne = 0;
  7. for(int i=0;i<n;i++)
  8. par[i]=-1;
  9. printf("the minimum spanning tree edges are...");
  10. while(ne < n-1)
  11. {
  12. //Find the least cost edge
  13. min = 999;
  14. for(int i=0;i<n;i++)
  15. for(int j=0;j<n;j++)
  16. if(cost[i][j] < min)
  17. {
  18. min=cost[i][j];
  19. a=u=i;
  20. b=v=j;
  21. }
  22. //Check if edge select cause cyclicity?
  23. while(par[u]!=-1)
  24. u=par[u];
  25. while(par[v]!=-1)
  26. v=par[v];
  27. if(u!=v)
  28. {
  29. printf("From vertex %d to vertex %d and the cost = %d\n",a,b,min);
  30. mincost+=min;
  31. par[v]=u;
  32. ne++;
  33. }
  34. //edge included in MST should not be considered for next iteration
  35. cost[a][b]=cost[b][a]=999;
  36. }
  37. printf("Cost of MST = %d", mincost);
  38. }
  39.  
  40. int main()
  41. {
  42. printf("Enter the no. of vertices:");
  43. scanf("%d",&n);
  44. printf("Enter the cost matrix\n");
  45. for(int i=0;i<n;i++)
  46. for(int j=0;j<n;j++)
  47. scanf("%d",&cost[i][j]);
  48. kruskal();
  49. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
4
99 65 65 45
76 76 54 65 
5 4 6 88
45 87 54 88
stdout
copy 
Enter the no. of vertices:Enter the cost matrix
the minimum spanning tree edges are...From vertex 2 to vertex 1 and the cost = 4
From vertex 2 to vertex 0 and the cost = 5
From vertex 0 to vertex 3 and the cost = 45
Cost of MST = 54
https://ideone.com/5T7xIE
language:
C (clang 8.0)
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!