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. 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
- "Conectar todos os pontos com custo mínimo" → MST
- "Estão conectados?" repetido muitas vezes → union-find
onde todo mundo erra · anotado no caderno
Usar BFS simples em grafo com peso (só vale com peso uniforme), ou implementar Dijkstra sem heap e entregar O(V²) sem perceber. 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 app |
|---|---|---|
| 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 app, 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