ITPEC FE Subject B October 2025 Question 9

The program implements BFS (Breadth-First Search). Key steps for traverse(1):

• •Start: enqueue vertex 1, mark visited[1] = true
• •Dequeue 1 → output 1. Row 1 of matrix: neighbors 2, 4 → enqueue both
• •Dequeue 2 → output 2. Row 2: neighbors 3, 5 (1 already visited) → enqueue both
• •Dequeue 4 → output 4. Row 4: neighbors 1, 5 — both already visited → nothing added
• •Dequeue 3 → output 3. Row 3: neighbor 2 — already visited → nothing added
• •Dequeue 5 → output 5. Row 5: neighbors 2, 4 — already visited → nothing added

Output order: 1, 2, 4, 3, 5

Why not others:
- a) 1,2,3,4,5 — wrong: vertex 4 is a direct neighbor of 1, so it enters the queue before 3
- b) 1,2,3,5,4 — wrong: 4 must come before 3 and 5
- d) 1,2,4,5,3 — wrong: 3 is enqueued before 5 (lower index processed first in row 2)
- e) 1,2,5,4,3 — wrong: 5 is not a direct neighbor of 1
- f) 1,4,5,2,3 — wrong: 2 is enqueued before 4 (lower index in row 1)

Key rule: In BFS with adjacency matrix, neighbors are added in ascending index order. The queue (FIFO) ensures level-by-level traversal. The output order depends on which vertex is dequeued first, not discovery order alone.

AI-generated — may contain errors