ITPEC FE Subject B October 2025 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 index starts at 1.

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

12345

Figure 1 Graph that is handled by the program

Here, the procedure traverse uses a queue represented by the class Queue. Figure 2 provides an explanation of the class Queue.

ConstructorDescription
Queue()Creates an empty queue.
MethodReturn valueDescription
enqueue(integer: elm)NoneAdds the integer elm as an element to the queue.
dequeue()integerExtracts the element from the queue and returns it.
isEmpty()booleanReturns true if the queue is empty; otherwise, returns false.

Figure 2 Explanation of the class Queue

[Program]
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}}
○ traverse(integer: k)
Queue: queue ← Queue()
boolean []: visited ← {false, false, false, false, false}
integer: v, i
queue.enqueue(k)
visited[k] ← true
while (not queue.isEmpty())
v ← queue.dequeue()
output v
for (increase i from 1 to 5 by 1)
if (graph[v,i] = 1 and visited[i] = false)
queue.enqueue(i)
visited[i] ← true
endif
endfor
endwhile

Answer group

Explanation

1, 2, 4, 3, 5 — the queue makes this a breadth-first traversal: every neighbour of a vertex is queued, in ascending vertex number, before any of theirs is output.

Row v of graph lists the neighbours of v: 1 has 2 and 4; 2 has 1, 3 and 5; 3 has 2; 4 has 1 and 5; 5 has 2 and 4. A vertex is marked visited when it is enqueued, so it enters the queue only once.

DequeuedOutputEnqueuedQueue after
112, 42, 4
223, 54, 3, 5
44none3, 5
33none5
55noneempty

Answer (c)

Why not others:

  • •(a) 1, 2, 3, 4, 5 — plain vertex order; 3 is only reached through 2, after 4 is already queued
  • •(b) 1, 2, 3, 5, 4 — depth-first order (follow 2 to 3, then to 5, before going back to 4), which needs recursion or a stack, not a queue
  • •(d) 1, 2, 4, 5, 3 — takes 5 before 3, but row 2 is scanned in ascending order, so 3 is queued first
  • •(e) 1, 2, 5, 4, 3 — outputs 5 ahead of 4, although 4 was queued earlier, by vertex 1
  • •(f) 1, 4, 5, 2, 3 — the order a stack (last in, first out) would give: 4, the last neighbour of 1 added, comes out first

Key rule: Breadth-first search outputs vertices in order of distance from the start, and within one distance in the order they were queued; with a stack in place of the queue, the same code becomes depth-first.

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.