DS & II

Capítulo 15 - Caminhamento em Grafos

Leitura de 4 min

🚀 Capítulo 15: Caminhamento em Grafos (BFS/DFS) (Tema: Indiana Jones)

NOTE

Este capítulo utiliza a temática de Indiana Jones para explicar o caminhamento em grafos. Explorar um templo perdido exige uma estratégia: ou você vai até o fundo de um túnel (DFS) ou explora as salas vizinhas primeiro (BFS)!

1. 🎯 Objetivo da Aula

Compreender os dois principais algoritmos de busca e caminhamento em grafos: Busca em Profundidade (DFS) e Busca em Largura (BFS), identificando suas diferenças e casos de uso.

2. 🏢 O Cenário Prático (Seu Desafio)

Indiana Jones entrou em uma pirâmide. O mapa das salas e túneis forma um grafo. Ele está na Sala A (Entrada) e quer encontrar a Sala com o Tesouro. Ele pode usar duas estratégias de exploração:

  1. Estratégia 1 (O Teimoso): Ele escolhe um túnel e vai andando por ele até não poder mais (batendo na parede ou num beco sem saída). Só então ele volta e tenta outro túnel.
  2. Estratégia 2 (O Precavido): Ele olha todas as portas da Sala A e dá um passo em cada uma. Depois, ele olha todas as portas das salas onde acabou de pisar. Ele se move como uma onda se espalhando.

Seu desafio é entender como o computador executa essas duas buscas!

3. 🧠 Fundamentos: A Teoria Traduzida

Percorrer um grafo significa visitar todos os vértices acessíveis a partir de um ponto inicial.

🕵️‍♂️ 1. DFS (Depth-First Search) - Busca em Profundidade

É a estratégia do “Teimoso”. O algoritmo avança o máximo possível ao longo de cada ramo antes de retroceder (backtracking).

  • Como funciona: Usa uma Pilha (Stack) para lembrar de onde veio.
  • Uso: Resolver labirintos, jogos de xadrez (prever jogadas futuras até o fim).

🌊 2. BFS (Breadth-First Search) - Busca em Largura

É a estratégia do “Precavido”. O algoritmo explora os vizinhos do nó inicial primeiro, depois os vizinhos dos vizinhos.

  • Como funciona: Usa uma Fila (Queue) para organizar a ordem de visita.
  • Uso: Encontrar o caminho mais curto (Ex: GPS), redes sociais (amigos de 1º grau, 2º grau).

4. 📖 Exemplo Guiado: O Mapa do Templo

graph TD
    A((Sala A)) --> B((Sala B))
    A --> C((Sala C))
    B --> D((Sala D))
    C --> E((Sala E))
  • Na busca DFS: A ordem de visita seria A -> B -> D (vai até o fundo) e depois volta para C -> E.
  • Na busca BFS: A ordem de visita seria A -> B -> C (primeiro nível) e depois D -> E (segundo nível).

5. 🛠️ Prática Obrigatória 1: Simulando o Caminho

Com base no exemplo guiado, se o tesouro estivesse na Sala C:

  1. Qual busca (DFS ou BFS) encontraria o tesouro fazendo menos passos?
  2. E se o tesouro estivesse na Sala D?

6. 🛠️ Prática Obrigatória 2: GPS e Redes Sociais

Qual algoritmo (BFS ou DFS) o Google Maps usa para encontrar o caminho mais curto entre a sua casa e a escola? Por quê? (Dica: Pense em qual deles se espalha em círculos ao redor do ponto de partida).

7. 📤 Instruções de Entrega (GitHub Desktop + Microsoft Teams)

  1. Faça o Commit: No GitHub Desktop, digite a mensagem (ex: Finaliza Capítulo 15 Estruturas de Dados) e clique em Commit to main.
  2. Envie para a Nuvem (Push): Clique em Push origin.

8. 📂 Estrutura de Pastas

mod_09_estruturas_de_dados/
├── capitulos/
│   ├── capitulo_15_caminhamento.md
│   └── codigos/
│       └── cap15/
│           └── busca_templo.js

9. 💡 Checkpoint de Lógica

Se um grafo tiver um ciclo (um caminho que volta para o início), o que acontece com os algoritmos DFS e BFS se não marcarmos os nós que já foram visitados? (Dica: Eles vão parar de rodar algum dia?).

10. 🔥 Desafio de Fixação

Pesquise o que é o Algoritmo de Dijkstra e como ele melhora a busca BFS para encontrar o caminho mais curto em grafos com pesos (distâncias).

🔑 Gabarito de Código/Fórmulas

Gabarito da Prática 1:

  1. Para a Sala C, o BFS acharia primeiro (visita A, depois B, depois C). O DFS iria até o fundo do ramo B (A->B->D) antes de tentar o C.
  2. Para a Sala D, o DFS acharia primeiro (A->B->D), enquanto o BFS passaria por C antes de chegar em D.

← Capitulo Anterior | Proximo Capitulo →

Visão de gráfico

Backlinks