MST PDF

CSC 373 - Algorithm Design, Analysis, and Complexity Summer 2016
Lalla Mouatadid
Greedy Algorithms: Minimum Spanning Tree
Definitions :
G(V, E, w) is an edge weighted graph if there exists a weight function w : E → R that assigns a weight
to every edge e ∈ E.
G(V, E) is connected if there exists a path between any two vertices. G(V, E) is a tree if it is connected
and has has no cycles. It is easy to see (convince yourself otherwise) that if G(V, E) is a tree and |V | = n,
then |E| = n − 1.
Let H(V 0 , E 0 ) be a subgraph of G(V, E). We say that H is a spanning tree of G if H is a tree and V 0 = V .
Let G(V, E, w) be an edge-weighted graph where w : E → N. H(V, E 0 ) is a minimum spanning tree of

GPif it is a spanning tree with weight less than or equal to the weight of any other spanning tree of G, i.e.,
w(e) for all other spanning trees H 0 (V, E 00 ) of G.
P
w(e) ≤
e∈E 0 e∈E 00
The MST problem asks for a minimum spanning tree of G. As we saw in class, a graph could have many
MST’s. It is quite amazing that many greedy algorithms for the MST problem are optimal, we covered
two in class and tutorial: Prim’s algorithm and Kruskal’s algorithm. Try to come up with another greedy
approach that gives you an optimal solution, for fun :) !
Before getting into the algorithms, let recall two facts about spanning trees:
1. Let T be a spanning tree of G. If you add any edge e ∈ / T to T then T 0 = T ∪ {e} contains a cycle.
This is easy to see. Let e = (u, v) be an edge not in T . Since T is a spanning tree, then there is already
a path between any two vertices of G; in particular there is a path between u and v. Adding e to T
will thus close the cycle from u to v.
2. Consider T 0 = T ∪ {e} as defined above, and let C be the cycle created by adding the edge e. If you
remove any edge e0 ∈ C from the cycle, you will get a new spanning tree of G; since removing an edge
from a cycle will not disconnect the graph.
Recall as well our discussion regarding adaptive vs. non adaptive greedy algorithms. Prim’s Algorithm
reorders its input in order to choose the cheapest edge. We say that Prim’s Algorithm is an adaptive
greedy algorithm; in the sense that, at every iteration, the algorithm tries to readjust the input to its own
convenience. In contrast, Kruskal’s Algorithm was non-adaptive, since the algorithm sorts the edges once
at the beginning and blindly processes one edge at a time.
1 Prim’s Algorithm
Proof of optimality:
Proof. Let T be the spanning tree returned by the algorithm, and suppose there doesn’t exist any MST of
G consistent with T . Consider an optimal MST O of G.
1
2
Algorithm 1 Prim’s Algorithm

Input: A weighted graph G(V, E, w) P
Output: A spanning tree T that minimizes w(e)
e∈E 0
1: U ←V
2: Pick an arbitrary start vertex s ∈ V
3: T = {s}
4: U ← U \{s}
5: while U 6= ∅ do
6: Choose u ∈ U adjacent to a v ∈ T such that w(u, v) is smallest out of all such vertices.
7: T ← T ∪ {u}
8: U ← U \{u}
9: end while
10: return T
Let e = (x, y) be the first edge chosen by the algorithm that is inconsistent with any MST of G, and let
T 0 be the sub-tree of T created by the algorithm just before the edge e was chosen. Let Pxy be the path
between x and y in O. Let C be the cycle created in O from adding e to Pxy (Fact 1).
Pxy must contain an edge e0 = (a, b) that has an end point in T 0 and end point outside of T 0 . Why? Since
otherwise, Pxy would be fully contained in T 0 , and choosing e(x, y) next would create a cycle in T 0 ∪ e, a
contradiction to step 6 of the Algorithm.
Therefore both e(x, y) and e0 (a, b) have an end point in T 0 and an point outside of T 0 . Since the algorithm
chose e instead of e0 , it follows that w(e) ≤ w(e0 ). By Fact (2), we can break C by removing e0 (a, b) and
obtaining a new MST of G, call it O0 . Notice that the total weight of O0 is w(O0 ) = w(O) + w(e) − w(e0 ).
Since w(e) ≤ w(e0 ), it follows that w(O0 ) ≤ w(O). Thus there exists an optimal MST of G, O0 , that contains
the edge e(x, y). Therefore, in order to show that Prim’s Algorithm does indeed produce an optimal MST
fo G, it suffices to repeat this argument for every new edge ẽ chosen by the algorithm, such that ẽ doesn’t
appear in any optimal solution.
2 Kruskal’s Algorithm
Algorithm 2 Kruskal’s Algorithm

Input: A weighted graph G(V, E, w) P
Output: A spanning tree T that minimizes w(e)
e∈E 0
1: Sort the edges of G in non-decreasing order of their weight: w(e1 ) ≤ w(e2 ) ≤ ... ≤ w(em ).
2: T ←∅
3: for i ← 1...m do
4: Remove ei from E
5: if Adding ei to T does not create a cycle then
6: T ← T ∪ {ei }
7: end if
8: end for
9: return T
Proof of optimality: We will prove optimality by contradiction.

3
Proof. Let T be the spanning tree returned by the algorithm, and suppose there doesn’t exist any MST of
G consisten with T .
Let e be the first edge chosen by the algorithm that is inconsistent with tany MST and let F be the forest
constructed by the algorithm just before adding e.
By the choice of e, there exists an optimal MST M of G consistent with F . By Fact (1), adding e to M
creates a cycle C. C must contain an edge e0 connecting two trees in F (why?).
Since the algorithm chose e instead of e0 , w(e) ≤ w(e0 ). Therefore, exchanging e for e0 can only decrease the
total weight of M . And by Fact (2), this exchange would also create a new spanning tree of G that contains
e. A contradiction to our assumption.

MST PDF

Uploaded by

Copyright:

Available Formats

MST PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

MST PDF

Uploaded by

Copyright:

Available Formats

CSC 373 - Algorithm Design, Analysis, and Complexity Summer 2016

Let G(V, E, w) be an edge-weighted graph where w : E → N. H(V, E 0 ) is a minimum spanning tree of

Algorithm 1 Prim’s Algorithm

Algorithm 2 Kruskal’s Algorithm

Proof of optimality: We will prove optimality by contradiction.

You might also like