[Subject home],
[FAQ],
[progress],
Bib',
Alg's,
C ,
Java- L.A.,
Friday, 26-Apr-2024 03:23:19 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 (Prim): Introduction
Saw various kinds of
Graph
and examples,
now . . .
Minimum
spanning tree (MST) of a weighted undirected graph, G.
An MST is connected, contains all vertices and
a subset of edges of G.
Note, cycles are redundant for connectivity.
Spanning tree is non-redundant, cheaper.
Minimum one = cheapest.
(NB. redundancy may in fact be useful for reliability.)
v2 is closest (and only remaining) vertex . . . MST
Done: Minimum Spanning Tree for G. [lecturer: run demo'; class: take notes!]
done := {v1} --initial Tree is <{v1},{}>
for vertex i in V-{v1}
T[i] := E[1,i] --direct edges else "infinity" [*]
end for
loop |V|-1 times
-- INV: {T[v]|v in done} represents a min' spanning Tree
-- of the nodes in done and {T[u]|u not in done} contains
-- the shortest known distances from the (sub-)spanning Tree
-- to such vertices u.
find closest vertex to (sub-)spanning Tree in V - done;
done +:= {closest};
add `closest' and `edge T[closest]' to (sub-)spanning Tree;
for vertex j in V - done
T[j] := min(T[j], --update knowledge on paths,
E[closest,j]) --perhaps better? [*]
end for
end loop -- run demo', cf. Dijkstra's
[*] Need to store more information to recover the MST as well as its cost.