Jerry the mouse is trying to reach a piece of cheese located somewhere in a maze. The maze can be represented as a graph, where:

  • Each node is labeled with a letter and a number (for example: A1, D2, F3).

  • Edges represent paths between locations in the maze.

Jerry starts at node D2 and explores the maze using Depth-First Search (DFS).

When DFS needs to choose which neighbor to visit next, Jerry must follow one consistent ordering rule. However, he is not sure which rule will lead him to the cheese the fastest.

Jerry is considering the following four DFS neighbor ordering strategies:

  1. Order neighbors by the letter only, ascending (A → Z)

  2. Order neighbors by the letter only, descending (Z → A)

  3. Order neighbors by the number only, ascending (1 → 9)

  4. Order neighbors by the number only, descending (9 → 1)

Assume that when sorting neighbors, the ignored part of the label is not considered.

The cheese is located at node J2.





Which of the following alternatives has the shortest time (number of nodes visited) and correctly describes the DFS strategy used, the order of visited nodes, and the time until Jerry finds the cheese?

a) Strategy: Number descending. Visit order: D2 → B4 → A1 → G6 → H3 → C3 → I4 → J2 . Time to reach cheese: 8 .

b) Strategy: Number ascending. Visit order: D2 → F1 → G6 → A1 → B4 → E5 → I4 → J2 . Time to reach cheese: 8 .

c) Strategy: Letter descending. Visit order: D2 → F1 → G6 → H3 → C3 → I4 → J2 . Time to reach cheese: 7 .

d) Strategy: Letter ascending. Visit order: D2 → B4 → A1 → E5 → I4 → J2 . Time to reach cheese: 6 .

e) None of the above.


Original idea by: Matheus de Oliveira Saldanha

Comentários

  1. Joao Meidanis14 de março de 2026 às 06:22

    Nice question, but it can be confusing. The visit order in a DFS may not constitute a path.

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Imagem
Using the Breath-First-Search (BFS) algorithm, how many nodes have a distance of 1, 2 and 3 from node A, respectively? a) 2, 4, 3 b) 3, 3, 3 c) 3, 4, 2 d) 2, 3, 4 e) None of the above. Original idea by: Matheus de Oliveira Saldanha
Leia mais
Evaluate the following affirmations regarding planarity and planarity testing algorithms: I. A multi-graph is considered planar when it admits a plane drawing . II. To postulate Euler's formula ( $N-L+F=2$ ), one can start with a single node and observe        the  effect on $N$ , $L$ , and $F$ when adding a new node connected to an existing node, or when    adding a link between two existing nodes . III.  Kuratowski's Theorem states that a graph is planar if and only if it contains a subdivision (the process of replacing a link by a path) of $K_{3,3}$ or of $K_{5}$ , effectively making them mandatory subgraphs for planarity . IV. The pseudo-code for the DMP algorithm begins by starting with a single node and iteratively selects a fragment $B$ with the maximum number of faces $F(B)$ that contain all its vertices of attachment . V.  When using the DMP algorithm, a fragment of a graph $G$ with respect to a subgraph $H$ can be an...
Leia mais