[Subject home],
[FAQ],
[progress],
Bib',
Alg's,
C ,
Java- L.A.,
Friday, 03-May-2024 08:39:11 AEST 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 closesttrees
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 := {{v1}, ..., {vn}}; --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, T1 and T2,
using edge,
e = (v1, v2).
The vertices of T1 and of T2 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 T1 and T2 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:
Create singletons
{ {v1}, {v2}, . . . ,
{v|V|} }
What sub-tree (subset) is vertex vi in?
Merge two sub-trees (subsets).
NB. Partition algorithm and data structure
is called "Union-Find".
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,
S1={v1},
S2={v2}, . . . ,
S|V|={v|V|},
initially.
Have a data-structure, say an array of linked-lists,
giving the vertices in each subset (subtree) Si:
...
St
-----> vi -----> vj ---> ... ---> vk
...
Su
-----> vp -----> ... ---> vq
...
and have an array, indexed by vertex number,
giving the subset containing each vertex: