mig1

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Você está jogando um jogo online chamado DotA. Percebendo que pode converter o mapa do jogo em um grafo com os vértices representando as posições no mapa e as arestas os caminhos até eles, você quer usar o algoritmo que acabou de aprender para navegar neste grafo.Considere o seguinte mapa do jogo convertido em um grafo:

                                                     

Suponha que você queira encontrar um caminho saindo do vértice 0 (zero) a fim de chegar no vértice 1 (um) passando por todas as posições no mapa ( vértices ). Anote a ordem em que os vértices são inseridos na fila de vértices ao executar o algoritmo de BFS para encontrar este caminho:

(a) 0-2-5-7-6-3-4-1

(b) 0-2-6-7-5-4-3-1

(c) 0-5-2-4-7-3-6-1

(d) 0-5-2-7-4-3-6-1

(e) NDA

Ideia original de: Lucas Miguel de Carvalho