PROBLEM: Find the Minimum Spanning Tree

PROBLEM: Find the Minimum Spanning Tree

of a Weighted Connected Undirected Graph

Kruskal’s Algorithm

(A) Input the set of nodes (N).

(B) Input the set of edges (E) in ascending order.

(D) Initialize the solution set (T) to be empty. It will eventually hold a subset of E.

(E) Kruskal’s Algorithm Note: | | below means the number of elements in the set

While |CNS| > 1 and E is not empty do

{

Remove the shortest edge S from the edge set E.

IF the edge S would connect two separate node sets in CNS,

THEN form the union of those node sets and add the edge S

to the solution set T.

ELSE discard the edge S as it would connect nodes already connected.

}

Once all the connected node sets are brought together, none of the remaining edges are considered. Note that for N nodes, a spanning tree of a connected graph will always contain N-1 edges. The minimum spanning tree is the spanning tree with the minimum total length.

Questions:

1. In what sense of the word is the resulting structure a tree? See the definition of a tree.

2. Will any N-1 element subset of the set of edges produce a spanning tree? Which ones will not?

3. How would I rewrite the algorithm to find the minimum spanning forest for an unconnected graph?

4. Why is this considered to be an example of a Greedy Algorithm?

Initial:

N: {A, B, C, D, E, F, G, H. I, J, K, L}

E: { (B,E,2), (F,I,3), (C,F,4), (C,I,5), (B,J,6), ... ,(J,K,22) }

T: { }

CNS: { {A}, {B}, {C}, {D}, {E}, {F}, {G}, {H}, {I}, {J}, {K}, {L} }

After (B,E,2) is accepted:

T: { {B,E,2} }

CNS: { {A}, {B, E}, {C}, {D}, {F}, {G}, {H}, {I}, {J}, {K}, {L} }

After (F,I,3) is accepted:

T: { {B,E,2},{F,I,3} }

CNS: { {A}, {B, E}, {C}, {D}, {F, I}, {G}, {H}, {J}, {K}, {L} }

After (C,F,4) is accepted:

T: { {B,E,2}, (F,I,3), (C,F,4) }

CNS: { {A}, {B, E}, {C, F, I}, {D}, {G}, {H}, {J}, {K}, {L} }

After (C,I,5) is rejected:

T and CNS are unchanged as nodes C and I are already connected (in the same set in CNS).

Continue until all nodes are connected (CNS contains only one set).

This will always require N-1 edges. The remaining edges in E are all rejected. T represents the minimum spanning tree. If all the edges are processed and |CNS| never drops to 1, then the graph is not connected. In this case, T automatically contains the minimum spanning forest.