Skip to main content

Kruskal's MST on 7-vertex graph

Short answer

Using Kruskal, sort edges: C-E1, F-G1, A-C2, B-F2, D-F2, C-D4 accepted; B-D3, B-G3 rejected. MST edges: C-E, F-G, A-C, B-F, D-F, C-D. Minimum cost = 12.

Create minimum spanning tree for the following graph using Kruskal's algorithm. [Figure: undirected weighted graph on vertices A to G with edges A-B 5, A-C 2, A-D 6, B-D 3, B-F 2, B-G 3, C-D 4, C-E 1, D-F 2, D-G 4, E-F 6, F-G 1]

Edges of the graph (A to G, 7 vertices, so the MST needs 6 edges), sorted by weight: C-E 1, F-G 1, A-C 2, B-F 2, D-F 2, B-D 3, B-G 3, C-D 4, D-G 4, A-B 5, A-D 6, E-F 6.

StepEdgeWeightDecisionComponents after
1C-E1accept{C,E}
2F-G1accept{F,G}
3A-C2accept{A,C,E}
4B-F2accept{B,F,G}
5D-F2accept{B,D,F,G}
6B-D3reject (B, D already connected)
7B-G3reject (cycle B-F-G)
8C-D4accept{A,B,C,D,E,F,G}

Six edges selected, stop.

        E
        | 1
A --2-- C --4-- D --2-- F --2-- B
                        |
                        1
                        G

Edges of the MST: C-E, F-G, A-C, B-F, D-F, C-D.

Minimum cost = 1 + 1 + 2 + 2 + 2 + 4 = 12.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 10 questions →