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
- Partition all nodes into sets (initially each set contains only its own node, later on the sets join and some sets are removed)
- Go through each edge in weight order, checking if it links two sets.
- If so, add it to the tree, and set the uppermost parent of a to be b.
- 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
- Create two sets; Tree and non-Tree
- Pick an arbitrary node to start in the Tree set
- 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.
- 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; } }
page revision: 15, last edited: 31 Oct 2011 23:04