2026-326

Consider the graph on the figure below. Determine the number of back edges, cross edges, and forward edges generated by the Depth-First Search (DFS) algorithm. Assume the algorithm visits neighboring vertices in ascending order.

A) 2 back edges, 4 cross edges, and 2 forward edges. 

B) 2 back edges, 5 cross edges, and 1 forward edge.

C) 1 back edge, 4 cross edges, and 2 forward edges.

D) 1 back edge, 5 cross edges, and 2 forward edges.

E) None of the above.

Original idea by: Melissa Araújo.

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.

Original idea by: Maria Luiza Ramos da Silva

2026-324

Consider the DFS time diagram below, which represents the starting and finishing times in a DFS call. Which of the graphs shown in the alternatives could produce it? 

a)                                                                      b)

             

c)                                                                       d) 

           

e) None of the above

Original idea by: Ingrid Barbosa

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-232

Given the following directed graph:

Which sequence represents a valid depth-first search (DFS) traversal order that involves only one tree?

A. a-d-b-f-c-e

B. a-d-f-b-e-c

C. e-c-d-f-b-a

D. c-d-b-a-f-e

E. None of the above

Original idea by: Darlinne Hubert Palo Soto

2024-231

How does a Depth-First Search (DFS) provide a topological sort ?

A) Sorting nodes by finishing time, in ascending order

B) Selecting nodes in a random order

C) Visiting nodes in alphabetical order

D) Sorting nodes by finishing time, in descending order

E) None of the above

Original idea by: Cinthia Kleiner

2024-230

 

Given the curriculum chart for the Computer Engineering course above, a student needs to schedule which subjects should be taken.  Which of the options below indicates the topological sort order obtained by taking the reverse order of finishing times in a particular DFS, where nodes are selected in alphabetical/numerical order in the main loop and also in the adjacency lists:

a) LA -> CEI -> DC1 -> DC2 -> C1 -> C2 -> C3 -> SP -> A1 -> A2

b) LA -> CEI -> DC1 -> DC2 -> A1 -> A2 -> C1 -> C2 -> C3 -> SP

c) C1 -> CEI -> C2 -> LA -> A1 -> DC1 -> C3 -> A2 -> DC2 -> SP

d) CEI -> C1 -> DC1 -> A1 -> LA -> C2 -> DC2 -> A2 -> C3 -> SP

e) None of the above

Original idea by: Matheus Lindino

2024-229

During a Depth-First Search (DFS) on a directed graph G, the following edges are traversed:

• Edge (u, v), where v has already been visited and fully explored.
• Edge (x, y), where y has been visited but not fully explored yet.
• Edge (a, b), where b has been fully explored, but belongs to a different branch from a in the DFS tree.

Of course, each edge is traversed when it origin node is being explored.  Which of the following options correctly classifies these edges according to their type in a DFS traversal?

A) (u, v) is a forward edge, (x, y) is a back edge, (a, b) is a back edge.

B) (u, v) is a cross edge, (x, y) is a forward edge, (a, b) is a tree edge.

C) (u, v) can be a forward or cross edge, (x, y) is a back edge, (a, b) is a cross edge.

D) (u, v) is a back edge, (x, y) is a cross edge, (a, b) is a forward edge.

E) None of the above

Original idea by: Sergio Sanchez

2023-203

Given the following adjacency matrix that represents a directed graph (a '1' in row \(x\) and column \(y\) means a directed link \(x \rightarrow y\)), apply a topological sort using Depth First Search (DFS) and determine the start and finish times for each node. Start from node 'a' and always prioritize visiting nodes in alphabetical order.

	\(a\)	\(b\)	\(c\)	\(d\)	\(e\)	\(f\)	\(g\)
\(a\)	0	1	0	0	0	0	0
\(b\)	0	0	1	0	1	0	0
\(c\)	0	0	0	1	0	0	0
\(d\)	0	0	0	0	1	0	1
\(e\)	0	0	0	0	0	1	0
\(f\)	0	0	0	0	0	0	0
\(g\)	0	0	0	0	0	1	0

1. a(1,14); b(2,13); c(3,12); d(4,11); e(5,10); f(6,7); g(5,8)
2. a(1,14); b(2,13); c(3,12); d(4,11); e(5,7); f(6,9); g(8,10)
3. a(1,14); b(2,13); c(3,12); d(4,11); e(5,10); f(7,8); g(6,9)
4. a(1,14); b(2,13); c(3,12); d(4,11); e(5,8); f(6,7); g(9,10)
5. None of the above

