Grafos e travessia BFS/DFS

Explorar um labirinto: duas estratégias

Imagine explorar um labirinto. A estratégia BFS (Breadth-First Search) é como jogar pedras: você espalha pedras em todas as direções ao mesmo tempo, atingindo primeiro os corredores mais próximos da entrada, depois os mais distantes. O caminho mais curto até a saída é garantido pelo BFS.

A estratégia DFS (Depth-First Search) é como rolar um fio: você escolhe um corredor, vai até o fundo, volta se não há saída, e tenta o próximo. Você pode demorar mais para achar a saída, mas explora caminhos completos antes de mudar de rota — ideal para detectar se a saída existe de alguma forma.

BFS vs DFS no mesmo grafo

Alterne entre BFS e DFS e avance passo a passo. Observe como a ordem de visita muda completamente — BFS vai nível por nível, DFS vai fundo antes de voltar.

Representação e BFS

# Representações de grafo em Python

# 1. Lista de adjacência (mais comum — eficiente para grafos esparsos)
grafo = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F", "G"],
    "D": [], "E": [], "F": [], "G": []
}

# 2. Matriz de adjacência (útil para grafos densos e Floyd-Warshall)
# grafo[i][j] = 1 se há aresta de i para j, 0 caso contrário
# Custo: O(n²) espaço — ruim para grafos grandes e esparsos

# BFS — Busca em Largura — O(V + E)
from collections import deque

def bfs(grafo, inicio):
    visitados = {inicio}
    fila = deque([inicio])
    ordem = []
    while fila:
        no = fila.popleft()    # desenfila da frente
        ordem.append(no)
        for vizinho in grafo[no]:
            if vizinho not in visitados:
                visitados.add(vizinho)
                fila.append(vizinho)
    return ordem           # A B C D E F G (nível por nível)

DFS e quando usar cada um

# DFS — Busca em Profundidade — O(V + E)

# Versão recursiva (mais elegante)
def dfs(grafo, no, visitados=None):
    if visitados is None: visitados = set()
    visitados.add(no)
    resultado = [no]
    for vizinho in grafo[no]:
        if vizinho not in visitados:
            resultado += dfs(grafo, vizinho, visitados)
    return resultado       # A B D E C F G (vai fundo antes de voltar)

# Aplicações de BFS vs DFS:
#
# BFS — ideal para:
#   ✓ Caminho mais curto (grafo sem pesos)
#   ✓ Verificar conectividade por níveis
#   ✓ Web crawling (explorar por camadas)
#
# DFS — ideal para:
#   ✓ Detectar ciclos
#   ✓ Ordenação topológica
#   ✓ Explorar labirintos / paths completos
#   ✓ Componentes conectados

Grafos na prática

Mini projeto: implemente BFS para encontrar o caminho mais curto em um labirinto representado como uma grade 2D (lista de listas). Cada célula é "." (livre) ou "#" (parede). Retorne a menor sequência de movimentos do ponto S ao ponto E. Dica: trate cada célula como um vértice do grafo; as arestas são os 4 vizinhos cardeais.

Projeto principal: implemente o algoritmo de Dijkstra para encontrar o caminho mais curto em um grafo ponderado. Entrada: dicionário de adjacência com pesos {"A": [("B", 4), ("C", 2)]}. Use uma heap (heapq) para processar sempre o nó de menor custo acumulado. Teste com uma rede de cidades e calcule a rota mais barata entre pares.

Desafio extra: implemente detecção de ciclos usando DFS. Um grafo direcionado tem ciclo se, durante o DFS, você visita um nó que já está na pilha de chamadas ativa (não apenas visitado — visitado mas já removido da pilha é OK). Implique isso para verificar dependências circulares em um sistema de pacotes (como pip faz ao instalar dependências).

Teste sua intuição

Onde você encontra isso