2026-325

You are analyzing a directed graph that represents a complex network of dependencies between software modules. You need to ensure the system is free of circular dependencies and find the minimum number of steps to reach a specific module from the source.

Based on the properties of Breadth-First Search (BFS) and Depth-First Search (DFS) presented in the course, which statement correctly identifies the best approach?

A) BFS should be used to find the minimum number of steps (length of a shortest path) because it provides parent links with a distance guarantee, while DFS is required to detect circular dependencies by identifying "back edges."

B) DFS should be used to find the shortest path because its "finishing times" represent the most efficient order, while BFS is the only tool capable of "edge classification" to find cycles.

C) In this directed graph, both BFS and DFS will naturally identify "forward" and "cross" edges, making them equally effective for topological sorting and cycle detection.

D) BFS is preferred for detecting cycles in undirected graphs because it lacks "forward edges," whereas DFS is preferred for shortest paths because it uses a stack to explore deep dependencies first.

E) None of the above.

Original idea by: Maria Luiza Ramos da Silva

2026-315

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

2025-255

A BFS was performed on an unknown graph, producing the following visitation order:

a-c-d-b-f-g-e-h

There are four candidate graphs:

I)

II)

III)

IV) 

Assuming that neighbors are always visited in ascending order, which of the graphs are valid candidates for the original graph?

a) I and II

b) I and III

c) II and IV

d) III and IV

e) None of the above

Original idea by: Pedro Zaffalon da Silva

2025-254

Analyze the statements below, knowing that DFS and BFS algorithms start at node "a" and the adjacency lists are sorted in alphabetical order.

 

I.  During the BFS execution, exactly three nodes that are already visited are verified (thus not being visited again);
II. There is just one back edge in the graph;
III. If we remove edges cd and ef, the resulting graph is a bipartite graph;
IV. The DFS execution would restart twice in this graph, creating two different trees;

The correct statements are: 

a) I and III

b) Only II

c) II and III

d) I, II and IV

e) None of the above

 

Original idea by: Giorgio Rossa

2025-253

Consider a graph 

$G=(V,E)$, and the Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms. Analyze the following statements:

I. In a DFS execution on a directed graph, the classification of edges as tree, forward, backward, and cross edges depends on the order in which vertices are explored.

II. In a BFS executed from a source vertex $s$ in an unweighted graph, the order in which vertices are discovered at the same level may vary depending on the order of edges in the adjacency list of the graph, but the minimum distance from each vertex to $s$ remains unchanged.

III. In directed graphs, a back edge detected during DFS indicates the presence of at least one cycle that includes the origin vertex of the edge.

IV. In undirected graphs, BFS can detect all cycles of length 3 (triangles), but it does not guarantee detection of larger cycles.

V. DFS guarantees that in a connected undirected graph, the tree generated contains exactly $\mathrm{\mid }V\mathrm{\mid }-1$ edges, independently of the presence of cycles.

Select the correct alternative:

A) Only I, II, and III are correct.
B) Only II, III, and IV are correct.
C) Only I, III, IV, and V are correct.
D) Only II, III, and V are correct.
E) None of the above.

Original idea by: Mateus de Padua Vicente

2024-237

John is a tourist from Minas Gerais who is on vacation and wants to explore the cities in UaiSo county. There are 3 main cities that he would like to visit: CheeseBreadLand, DulceDeLecheTown and TorresmoCity, that are painted in blue in the map. But John only moves following a BFS order, and he has time to visit 5 cities only. Help John optimize his trip so he can visit the most possible interesting cities. Consider that the BFS always chooses the neighbors in ascending order and the following map is an undirected graph. 

To visit the most cities he would like, what should John do?

a) John should start his trip on city 1, so he can visit 2 cities of interest.

b) John should start his trip on cities 4 or 9, so he can visit 2 cities of interest.

c) John should start his trip on city 3, so he can visit 3 cities of interest.

d) John should start his trip on city 2, so he can visit 2 cities of interest.

e) None of the above

Original idea by: João Vitor Baptista Moreira

2024-236

Given the undirected graph bellow:

What is the distance from A to all nodes in this graph?

a) A - 0, B - 1, C - 2, D - 1, E - 2, F - 3, H - 4, G - 0

b) A - 0, B - 1, C - 2, D - 1, E - 2, F - 2, H - 3, G - 4

c) A - 0, B - 1, C - 2, D - 1, E - 2, F - 2, H - 3, G - unreachable

