Percurso em Grafos

Esta simulação mostra como um computador explora um grafo. Os alunos escolhem a busca em largura (BFS) ou a busca em profundidade (DFS), definem o nó inicial e a velocidade, e acompanham os nós mudarem de cor conforme estão esperando, sendo processados ou visitados. Os indicadores mostram o número de visitados, o tamanho da fila ou da pilha e a ordem das visitas, e um botão gera um novo grafo aleatório. Rodar os dois métodos a partir do mesmo início mostra que a BFS se espalha em anéis enquanto a DFS mergulha fundo. Serve a aulas de computação sobre estruturas de dados e algoritmos.

• Execute a BFS a partir do nó 1 e leia o indicador Ordem de visita.
• Mude o Método para DFS com o mesmo Nó inicial e compare a ordem.
• Observe o indicador Tamanho da fila / pilha crescer e diminuir em cada método.
• Altere o Nó inicial e veja como todo o percurso muda.
• Pressione Gerar grafo novamente e preveja a ordem antes de executar.

1. 1Descreva como as buscas em largura e em profundidade exploram um grafo.
2. 2Distinga uma fila de uma pilha e associe cada uma a um método de busca.
3. 3Preveja a ordem de visita em um grafo pequeno.
4. 4Explique por que a BFS encontra rotas com o menor número de saltos.

Perguntas frequentes dos professores