- 2069 Poush · 4 marks
Round Robin MST on 7-vertex graph
Short answer
Using Round Robin, the MST edges are A-F (10), B-G (14), C-D (12), E-D (22), E-F (25), B-C (16) with total weight 99.
Use Round Robin's algorithm to find minimum weight spanning tree from the following graph. [Figure: undirected weighted graph on vertices A, B, C, D, E, F, G with edges A-B 28, A-F 10, B-G 14, B-C 16, G-D 18, C-D 12, E-G 24, E-D 22, E-F 25]
Round Robin algorithm (Yao / Cheriton-Tarjan) builds an MST by merging trees. Start with every vertex as a separate tree placed in a queue. Repeat: remove the tree T at the front, find the minimum-weight edge leaving T, merge T with the tree at the other end of that edge (remove that tree from the queue), and add the merged tree to the rear. Stop when one tree remains.
Graph edges: A-B 28, A-F 10, B-G 14, B-C 16, G-D 18, C-D 12, E-G 24, E-D 22, E-F 25. Initial queue: [A] [B] [C] [D] [E] [F] [G].
| Step | Tree taken | Cheapest edge leaving it | Merge | Queue after |
|---|---|---|---|---|
| 1 | {A} | A-F (10) | with {F} | [B] [C] [D] [E] [G] [A,F] |
| 2 | {B} | B-G (14) | with {G} | [C] [D] [E] [A,F] [B,G] |
| 3 | {C} | C-D (12) | with {D} | [E] [A,F] [B,G] [C,D] |
| 4 | {E} | E-D (22) | with {C,D} | [A,F] [B,G] [C,D,E] |
| 5 | {A,F} | E-F (25) | with {C,D,E} | [B,G] [A,C,D,E,F] |
| 6 | {B,G} | B-C (16) | with {A,C,D,E,F} | [A,B,C,D,E,F,G] |
Six edges chosen, one tree remains.
MST edges: A-F (10), B-G (14), C-D (12), E-D (22), E-F (25), B-C (16). Minimum weight = 10 + 14 + 12 + 22 + 25 + 16 = 99.
A -10- F -25- E -22- D -12- C -16- B -14- G
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Spanning tree properties; Round Robin MST · Data Structure and Algorithm, chapter 10
- Kruskal's MST on 9-vertex graph · Data Structure and Algorithm, chapter 10 · asked 3×
- Kruskal's MST on 7-vertex graph · Data Structure and Algorithm, chapter 10 · asked 3×
- MST definition; Kruskal's MST on 6-vertex graph · Data Structure and Algorithm, chapter 10
- Kruskal's MST on graph A to G · Data Structure and Algorithm, chapter 10 · asked 3×
- B-tree of order 5 for 82, 12, 22, ... · Data Structure and Algorithm, chapter 6 · asked 2×
- Round robin scheduling (53, 17, 68, 24 ms) · Embedded System, chapter 6 · asked 4×
- Mat 18 m × 22 m, safe building weight · Foundation Engineering, chapter 7 · asked 2×