ITPEC FE Subject B October 2024 Question 9

Tracing DFS traversal order using an adjacency matrix.

This is a standard DFS (Depth-First Search) implemented with an adjacency matrix. The procedure traverse(k) marks vertex k as visited, outputs it, then recursively visits all unvisited neighbors in index order.

Adjacency matrix (rows 1–5):

Step-by-step trace of `traverse(1)`:

1. traverse(1): output 1, neighbors: 2, 4. First unvisited = 2 → call traverse(2)
2. traverse(2): output 2, neighbors: 1, 3, 5. Vertex 1 visited. First unvisited = 3 → call traverse(3)
3. traverse(3): output 3, neighbors: 2. Vertex 2 visited. Return to traverse(2)
4. Back in traverse(2): continue loop. i=4: graph[2][4]=0 (no edge). i=5: graph[2][5]=1, unvisited → call traverse(5)
5. traverse(5): output 5, neighbors: 2, 4. Vertex 2 visited. Vertex 4 unvisited → call traverse(4)
6. traverse(4): output 4, neighbors: 1, 5. Both visited. Return.

Result: 1, 2, 3, 5, 4 → (b)

Why not others:
- (a) 1, 2, 3, 4, 5 — vertex 4 is not directly reachable from 3 (no edge graph[3][4]), so 4 cannot come right after 3
- (c) 1, 2, 4, 3, 5 — vertex 4 is not a neighbor of vertex 2 (graph[2][4]=0), so DFS from 2 cannot visit 4 before 3
- (d) 1, 2, 4, 5, 3 — same issue: no edge between 2 and 4, so 4 cannot follow 2

Key rule: In DFS with an adjacency matrix, neighbors are visited in ascending index order — always trace the loop i from 1 to n carefully to determine the exact order.

AI-generated — may contain errors