Search

0.4.5.2.1 Source Code

Here is some untested code that implements Kruskal's algorithm in C++. It relies on a heap class, a graph class, and a general tree class with equivalence class operation methods. Although none of these classes are included here, this should be sufficient to give you an idea of how to implement Kruskal's algorithm:

void kruskal(graph \&g) {

  // our general equivalence class tree will have as many nodes as are
  // in the input graph G.  We will be linking these nodes up in the
  // body of the algorithm.
  gentree a(g.num_nodes());

  // we will also need an edge heap array in order to process the
  // edges in G one at a time in the order small->large
  edge e(G.num_edges());

  // the edge we are considering... also a loop storage variable
  edge w;
  
  // local counter
  int edge_count = 0;

  // loop control
  int i;

  // this is the number of spanning trees we are considering.  This
  // will start at the number of vertices in G but, as vertices are
  // joined up by lowest-weight edges, this will reduce.  Eventually
  // it will hit one at which point we know we should stop the algorithm.
  int numMST;

  // these are the endpoints of the edge we are considering
  vertex v, u;

  // save all the edges in G for later processing.
  for (i = 0; i < g.num_nodes; i++) {
    for (w = g.first_edge(i); g.is_edge(w); w = g.next_edge(w))
      e[edge_count++] = w;

    
  // min-heapify the edges
  minheap h(e, edge_count);

  // initially there are the same numer of equivalence classes as
  // the number of vertices in G; each vertex is its own class.
  numMST = G.num_nodes();

  // while we have not yet arrived at one equivalence class (spanning
  // tree)...
  for (i = 0; numMST > 1; i++) {

     // consider the next smallest edge
     w = h.remove_min();

     // look at w's endpoints
     v = g.vertex_one(w); u = g.vertex_two(w);

     // if these two vertices are not in the same equivalence class
     // (i.e. they are in different tree sections) join their
     // respective equivalence classes into one.
     if (a.differ(v.identifier(), u.identifier())) {
       a.union(v, u);
       add_edge_to_MST(w);

       // one less
       numMST--;
     }
  }
}