[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:

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).

{ v5 } and { v6 } are closest . . .

MST/Kruskal
-
now { v3 } and { v4 } are closest . . .
MST/Kruskal
-
now 3 choices, break tie in favour of { v2 } and { v3, v4 }, say . . .
MST/Kruskal
-
now { v1 } and { v2, v3, v4 } . . .
MST/Kruskal
-
finally { v5, v6 } and { v1, v2, v3, v4 } . . .
MST/Kruskal
-
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'

Correctness of Kruskal's algorithm

Complexity of Kruskal's Minimum Spanning Tree algorithm.

NB. Partition algorithm and data structure is called "Union-Find".

MST/Kruskal

Algorithm needs short edges:

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:

Complexity of Partition for Kruskal's algorithm:

Graphs:   Min' Spanning Tree (Kruskal):   Summary

Prepare: Directed Acyclic Graphs (DAGs).
© L.Allison, Sunday, 28-Nov-2021 04:43:53 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/17MST2.shtml
Computer Science, Software Engineering, Science (Computer Science).