---
title: "Round Robin MST on 7-vertex graph"
subject: "Data Structure and Algorithm"
chapter: 10
key: "semester_4/data_structure_and_algorithm:round-robin-mst-graph-l"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/round-robin-mst-graph-l
site: BCT Engineering
---

# Round Robin MST on 7-vertex graph

Data Structure and Algorithm · Chapter 10: Graphs

- Asked in: 2069 Poush, 4 marks
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/round-robin-mst-graph-l
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-10

## Question

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]

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

## Answer

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

```text
A -10- F -25- E -22- D -12- C -16- B -14- G
```

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. In Round Robin, which edge is used when tree T is taken from the front of the queue?
   A. The maximum-weight edge leaving T
   B. Any edge inside T
   C. The edge with the smallest label
   D. The minimum-weight edge leaving T
   Answer: D. T is merged using its cheapest edge to a different tree. (Key point: Round Robin merging)

2. Starting with {A}, which merge happens first?
   A. A with F using edge 25
   B. A with G using edge 14
   C. A with B using edge 28
   D. A with F using edge 10
   Answer: D. A's edges are A-B 28 and A-F 10; the cheapest is A-F. (Key point: Step 1 result)

3. When {E} is taken, with {C,D} merged already, why is E-D (22) chosen?
   A. It is the only edge at E
   B. E-D has the highest weight
   C. It is the cheapest edge leaving E (E-G 24, E-F 25 are heavier)
   D. Edges to larger trees are always preferred
   Answer: C. E's edges are E-G 24, E-D 22, E-F 25; 22 is the minimum, joining E with {C,D}. (Key point: Step 4 choice)

4. When does the algorithm stop, and what is the MST weight here?
   A. After 7 merges; weight 99
   B. When one tree remains; weight 99
   C. When one tree remains; weight 115
   D. When the queue is empty of single vertices; weight 90
   Answer: B. With 7 vertices, 6 merges leave one tree; 10+14+12+22+25+16 = 99. (Key point: End condition and cost)

## Related in Data Structure and Algorithm

- [Spanning tree properties; Round Robin MST](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aspanning-tree-properties-round-robin) — Data Structure and Algorithm, chapter 10
- [Kruskal's MST on 9-vertex graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Akruskal-mst-graph-f) — Data Structure and Algorithm, chapter 10, asked 3×
- [Kruskal's MST on 7-vertex graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Akruskal-mst-graph-74) — Data Structure and Algorithm, chapter 10, asked 3×
- [MST definition; Kruskal's MST on 6-vertex graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amst-definition-kruskal-graph-i) — Data Structure and Algorithm, chapter 10
- [Kruskal's MST on graph A to G](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Akruskal-mst-graph-d) — Data Structure and Algorithm, chapter 10, asked 3×
- [B-tree of order 5 for 82, 12, 22, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-order5-82-12-22) — Data Structure and Algorithm, chapter 6, asked 2×

## Related in other subjects

- [Round robin scheduling (53, 17, 68, 24 ms)](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Asched-rr-53-17-68-24-q4) — Embedded System, chapter 6, asked 4×
- [Mat 18 m × 22 m, safe building weight](https://www.bctengineer.com/question.md?key=semester_5%2Ffoundation_engineering%3Amat-18x22-clay-ucs75) — Foundation Engineering, chapter 7, asked 2×