title: C++ how to implement Kruskal's theorem for double weight (instead of integers)
body: <p>I found a template for Minimum Spanning Tree using Kruskal's algorithm <a href="http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/" rel="nofollow">here</a></p>
  
  <p>They're using integers weight, is it possible if I want to implement the code using double weight instead ?</p>
  
  <p>I made changes here and there and kept giving me errors.</p>
  
  <p>Here's what I changed:</p>
  
  <pre><code>struct Edge
  {
      int src, dest;
      double weight;
  };
  </code></pre>
  
  <p>and</p>
  
  <pre><code>   double myComp(const void* a, const void* b)
      {
          struct Edge* a1 = (struct Edge*)a;
          struct Edge* b1 = (struct Edge*)b;
          return a1-&gt;weight &gt; b1-&gt;weight;
      }
  </code></pre>
  
  <p>I don't know why, but these changes made the quicksort in <code>void KruskalMST(struct Graph* graph)</code> fail to work in the next couple of lines</p>
  
  <p>Here's the original code:</p>
  
  <pre><code>// Kruskal's algortihm to find Minimum Spanning Tree of a given connected,
  // undirected and weighted graph
  #include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;string.h&gt;
  
  // a structure to represent a weighted edge in graph
  struct Edge
  {
      int src, dest, weight;
  };
  
  // a structure to represent a connected, undirected and weighted graph
  struct Graph
  {
      // V-&gt; Number of vertices, E-&gt; Number of edges
      int V, E;
  
      // graph is represented as an array of edges. Since the graph is
      // undirected, the edge from src to dest is also edge from dest
      // to src. Both are counted as 1 edge here.
      struct Edge* edge;
  };
  
  // Creates a graph with V vertices and E edges
  struct Graph* createGraph(int V, int E)
  {
      struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph) );
      graph-&gt;V = V;
      graph-&gt;E = E;
  
      graph-&gt;edge = (struct Edge*) malloc( graph-&gt;E * sizeof( struct Edge ) );
  
      return graph;
  }
  
  // A structure to represent a subset for union-find
  struct subset
  {
      int parent;
      int rank;
  };
  
  // A utility function to find set of an element i
  // (uses path compression technique)
  int find(struct subset subsets[], int i)
  {
      // find root and make root as parent of i (path compression)
      if (subsets[i].parent != i)
          subsets[i].parent = find(subsets, subsets[i].parent);
  
      return subsets[i].parent;
  }
  
  // A function that does union of two sets of x and y
  // (uses union by rank)
  void Union(struct subset subsets[], int x, int y)
  {
      int xroot = find(subsets, x);
      int yroot = find(subsets, y);
  
      // Attach smaller rank tree under root of high rank tree
      // (Union by Rank)
      if (subsets[xroot].rank &lt; subsets[yroot].rank)
          subsets[xroot].parent = yroot;
      else if (subsets[xroot].rank &gt; subsets[yroot].rank)
          subsets[yroot].parent = xroot;
  
      // If ranks are same, then make one as root and increment
      // its rank by one
      else
      {
          subsets[yroot].parent = xroot;
          subsets[xroot].rank++;
      }
  }
  
  // Compare two edges according to their weights.
  // Used in qsort() for sorting an array of edges
  int myComp(const void* a, const void* b)
  {
      struct Edge* a1 = (struct Edge*)a;
      struct Edge* b1 = (struct Edge*)b;
      return a1-&gt;weight &gt; b1-&gt;weight;
  }
  
  // The main function to construct MST using Kruskal's algorithm
  void KruskalMST(struct Graph* graph)
  {
      int V = graph-&gt;V;
      struct Edge result[V];  // Tnis will store the resultant MST
      int e = 0;  // An index variable, used for result[]
      int i = 0;  // An index variable, used for sorted edges
  
      // Step 1:  Sort all the edges in non-decreasing order of their weight
      // If we are not allowed to change the given graph, we can create a copy of
      // array of edges
      qsort(graph-&gt;edge, graph-&gt;E, sizeof(graph-&gt;edge[0]), myComp);
  
      // Allocate memory for creating V ssubsets
      struct subset *subsets =
          (struct subset*) malloc( V * sizeof(struct subset) );
  
      // Create V subsets with single elements
      for (int v = 0; v &lt; V; ++v)
      {
          subsets[v].parent = v;
          subsets[v].rank = 0;
      }
  
      // Number of edges to be taken is equal to V-1
      while (e &lt; V - 1)
      {
          // Step 2: Pick the smallest edge. And increment the index
          // for next iteration
          struct Edge next_edge = graph-&gt;edge[i++];
  
          int x = find(subsets, next_edge.src);
          int y = find(subsets, next_edge.dest);
  
          // If including this edge does't cause cycle, include it
          // in result and increment the index of result for next edge
          if (x != y)
          {
              result[e++] = next_edge;
              Union(subsets, x, y);
          }
          // Else discard the next_edge
      }
  
      // print the contents of result[] to display the built MST
      printf("Following are the edges in the constructed MST\n");
      for (i = 0; i &lt; e; ++i)
          printf("%d -- %d == %d\n", result[i].src, result[i].dest,
                                                     result[i].weight);
      return;
  }
  
  // Driver program to test above functions
  int main()
  {
      /* Let us create following weighted graph
               10
          0--------1
          |  \     |
         6|   5\   |15
          |      \ |
          2--------3
              4       */
      int V = 4;  // Number of vertices in graph
      int E = 5;  // Number of edges in graph
      struct Graph* graph = createGraph(V, E);
  
  
      // add edge 0-1
      graph-&gt;edge[0].src = 0;
      graph-&gt;edge[0].dest = 1;
      graph-&gt;edge[0].weight = 10;
  
      // add edge 0-2
      graph-&gt;edge[1].src = 0;
      graph-&gt;edge[1].dest = 2;
      graph-&gt;edge[1].weight = 6;
  
      // add edge 0-3
      graph-&gt;edge[2].src = 0;
      graph-&gt;edge[2].dest = 3;
      graph-&gt;edge[2].weight = 5;
  
      // add edge 1-3
      graph-&gt;edge[3].src = 1;
      graph-&gt;edge[3].dest = 3;
      graph-&gt;edge[3].weight = 15;
  
      // add edge 2-3
      graph-&gt;edge[4].src = 2;
      graph-&gt;edge[4].dest = 3;
      graph-&gt;edge[4].weight = 4;
  
      KruskalMST(graph);
  
      return 0;
  }
  </code></pre>