Question

QUESTÃO 1
A busca em largura de baseia no conceito de fila, no qual para cada nó que está no início da fila, é preciso visitar todos os seus adjacentes, antes de verificar os adjacentes de um novo nó, de maneira recorrente. Observe o algoritmo BFS(), abaixo:



Assim sendo, aplique o algoritmo acima no grafo representado abaixo, considerando que a busca se inicia no vértice 1.



A sequência de visitação que corresponde à resposta correta é:
Alternativas
Alternativa 1:
1, 2, 5, 3, 4, 7, 6.

Alternativa 2:
1, 3, 2, 5, 4, 7, 6.

Alternativa 3:
1, 3, 4, 7, 6, 5, 2.

Alternativa 4:
1, 2, 3, 5, 4, 6, 7.

Alternativa 5:
2, 3, 4, 5, 6, 7.

Answer 1

Resposta:

Alternativa 4:

1, 2, 3, 5, 4, 6, 7.

Explicação:

Na fila o primeiro que entra é o primeiro que sai então a resposta será a mesma sequencia do desenfileiramento.

Enfileira o 1, como o 1 se liga ao 2 e ao 3, enfileira 2 e 3 ficando assim:

Fila: 1, 2, 3.

Desenfileirado:

Como o 1 não se liga a mais a ninguém desenfileira o 1 ficando assim:

Fila: 2, 3.

Desenfileirado: 1

Então o primeiro fica sendo o 2 que se liga apenas ao 5, então enfileira o 5 e desenfileira o 2 pois não se liga mais a ninguém ficando assim:

Fila: 3, 5.

Desenfileirado: 1, 2.

Então o primeiro se torna o 3 que se liga apenas ao 4, então enfileira o 4 e desenfileira o 3:

Fila: 5, 4.

Desenfileirado: 1, 2, 3.

O próximo é o 5 que se liga com o 6, enfileira o 6 e desenfileira o 5.

Fila: 4, 6.

Desenfileirado: 1, 2, 3, 5.

O próximo se torna o 4 que se liga apenas ao 7, após enfileirar o 7, como não há mais elementos para ligar desefileira os demais do inicio para o fim.

Fila:

Desenfileirados: 1, 2, 3, 5, 4, 6, 7.