shabbyheart

Kruskal Algorithm by link list

Jan 3rd, 2020
202
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.49 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Edge
  4. {
  5.     public:
  6.     int src, dest, weight;
  7. };
  8. class Graph
  9. {
  10.     public:
  11.     int V, E;
  12.     Edge* edge;
  13. };
  14. //Graph* createGraph(int V, int E)
  15. //{
  16. //    Graph* graph = new Graph;
  17. //    graph->V = V;
  18. //    graph->E = E;
  19. //    graph->edge = new Edge[E];
  20. //
  21. //    return graph;
  22. //}
  23. class subset
  24. {
  25.     public:
  26.     int parent;
  27.     int rank;
  28. };
  29. int find(subset subsets[], int i)
  30. {
  31.     if (subsets[i].parent != i)
  32.         subsets[i].parent = find(subsets, subsets[i].parent);
  33.  
  34.     return subsets[i].parent;
  35. }
  36. void Union(subset subsets[], int x, int y)
  37. {
  38.     int xroot = find(subsets, x);
  39.     int yroot = find(subsets, y);
  40.     if (subsets[xroot].rank < subsets[yroot].rank)
  41.         subsets[xroot].parent = yroot;
  42.     else if (subsets[xroot].rank > subsets[yroot].rank)
  43.         subsets[yroot].parent = xroot;
  44.     else
  45.     {
  46.         subsets[yroot].parent = xroot;
  47.         subsets[xroot].rank++;
  48.     }
  49. }
  50. int myComp(const void* a, const void* b)
  51. {
  52.     Edge* a1 = (Edge*)a;
  53.     Edge* b1 = (Edge*)b;
  54.     return a1->weight > b1->weight;
  55. }
  56. void KruskalMST(Graph* graph)
  57. {
  58.     int V = graph->V;
  59.     Edge result[V]; // Tnis will store the resultant MST
  60.     int e = 0; // An index variable, used for result[]
  61.     int i = 0; // An index variable, used for sorted edges
  62.     qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
  63.  
  64.     subset *subsets = new subset[( V * sizeof(subset) )];
  65.     for (int v = 0; v < V; ++v)
  66.     {
  67.         subsets[v].parent = v;
  68.         subsets[v].rank = 0;
  69.     }
  70.     while (e < V - 1 && i < graph->E)
  71.     {
  72.         Edge next_edge = graph->edge[i++];
  73.  
  74.         int x = find(subsets, next_edge.src);
  75.         int y = find(subsets, next_edge.dest);
  76.         if (x != y)
  77.         {
  78.             result[e++] = next_edge;
  79.             Union(subsets, x, y);
  80.         }
  81.     }
  82.     int sum = 0;
  83.     cout<<"Following are the edges in the constructed MST\n";
  84.     for (i = 0; i < e; ++i)
  85.         cout<<result[i].src<<" -- "<<result[i].dest<<" == "<<result[i].weight<<endl;
  86.  
  87.     for(i =0; i<e; i++)
  88.         sum += result[i].weight;
  89.     cout<<endl<<"Total cost = "<< sum;
  90.     return;
  91. }
  92. int main()
  93. {
  94.     freopen("input.txt","r",stdin);
  95.     Graph* g=new Graph();
  96.     cin>>g->V>>g->E;
  97.     g->edge = new Edge[g->E];
  98.     int i=0;
  99.     while(i<g->E)
  100.     {
  101.         cin>>g->edge[i].src;
  102.         cin>>g->edge[i].dest;
  103.         cin>>g->edge[i].weight;
  104.         i++;
  105.     }
  106.     KruskalMST(g);
  107.  
  108.     return 0;
  109. }
Add Comment
Please, Sign In to add comment