O padrão em 30 segundos
Os grafos com peso: Dijkstra (menor caminho sem aresta negativa), Prim/Kruskal (árvore geradora mínima), union-find com compressão. A categoria também traz dois clássicos sem peso: ordenação topológica (Alien Dictionary) e caminho euleriano (Reconstruct Itinerary). Caem menos que BFS/DFS básico, mas separam pleno de sênior em processo mais puxado.
Como reconhecer na hora
- Arestas com CUSTO e "caminho mais barato" → Dijkstra com heap (com limite de K paradas, Bellman-Ford em K+1 rodadas)
- "Conectar todos os pontos com custo mínimo" → MST
- "Estão conectados?" repetido muitas vezes → union-find
Usar BFS simples em grafo com peso (só vale com peso uniforme), ou implementar Dijkstra sem heap e entregar O(V²) sem perceber. E não leve a regra da BFS pra cá: no Dijkstra o nó só é finalizado quando SAI do heap, não quando entra. Se a vaga é júnior/pleno, domine BFS/DFS primeiro; isso aqui é o polimento.
Complexidade típica: Dijkstra O((V+E) log V) com heap; union-find quase O(1) amortizado por operação.
Os 6 problemas da categoria
| Problema | Dificuldade | Nível no VagaGringa |
|---|---|---|
| Min Cost to Connect All Points | medium | nível 3 |
| Network Delay Time | medium | nível 3 |
| Cheapest Flights Within K Stops | medium | nível 3 |
| Reconstruct Itinerary | hard | nível 4 |
| Swim in Rising Water | hard | nível 4 |
| Alien Dictionary | hard | nível 4 · core |
No VagaGringa, esses 6 problemas entram numa trilha de 4 níveis com marcação do que mais cai em entrevista, e você registra tentativa, revisão e domínio de cada um.
Abrir a trilha NeetCode no app