Original idea by: Thaysa Bello

2023-202

Consider the following statements regarding the graph below, where a DFS algorithm was run, starting at A.  Assume the adjacency lists are in alphabetical order. 

 

 

 

I. Edge 4 is a forward edge.

II. Edge 11 is the only cross edge.

III. There are 8 tree edges.

 

Which of the alternatives below is correct?

(A)  Only I and II are correct.

(B) Only II and III are correct.

(C) Only I is correct.

(D) Only III is correct.

(E) None of the above. 

 

Original idea by: Raysa Masson Benatti 

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

2022-151

Pedro has been given several tasks to do. But instead of a list with the order of the tasks, his supervisor gave him a graph where edges that go from node A to B mean that task B depends on task A. Unfortunately, Pedro does not know how to use this information from the graph, so he doesn't know which tasks to do first. The graph his supervisor provided was:

As a specialist in graphs, you were chosen to help Pedro with ordering the tasks he needs to do. His supervisor said to him to always prioritize the task with the smallest label when there is a choice. Knowing the constraints, which order should Pedro follow?

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

  Original idea by: Pedro Henrique Di Francia Rosso

2022-150

How many topological orderings exist in  the graph given below?

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

Original idea by: Meer Muhammad Khan

2022-149

Given the following directed graph, if DFS is started from vertex 0 for an implementation in which the adjacency lists are in sorted order, then what is correct to affirm regarding edge classifications:

A. {a, b, c, d} are tree-edges; 

    {g, h} are forward-edges;

    {e, f} are back-edges;

    {i} is a cross-edge

B. {b, e, d, i, j, c} are tree-edges; 

     {g} is a forward-edge; 

     {a} is a back-edge; 

     {h} is a cross-edge;

C. {a, b, c, g} are tree-edges; 

    {d, h} are forward-edges;

    {e, f} are back-edges;

    {i} is a cross-edge;

D. {a, b, c, d} are tree-edges; 

    {g, h} are forward-edges;

    {e, i} are back-edges;

    {f} is a cross-edge

E. None of the above

Original idea by: Marcelo Silva

2022-148

Given the network of Figure 1, which alternative does not describe a possible topological sorting of this graph?

Fig. 1. Network.

1. A, C, G, E, D, H, B, F
2. E, A, G, C, B, D, H, F
3. A, B, C, D, E, G, H, F
4. G, A, C, E, B, H, D, F
5. None of the above.

Original idea by: Gabriel Oliveira

2022-147

Consider the Active Time Diagram defined below. The rows, \( a \) to \( e \), represent the nodes of a network. The columns, 1 to 10, represent the star and ending times of the nodes during a given DFS Algorithm, which starts at node \( a \) and proceeds through the network. So, the horizontal bar at row \( a \) indicates that node \( a \) has starting time 1 and ending time 10, delimiting the time it is active, and so on for the others.

Based on this diagram, we are able to infer some information on Edge Classification, as follows:

1. Edges \( d \rightarrow c \) and \( e \rightarrow d \) are cross-edges.
2. Edges \( a \rightarrow c \) and \( a \rightarrow e \) are forward-edges.
3. Edge \( c \rightarrow a \) is a backward-edge.

Given the above statements, which of them are true:

1. I and II.
2. I and III.
3. II and III.
4. I, II and III.
5. None of the above.

Original idea by: Fábio Assunção.

2022-146

A truck driver from a food supply company has to visit several cities to make deliveries. However, he must visit some cities before others, in order to pick up important items. These precedence requirements are shown as the edges in the graph below. Whci alternative shows a topological order of cities?

 

 

 

 

1. São José do Rio Preto, Ribeirão Preto, Araçatuba, Bauru, Campinas, São Carlos, Andradina, Mococa
   
2. São Carlos, Andradina, Araçatuba, Bauru, Campinas, Mococa, São José do Rio Preto, Ribeirão Preto
3. São José do Rio Preto, Ribeirão Preto, São Carlos, Andradina, Araçatuba, Bauru, Campinas, Mococa
4. Andradina, São José do Rio Preto, Araçatuba, Bauru, São Carlos, Ribeirão Preto, Mococa, Campinas
5. None of the above.

Original idea by: André Nóbrega