Síntese: qual padrão usar?
Quatro padrões de grafo cobertos. Esta seção é o ápice do raciocínio DFS/BFS que vem desde Matriz e Árvore — aqui ele aparece na estrutura mais geral. Hora de treinar o reflexo de escolher a ferramenta.
A árvore de decisão da seção
1. Preciso PERCORRER / alcançar / contar grupos conectados?
├── alcançar / cobrir / "existe caminho?" → DFS ou BFS (com visitados)
├── caminho MAIS CURTO / menos passos → BFS
└── várias fontes ("tempo até alcançar tudo") → BFS MULTI-FONTE
2. Há DEPENDÊNCIAS / ordem ("X antes de Y") num grafo dirigido?
→ ORDENAÇÃO TOPOLÓGICA (Kahn) — também detecta ciclo
3. Preciso agrupar / "estão conectados?" / detectar ciclo (não-dirigido),
especialmente com arestas chegando aos poucos?
→ UNION-FIND
4. É um GRID? → trate como grafo (vizinhos = arestas) e use os mesmos DFS/BFS
E os reflexos da seção: sempre use visitados (grafos têm ciclos); construa a lista de adjacência a partir das arestas; e nomeie o Big-O como O(V + E).
O mapa completo da seção
| Padrão | Pergunta-chave | Tempo |
|---|---|---|
| DFS / BFS | "alcançar / contar componentes / clonar" | O(V + E) |
| BFS (mais curto) | "menor número de passos" | O(V + E) |
| Ordenação topológica | "ordem com dependências / tem ciclo?" | O(V + E) |
| Union-Find | "conectados? / ciclo / conexões dinâmicas" | ~O(V + E·α) |
| BFS multi-fonte | "tempo até alcançar tudo (grid)" | O(V + E) |
A ideia que une tudo: um grafo é nós + arestas, e quase tudo é uma travessia com visitados. DFS (fundo), BFS (camadas), topológica (por dependências), Union-Find (por grupos) — quatro formas de organizar essa travessia. Árvore, grid e lista ligada foram ensaios para isto.
Quiz da seção
Enunciados que você não viu nas aulas. Identifique o padrão e o porquê. 6+ acertos: pronto para a prova.
🧠 Quiz da seção: Grafos
0/71. 'Existe um caminho entre os nós A e B num grafo não-dirigido?' Qual padrão?
2. 'Qual a menor quantidade de transformações de uma palavra em outra, mudando uma letra por vez (cada passo válido no dicionário)?' Qual padrão?
3. 'Há n tarefas com dependências; existe uma ordem válida de execução?' Qual padrão?
4. 'Cidades vão sendo conectadas por estradas, uma a uma; após cada estrada, quantos grupos de cidades conectadas existem?' Qual padrão?
5. 'Distância de cada célula livre até a parede/porta mais próxima num grid.' Qual padrão?
6. 'Maior sequência de números consecutivos num array (ex.: [100,4,200,1,3,2] → 4, pois 1,2,3,4).' Como o pensamento de grupos ajuda?
7. Qual a ideia-mãe que une toda a seção — e a conecta com Matriz e Árvore?
Pronto para a prova?
A prova final da seção Grafos tem três problemas inéditos — fácil, médio e difícil — com casos ocultos. O difícil (Word Ladder) é uma BFS num grafo implícito de palavras: a confirmação de que você enxerga grafos mesmo onde eles não estão desenhados. As quatro aulas cobrem tudo que você precisa.
Boa prova! Volte para a página da seção e clique em "Prova final".