Skip to main content

Kruskal's MST on 9-vertex graph

Short answer

Kruskal sorts edges: g-h1, f-g2, a-b4, i-g6, c-d7, b-c8, h-a8, d-e9 accepted; h-i7 rejected. MST edges: g-h, f-g, a-b, i-g, c-d, b-c, h-a, d-e. Minimum cost = 45.

Find the minimum spanning tree of the following graph using Kruskal's algorithm. [Figure: undirected weighted graph on vertices a, b, c, d, e, f, g, h, i with edges a-b 4, b-c 8, c-d 7, d-e 9, e-f 10, f-g 2, g-h 1, h-a 8, b-h 11, h-i 7, i-g 6]

Graph with 9 vertices a to i, so the MST has 8 edges. Sort the edges: g-h 1, f-g 2, a-b 4, i-g 6, c-d 7, h-i 7, b-c 8, h-a 8, d-e 9, e-f 10, b-h 11.

StepEdgeWeightDecisionTotal
1g-h1accept1
2f-g2accept3
3a-b4accept7
4i-g6accept13
5c-d7accept20
6h-i7reject (h, i already connected through g)20
7b-c8accept28
8h-a8accept (joins {a,b,c,d} with {f,g,h,i})36
9d-e9accept (adds e, 8th edge)45

MST edges: g-h, f-g, a-b, i-g, c-d, b-c, h-a, d-e. Minimum cost = 45.

e -9- d -7- c -8- b -4- a -8- h -1- g -2- f
                                    |
                                    6
                                    |
                                    i

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 10 questions →