ITPEC FE Subject A April 2025 Question 6

A B D F E C — the official key follows a stack-based traversal that pushes each vertex's neighbours in ascending order.

The graph's edges are A–B, B–C, B–D, C–F, D–E and D–F. Push A, then repeatedly pop a vertex, visit it, and push its unvisited neighbours in ascending order, marking them as they are pushed:

• •Pop A, visit A; push B
• •Pop B, visit B; push C, then D
• •Pop D, visit D; push E, then F
• •Pop F, visit F; C is already on the stack, so nothing is pushed
• •Pop E, visit E; pop C, visit C

The visiting order is A, B, D, F, E, C.

Note on the key: ITPEC's official answer is (d), and that is what the exam scores. A recursive depth-first search that takes neighbours in ascending order visits A, B, C, F, D, E, which is not among the options. A recursive search cannot go from F to E while C is unvisited. Only the stack procedure above produces (d).

Answer (d)

Why not others:

• •(a) A B C D E F — plain alphabetical order; even a breadth-first search reaches F (through C) before E
• •(b) A B C D F E — the breadth-first order: B's neighbours C and D, then C's neighbour F, then D's neighbour E
• •(c) A B D E F C — takes D before C at B but E before F at D, so it follows no single neighbour order

Key rule: A depth-first traversal goes as deep as it can before backtracking, and a breadth-first traversal visits all neighbours first; with an explicit stack, neighbours pushed in ascending order come off in descending order.

Algorithm and Programming · AI-written, may contain errors