COMP1927 - Spanning Trees

A spanning tree is any path through a graph that connects every vertex.

A minimum spanning tree is the spanning tree with the least cost.

The two algorithms below (Kruskal's and Prim's) are optimal greedy strategies.

Kruskal's Algorithm

Kruskal's algorithm is actually quite simple. He focusses on edges, making it effective for sparse graphs.

Algorithm

  1. Partition all nodes into sets (initially each set contains only its own node, later on the sets join and some sets are removed)
  2. Go through each edge in weight order, checking if it links two sets.
  3. If so, add it to the tree, and set the uppermost parent of a to be b.
  4. Repeat until all nodes are in one set.

Complexity

It has a complexity of O(E*lg(E)) (and E < V2, which means that it's O(E*lg(V)), actually).

Code

Graph kruskal (Graph g, int numV, int numE) {
 
   Graph k = createGraph (numV);
   PQueue p = createPQueue();
 
   // Insert all the edges of the graph into the PQueue
   insertAllEdges(g, p);
 
   // Put every node in its own set to start with
   int parents[numV];
   int i;
   for (i = 0; i < numV; i++) {
      parents[i] = i;
   }
 
   Edge e;
   int parentA = 0;
   int parentB = 0;
 
   // Whilst we haven't looked at all the edges
   while (!isEmtpy(p)) {
 
      // Delete the smallest edge on the PQueue
      e = delMin(pq);
 
      // If the uppermost parents aren't the same
      // Then add it to the tree and link them
      parentA = parent(parents, e.a);
      parentB = parent(parents, e.b);
      if (parentA != parentB) {
         insertEdge(k, e);
         link(parents, parentA, e.b);
      }
 
   }
 
   return k;
 
}
 
int parent (int parents[], int vertex) {
 
   int upperParent = vertex;
 
   if (parents[vertex] != vertex) {
      upperParent = parent (parents, parents[vertex]);
   }
 
   return upperParent;
 
}
 
void link (int parents[], int parent, int vertex) {
 
   parents[parent] = vertex;
 
}

Prim's Algorithm

Prim's algorithm focusses on vertices, making it superior for dense graphs.

Algorithm

  1. Create two sets; Tree and non-Tree
  2. Pick an arbitrary node to start in the Tree set
  3. Go through each edge in weight order; if it links a Tree and non-Tree node, add it and swap the non-Tree node to Tree.
  4. Repeat until all nodes are Tree.

Complexity

Code

Graph prims (Graph g, int numV, int numE) {
 
   Graph m = createGraph (numV);
   PQueue p = createPQueue();
 
   int tree[numV];
   int nonTree[numV]
 
   // Set the 0th node to be the Tree set
   tree[0] = TRUE;
 
   // Insert the edges from the starting node into the PQueue
   insertEdges(g, p, 0);
 
   // Set the other nodes to be the nonTree set
   int i;
   for (i = 1; i < numV; i++) {
      nonTree[i-1] = TRUE;
      tree[i] = FALSE;
   }
 
   // Initialise blank cells to FALSE
   nonTree[numV-1] = FALSE;
 
   Edge e;
   int inTreeA = FALSE;
   int inTreeB = FALSE;
 
   // Whilst we haven't looked at all the edges
   while (!isEmtpy(p)) {
 
      // Delete the smallest edge on the PQueue
      e = delMin(pq);
 
      // If the edge links tree and nonTree
      // Then add it to the tree and link them
      inTreeA = inTree(tree, e.a, numV);
      inTreeB = inTree(tree, e.b, numV);
      if (inTreeA != inTreeB) {
         insertEdge(m, e);
         link(tree, nonTree, e.a, e.b, numV);
         // Insert the edges from the new node into the PQueue
         if (!inTreeA) {
            insertEdges(g, p, e.a);
         } else {
            insertEdges(g, p, e.b);
         }
      }
 
   }
 
   return k;
 
}
 
int inTree (int tree[], int vertex, int numV) {
 
   int result = FALSE;
 
   if (tree[vertex]) {
      result = TRUE;
   }
 
   return result;
 
}
 
void link (int tree[], int nonTree[], int vertex1, int vertex2, int numV) {
 
   if (!inTree(tree, vertex1, numV)) {
      tree[vertex1] = TRUE;
      nonTree[vertex1] = FALSE;
   } else {
      tree[vertex2] = TRUE;
      nonTree[vertex2] = FALSE;
   }
 
}