ITPEC FE Subject B October 2024 Question 9

Topic: Graph Traversal

From the answer group below, select the correct answer to be inserted into blank in the description. Here, the array indexes start at 1.

The procedure traverse traces through a vertex of the graph shown in the Figure, and outputs all vertex numbers in the graph. The vertex number of the graph is specified with the argument k. The global variable n indicates the number of vertices in the graph. The global array graph represents the graph in the figure. Each element graph[i][j] is equal to 1 if an edge exists between vertices i and j, and it is equal to 0 otherwise. The global array visited stores boolean values, where visited[i] indicates whether vertex i of the graph has been visited during the procedure.
When the procedure is called as traverse(1), the output is in the order blank.

12345

Figure Structure of the graph

[Program]
global: integer: n ← 5
global: integer [][]: graph ← {{0, 1, 0, 1, 0}, {1, 0, 1, 0, 1},
{0, 1, 0, 0, 0}, {1, 0, 0, 0, 1},
{0, 1, 0, 1, 0}}
global: boolean []: visited ← {false, false, false, false, false}
○ traverse(integer: k)
integer: i
visited[k] ← true
output k
for (increase i from 1 to n by 1)
if (graph[k][i] = 1 and visited[i] = false)
traverse(i)
endif
endfor

Answer group

Explanation

1, 2, 3, 5, 4 — depth-first: each call moves to its lowest-numbered unvisited neighbour and returns only when it has none left.

The matrix gives the edges 1–2, 1–4, 2–3, 2–5 and 4–5.

  1. traverse(1) outputs 1; its first unvisited neighbour is 2
  2. traverse(2) outputs 2; 1 is visited, so it calls traverse(3)
  3. traverse(3) outputs 3; its only neighbour 2 is visited, so it returns
  4. Back in traverse(2), graph[2][4] is 0 and graph[2][5] is 1, so it calls traverse(5), which outputs 5
  5. In traverse(5), 2 is visited and 4 is not, so traverse(4) outputs 4; when the calls return, the loop in traverse(1) finds 4 already visited

Answer (b)

Why not others:

  • •(a) — plain ascending order; 4 cannot follow 3, because 3's only neighbour is 2 and the search backs up to 2, whose next neighbour is 5
  • •(c) — breadth-first order (the neighbours of 1, then those of 2); the recursion goes deep before wide, so 3 is output before 4
  • •(d) — 4 is not a neighbour of 2, so it cannot come straight after 2; depth-first reaches 3 right after 2

Key rule: A recursive traversal with a visited array is depth-first: it finishes one branch completely before trying the next neighbour, taking neighbours in index order.

Graph Traversal · AI-written, may contain errors

Practice this exam

This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.