d) A - 0, B - 1, C - 2, D - 1, E - 2, F - 3, H - 2, G - unreachable

e) None of the above

Original idea by: João Augusto

2022-159

Given the following oriented graph and applying two BFSs, one starting from node A (BFS-A), and the other starting at D (BFS-D), which of the following statements are true?


I.   BFS-A visits node D.
II.  The number of visited nodes in BFS-A is 5
III. BFS-D gets to visit all nodes in the graph.
IV. Deleting the red links reduces the number of visited nodes in BFS-D.

 

    A. Only II

    B. II and IV

    C. II, III and IV

    D. III and IV

    E. None of the above

    Original idea by: Victor Sotelo

2022-158

Concerning the Breadth First Search (BFS) algorithm with a queue, observe the oriented graph below, and assume that the adjacency lists are arranged in decreasing order.

Suppose you start a BFS in this graph from node 3.  Select the option representing the order of node numbers loaded into the queue during this operation.

1. 3 – 4 – 6 – 5 – 7 – 8 – 2 – 1 – 10
2. 3 – 6 – 5 – 4 – 8 – 7 – 2 – 1
3. 3 – 4 – 5 – 6 – 2 – 8 – 7 – 10 – 1
4. 3 – 6 – 5 – 4 – 8 – 7 – 2 – 1 – 10
5. None of the above.

Original idea by: Rubens de Castro Pereira

2022-157

Considering the following graph.

Which one of the following is a possible order for visiting the nodes using BFS?

1. QMNPRO
2. NQMPOR
3. MNOPQR
4. QMNPOR
5. None of the above

Original idea by: Rodrigo Bifulco

2022-156

Given the directed and unweighted graph below, and supposing that we start in node 1:

Which of the following items gives the information about the Furthest Node from 1 and one of the Shortest Paths to the furthest Node?

1. Furthest Node: 8 and Shortest Path: \( 1 \rightarrow 2 \rightarrow 4 \rightarrow 7 \rightarrow 8 \)
2. Furthest Node: 9 and Shortest Path: \( 1 \rightarrow 2 \rightarrow 6 \rightarrow 7 \rightarrow 9 \)
3. Furthest Node: 8 and Shortest Path: \( 1 \rightarrow 2 \rightarrow 6 \rightarrow 7 \rightarrow 8 \)
4. Furthest Node: 9 and Shortest Path: \( 1 \rightarrow 2 \rightarrow 4 \rightarrow 7 \rightarrow 8 \rightarrow 9 \)
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso

2022-155

The Breadth First Search (BFS) algorithm has been implemented using the queue. Which of the following is a best possible order of visiting the nodes in the graph below?

A. ABCDEF

B. ABCFDE

C. ABCFED 

D. EDFCBA

E. None of the above

Original idea by: Muhammad Idrees

2022-154

Given the unoriented graph below, indicate the correct distances from node 1 to each node different from 1, in the numerical ascending order of nodes. Tip: you may use the BFS algorithm.

 

 

 

 

 

1. 1, 2, 2, 3, 4, 4, 4
2. 1, 2, 2, 4, 4, 4, 4
3. 1, 1, 2, 2, 3, 3, 3
4. 2, 2, 3, 3, 3, 4, 4
5. None of the above.

Original idea by: André Nóbrega

2022-152

Consider the following graph. If there is a decision between multiple neighbor nodes in the Depth-First Search (DFS) or Breadth First-Search (BFS) algorithms, select the node with the smallest number.

In what order will the nodes be visited in both DFS and BFS algorithms starting at node 1?

1. DFS: 1 – 2 – 3 – 7 – 6 – 5 – 8 – 4  and  BFS: 1 – 2 – 4 – 5 – 3 – 7 – 8 – 6.
2. DFS: 1 – 2 – 3 – 5 – 8 – 7 – 6 – 4  and  BFS: 1 – 2 – 4 – 3 – 5 – 7 – 8 – 6.
3. DFS: 1 – 2 – 3 – 5 – 8 – 6 – 7 – 4  and  BFS: 1 – 2 – 4 – 3 – 5 – 7 – 6 – 8.
4. DFS: 1 – 2 – 3 – 5 – 8 – 6 – 7 – 4  and  BFS: 1 – 2 – 4 – 3 – 5 – 7 – 8 – 6.
5. None of the above.

Original idea by: Rubens de Castro Pereira