[Subject home],
[FAQ],
[progress],
Bib',
Alg's,
C ,
Java- L.A.,
Sunday, 28-Nov-2021 04:43:53 AEDT Instructions:
Topics discussed in these lecture notes are examinable
unless otherwise indicated.
You need to follow instructions,
take more notes &
draw diagrams especially as [indicated] or
as done in lectures,
work through examples, and
do extra reading.
Hyper-links not in [square brackets] are mainly for revision,
for further reading, and for lecturers of the subject.
Graphs:
Min' Spanning Tree (Kruskal):
Introduction
Recall:
cycles are redundant
spanning tree is connected, acyclic,
i.e. non-redundant
minimum spanning tree (MST) is "cheapest"
Prim's algorithm (for dense graphs) and . . .
Now,
Kruskal's
MST algorithm for sparse graphs . . . Kruskal's
algorithm
Start with a spanning forest,
of "singletons".
At each step, join the two closest_{ }trees
Partition vertices into (singleton) subsets.
Beware, two other meanings
of the word:
Partition an array (Quick-sort).
Partition an integer (combinatorics).
Minimum Spanning Tree of G. [lecturer: use demo'; class: take notes!]
P := {{v_{1}}, ..., {v_{n}}}; --partition V
E' := { };
loop |V|-1 times
--Inv: E' contains only edges of a min' span' tree
-- for each S in P & each S in P represents
-- a subtree of a minimum spanning tree of G
find shortest edge e joining
different subsets S1 and S2 in P;
E' += {e};
P := P - {S1,S2} + {S1 union S2}
end loop -- use demo'
Certainly gives a spanning tree, T.
But is it minimal?
Invariant true initially.
At an arbitrary step, alg' joins two minimum (sub-) trees, T_{1} and T_{2},
using edge,
e = (v_{1}, v_{2}).
The vertices of T_{1} and of T_{2} must be connected
somehow in every MST.
Suppose there is a better MST, T', of G, better than T
as found by Kruskal's algorithm.
T' must connect T_{1} and T_{2} somehow.
Adding e to T', forms a cycle,
so we can remove some other edge, f.
But T' + e - f at least as cheap as T' because
e was chosen as the cheapest edge "joining different"
sub-trees!
So that's impossible, contradiction: Kruskal's algorithm did make
an optimal choice.
Complexity of
Kruskal's
Minimum Spanning Tree algorithm.
Outer loop executed | V | - 1 times, but
overall complexity depends on
finding shortest edge joining two
different sub-trees (subsets) and
the operations to manipulate the
partition of the vertices:
better, keep a
priority-queue
(shortest on top) of edges,
still O(|E|.log|E|)-time
but with a smaller constant.
Examine edges until we find one linking two different subtrees,
i.e. two different subsets of the partition. [lecturer: draw diagrams; class: take notes!]
Partition (Union-Find) for
Kruskal's
Alg', a simple way:
Number subsets,
S_{1}={v_{1}},
S_{2}={v_{2}}, . . . ,
S_{|V|}={v_{|V|}},
initially.
Have a data-structure, say an array of linked-lists,
giving the vertices in each subset (subtree) S_{i}:
...
S_{t}
-----> v_{i} -----> v_{j} ---> ... ---> v_{k}
...
S_{u}
-----> v_{p} -----> ... ---> v_{q}
...
and have an array, indexed by vertex number,
giving the subset containing each vertex: