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

{ 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

• 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

1. finding shortest edge joining two different sub-trees (subsets) and

2. 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".

MST/Kruskal

### Algorithm needs short edges:

• Could sort edges, taking   O(|E|.log|E|)-time, or

• 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:
vertex :   . . . vj . . . vp . . . vi . . .
to subset:    . . .
 St
 . . .
 Su
 . . .
 St
 . . .
Complexity of Partition for Kruskal's algorithm:

• What subset contains vi ?

• To merge two subsets:

• Append their membership lists, and

• change "contained-by" array for the vertices in the smaller subset.

• Total time is O(|E|.log|E|) for Kruskal's algorithm

because [________________________].

## Graphs:   Min' Spanning Tree (Kruskal):   Summary

• Complexity: worst-case:   O( | E | . log | E | )-time -

• dominated by the priority queue operations to find short edges.

(Note,   |E| >= |V|-1 if the graph is connected.)

• Kruskal's is faster than Prim's if   | E | << | V |2

i.e. faster for sparse graphs.

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