Padrão 1: DFS e BFS com visitados
As duas travessias que você já viu em Matriz e Árvore agora aparecem na sua forma mais geral. A única novidade em relação à árvore: como grafos têm ciclos, o conjunto de visitados deixa de ser opcional — é o que evita rodar para sempre.
Tente primeiro: Number of Connected Components
Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.
Há n nós (numerados de 0 a n-1) e uma lista de edges (arestas não-dirigidas). Retorne o número de componentes conexos (grupos de nós ligados entre si).
Exemplo: n = 5, edges = [[0,1],[1,2],[3,4]] → 2 (o grupo {0,1,2} e o grupo {3,4}).
Tentou? A ideia central: cada vez que você encontra um nó ainda não visitado, ele inicia um novo grupo — e uma busca (DFS/BFS) a partir dele marca todo o grupo. A teoria abaixo formaliza isso.
A teoria: percorrer marcando visitados
DFS (profundidade): vá o mais fundo possível por um caminho, recuando quando travar. Recursivo e curto:
dfs(no):
marque no como visitado
para cada vizinho de no:
se não visitado: dfs(vizinho)
BFS (largura): explore em camadas, com uma fila:
fila = [origem]; marque origem
enquanto a fila não está vazia:
no = desenfileira
para cada vizinho de no:
se não visitado: marque e enfileire
Os dois visitam todos os nós alcançáveis a partir da origem, em O(V + E). A diferença é a ordem (fundo vs camadas) — e a escolha segue o mesmo critério da Matriz: BFS para caminho mais curto; DFS para "alcançar / cobrir / existe". Compare as ordens no mesmo grafo:
Contar componentes conexos
Um grafo pode ter vários "pedaços" desconexos. Para contá-los: percorra todos os nós; cada nó ainda não visitado inicia um novo componente (+1), e uma busca a partir dele marca todo o pedaço. É o mesmo raciocínio do "contar ilhas" (Matriz!), agora num grafo geral. O(V + E) de tempo.
Exemplo: Clone Graph (DFS com um mapa)
"Copie um grafo inteiro (nós e arestas), criando objetos novos." O desafio:
ao seguir as arestas, você reencontra nós já copiados (por causa dos ciclos) —
e não pode copiá-los de novo. A solução: um mapa original → cópia, e
registrar a cópia antes de recursar nos vizinhos (senão, um ciclo causa
recursão infinita):
O mapa serve de duas coisas ao mesmo tempo: memória do que já foi clonado (evita duplicar) e detector de visitados (evita o ciclo infinito). Mudar o original depois prova que a cópia é mesmo independente.
🧠 Quiz de fixação
0/41. Por que o conjunto de visitados é OBRIGATÓRIO em grafos, mas não era em árvores?
2. Para contar componentes conexos, qual é a estratégia?
3. No Clone Graph, por que registrar a cópia no mapa ANTES de recursar nos vizinhos?
4. DFS e BFS num grafo visitam os mesmos nós. Como escolher entre eles?
Resumo
- DFS (fundo, recursão) e BFS (camadas, fila) percorrem o alcançável em O(V+E), sempre com visitados.
- Componentes conexos: cada nó não visitado inicia uma busca = +1 componente.
- Clone Graph: mapa
original → cópiaregistra antes de recursar (corta ciclos e evita duplicar).
Próxima aula: ordenar tarefas com dependências — ordenação topológica.