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);

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
parentA = parent(parents, e.a);
parentB = parent(parents, e.b);
if (parentA != parentB) {
insertEdge(k, e);
}

}

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.

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
inTreeA = inTree(tree, e.a, numV);
inTreeB = inTree(tree, e.b, numV);
if (inTreeA != inTreeB) {
insertEdge(m, e);
// 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;
}

}
```
page revision: 15, last edited: 31 Oct 2011 23:04