Suppose a company plans to build a communication network connecting its 5 computer centers in 5 cities. Any two cities can be linked with a leased cable line with a certain cost. Which links should be made to ensure that there is a connection between any two cities so that the total cost is minimum? The following graph illustrates the problem.
A solution to the above problem would be a spanning tree of the above weigted graph with minimum weight (i.e., the sum of the weights of the edges in the spanning tree is minimum). Such a spanning tree is called a minimum spanning tree.
Definition (Minimum spanning tree). A minimum spanning tree of a connected weighted graph \(G\) (i.e., edges of \(G\) have weights) is a spanning tree whose sum of edge weights
is not greater than that of other spanning trees of \(G\).
There are two well-known algorithms to find a minimum spanning tree: Kruskal's algorithm (1956) and Prim's algorithm (1957).
An algorithm is greedy if it makes optimal choices at each step. A greedy algorithm does not necessarily produce an optimal solution.
Both Kruskal's algorithm and Prim's algorithm are greedy algorithms but produce optimal solutions.
Kruskal's algorithm
Input: a weighted connected graph \(G\) on \(n\) vertices
Output: \(T\), a minimum spanning tree of \(G\)
\(T=\) the empty graph
for \(i=1\) to \(n-1\)
\(e=\) an edge of minimum weight not forming a cycle if added to \(T\)
\(T=T+e\)
return \(T\)
Example.
Use Kruskal's algorithm to find a minimum spanning tree of the above weighted \(W_5\).
Solution. We get a minimum spanning tree \(T\) by the following steps.
- \(T=\) the empty graph.
- \(\{a,b\}\) and \(\{c,d\}\) are the edges of minimum weight.
- \(T=T+\{c,d\}\) (or \(T+\{a,b\}\)).
- \(\{a,b\}\) is the edge of minimum weight that does not form a cycle when added to \(T\).
- \(T=T+\{a,b\}\).
- \(\{e,d\}\) (or \(\{a,e\}\)) is the edge of minimum weight that does not form a cycle when added to \(T\).
- \(T=T+\{e,d\}\).
- \(\{a,e\}\) is the edge of minimum weight that does not form a cycle when added to \(T\).
- \(T=T+\{a,e\}\).
Thus a minimum spanning tree \(T\) is the walk \(baedc\) with weight 6.
Prim's algorithm is similar to Kruskal's algorithm. But it requires that edge addition at each step creates a tree. Despite this requirement, it produces a minimum spanning tree.
Prim's algorithm
Input: a weighted connected graph \(G\) on \(n\) vertices
Output: \(T\), a minimum spanning tree of \(G\)
\(T=\) a minimum weight edge of \(G\)
for \(i=1\) to \(n-2\)
\(e=\) an edge of minimum weight incident with a vertex in \(T\)
not forming a cycle if added to \(T\)
\(T=T+e\)
return \(T\)
Example.
Use Prim's algorithm to find a minimum spanning tree of the above weighted \(W_5\).
Solution. We get a minimum spanning tree \(T\) by the following steps.
- \(T=\{a,b\}\) (or \(\{c,d\}\)).
- \(\{c,a\},\{e,a\},\{e,b\}, \{d,b\}\) are all incident with one vertex of \(T\), not forming a cycle when added to \(T\),
with weights \(4,2,3,3\) respectively.
- \(T=T+\{e,a\}\).
- \(\{c,a\},\{c,e\},\{d,e\}, \{d,b\}\) are all incident with one vertex of \(T\), not forming a cycle when added to \(T\),
with weights \(4,3,2,3\) respectively.
- \(T=T+\{d,e\}\).
- \(\{c,a\},\{c,e\},\{c,d\}\) are all incident with one vertex of \(T\), not forming a cycle when added to \(T\), with weights \(4,3,1\) respectively.
- \(T=T+\{c,d\}\).
Thus a minimum spanning tree \(T\) is the walk \(baedc\) with weight 6.
Last edited