Explore grafos com BFS e DFS
Modele problemas como grafos e busque neles sem revisitar nós.
- Representar um grafo com uma lista de adjacência ou uma grade.
- Escolher entre a busca em largura e a busca em profundidade.
- Contar componentes conectados e encontrar caminhos mais curtos.
Muitos problemas de entrevista são grafos disfarçados: grades de terra e água, pré-requisitos de cursos, escadas de palavras, redes sociais. Um grafo é um conjunto de nós mais arestas; no código, costuma ser uma lista de adjacência (um dict de nó para vizinhos) ou uma grade implícita, em que os vizinhos de cada célula são as de cima, de baixo, da esquerda e da direita. As duas buscas fundamentais visitam cada nó alcançável uma vez, em tempo O(V + E).
BFS versus DFS
- A busca em largura (BFS) usa uma fila e explora em anéis de distância crescente. Ela encontra o caminho mais curto num grafo sem pesos.
- A busca em profundidade (DFS) usa recursão ou uma pilha e segue um caminho o mais longe possível. Ela é natural para componentes conectados, detecção de ciclos e ordenação topológica.
- As duas precisam de um set de visitados (ou de marcar as células no próprio lugar) para que os nós não sejam processados duas vezes - caso contrário, os ciclos causam laços infinitos.
1from collections import deque
2
3graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": ["E"], "E": []}
4
5def shortest_steps(start, goal):
6 queue = deque([(start, 0)])
7 visited = {start}
8 while queue:
9 node, steps = queue.popleft()
10 if node == goal:
11 return steps
12 for neighbor in graph[node]:
13 if neighbor not in visited:
14 visited.add(neighbor)
15 queue.append((neighbor, steps + 1))
16 return -1
17
18print(shortest_steps("A", "E"))3
Para contar componentes conectados - como ilhas numa grade -, percorra todos os nós; sempre que encontrar um ainda não visitado, incremente a contagem e preencha (flood-fill) tudo o que é alcançável a partir dele com BFS ou DFS. Cada célula é visitada uma vez, então a varredura inteira é O(linhas × colunas).
Principais conclusões
Listas de adjacência e grades são as representações de grafo mais comuns.
BFS para caminhos mais curtos sem pesos; DFS para componentes, ciclos e ordenação.
Sempre acompanhe os nós visitados; as duas buscas são O(V + E).
Quiz da aula
5 perguntas · aprovação com 4 acertos · até 50 XP
Ao passar, você conclui a aula e mantém sua sequência. As perguntas erradas voltarão em sessões de revisão.
Pratique: resolva problemas de entrevistas técnicas
Resolva um problema clássico de entrevista em Python e execute-o com casos de teste. Busque a complexidade ideal e depois confira os casos extremos. Os exercícios rodam localmente no navegador.
Conte as ilhas
Leia o número de linhas e depois essa quantidade de linhas com 1 (terra) e 0 (água). Imprima o número de ilhas: grupos de células de terra ligadas para cima, para baixo, para a esquerda ou para a direita.
- Três ilhas
- Uma ilha
- Sem terra
O Python é executado em um ambiente isolado no navegador, com limite de 60 segundos. O runtime é carregado pelo CDN do Pyodide; seu código permanece neste navegador.
Dúvidas sobre esta lição
Travou em algum ponto? Pergunte. Descobriu algo? Compartilhe. Explicar também é uma ótima forma de aprender.
Carregando publicações…