Analise a função BFS abaixo, que devolve o caminho mais curto (em número de saltos) entre dois vértices: from space collections space import space deq

Question

Analise a função BFS abaixo, que devolve o caminho mais curto (em número de saltos) entre dois vértices: from space collections space import space deque def space bfs_caminho left parenthesis garfo comma space origem comma space destino right parenthesis colon space space space space space space space fila space equals space deque left parenthesis left square bracket left square bracket origem right square bracket right square bracket right parenthesis space space space space space space space visitados space equals space set left parenthesis right parenthesis space space space space space space space while space fila colon space space space space space space space space space space space space space caminho space equals space fila. popleft left parenthesis right parenthesis space space space space space space space space space space space space space straight v space equals space caminho left square bracket negative 1 right square bracket space space space space space space space space space space space space space if space straight v space equals equals space destino colon space space space space space space space space space space space space space space space space space space space space return space caminho space space space space space space space space space space space space if space straight v space in space visitados colon space space space space space space space space space space space space space space space space space continue space space space space space space space space space space space space visitados. add left parenthesis straight v right parenthesis space space space space space space space space space space space space for space vizinho space in space grafo. get left parenthesis straight v comma space left square bracket right square bracket right parenthesis colon space space space space space space space space space space space space space space space space space space fila. append left parenthesis caminho space plus space left square bracket vizinho right square bracket right parenthesis grafo space equals space left curly bracket space space space space space space space space space " straight A " colon space left square bracket " straight B " comma space " straight C " right square bracket comma space space space space space space space space space " straight B " colon space left square bracket " straight D " comma space " straight E " right square bracket comma space space space space space space space space space " straight C " colon space left square bracket " straight F " right square bracket comma space space space space space space space space space " straight D " colon space left square bracket right square bracket comma space space space space space space space space space " straight E " colon space left square bracket " straight F " right square bracket comma space space space space space space space space space " straight F " colon space left square bracket right square bracket right curly bracket print left parenthesis bfs_caminho left parenthesis grafo comma space " straight A " comma space " straight F " right parenthesis right parenthesis Qual lista é impressa? a. ['A', 'B', 'E', 'F'] b. ['A', 'C', 'F'] c. ['A', 'B', 'D', 'F'] d. ['A', 'C', 'E', 'F'] e. ['A', 'E', 'F']

Ed · Answer

Vamos analisar a função BFS (Busca em Largura) e o grafo fornecido para determinar qual lista é impressa ao chamar `bfs_caminho(grafo, "A", "F")`.

O grafo é representado da seguinte forma:

- A: [B, C]
- B: [D, E]
- C: [F]
- D: []
- E: [F]
- F: []

Agora, vamos seguir o algoritmo BFS a partir do vértice "A":

1. **Início em "A"**: A fila começa com ["A"] e "A" é visitado.
2. **Explorando "A"**: Os vizinhos de "A" são "B" e "C". A fila agora contém ["B"], ["C"].
3. **Próximo vértice "B"**: A fila agora é ["B", "C"]. Visitamos "B" e seus vizinhos são "D" e "E". A fila agora contém ["C", "B", "D"], ["B", "E"].
4. **Próximo vértice "C"**: A fila agora é ["C", "B", "D", "E"]. Visitamos "C" e seu vizinho é "F". A fila agora contém ["B", "D", "E", "C", "F"].
5. **Próximo vértice "D"**: A fila agora é ["B", "D", "E", "C", "F"]. Visitamos "D", que não tem vizinhos.
6. **Próximo vértice "E"**: A fila agora é ["B", "E", "C", "F"]. Visitamos "E" e seu vizinho é "F". A fila agora contém ["C", "F"].
7. **Próximo vértice "F"**: A fila agora é ["C", "F"]. Visitamos "F", que é o destino.

O caminho mais curto encontrado é: ['A', 'B', 'E', 'F'].

Portanto, a alternativa correta é:
a) ['A', 'B', 'E', 'F'].

Cálculo

Respostas

Ainda com dúvidas?

Mais conteúdos dessa disciplina