Questão BFS/DFS

 

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

 

I.  During a BFS execution, three nodes that are already visited are verified (thus not being visited again);
II. There is one back edge in the graph;
III. If we remove the 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 

 

 

Comentários

  1. Joao Meidanis30 de agosto de 2025 às 15:15

    Boa questão. Alternativa correta é a E, certo?

    ResponderExcluir
    Respostas
    1. Giorgio Rossa30 de agosto de 2025 às 17:25

      Obrigado! Era para ser a C... Na I pelas minhas contas apenas 2 nós são checados novamente, e a DFS na IV só cria uma árvore.

      Excluir

Postar um comentário

Postagens mais visitadas deste blog

Push-relabel algorithm

Imagem
The following image illustrates a partially executed flow graph and the Push-Relabel algorithm, with the respective residual graph displayed on the right. The algorithm followed a FIFO order of selecting nodes and then selected nodes by alphabetical order when they were simultaneously activated. Active nodes are the ones that have excess in the pre-flow.  Based on the process illustrated, mark the correct alternative of the next step in the algorithm: a) Relabeling of ' c ', transforming 'h' to 2, and returning the excess flow to ' b ' using Push. b) Relabeling of ' a ', transforming 'h' to 8, and returning the excess flow to ' S ' using Push. c) Relabeling of ' c ', transforming 'h' to 8, and returning the excess flow to ' S ' using Push. d) Relabeling of ' e ', transforming 'h' to 1, and pushing the excess flow to ' t '. e) None of the above     Original idea  by: Giorgio Rossa
Leia mais

TSP Question

Imagem
The graph below shows the weight of each link between nodes. Considering that links not shown have infinite weight, find the correct alternative.  a) Using the Closest Neighbor heuristic, starting from node 'a'  will result in the cycle a-c-d-f-e-b-a, with a total cost of 19. b) Using the Closest Neighbor heuristic, any starting node will result in a total cost of 16. c) Using the Cheapest Insertion heuristic, starting from the cycle a-b-c-a will result in a final cost of 16. d) Using the Closest Neighbor heuristic, starting from node  'a'  will result in the cycle a-b-e-c-d-f-a, with a total cost of 16. e) None of the above.    Original idea  by: Giorgio Rossa
Leia mais