Grafos: BFS e DFS explicados com exemplos práticos em Python

Grafos são uma das estruturas de dados mais poderosas e universais da ciência da computação. Redes sociais (usuários = nós, amizades = arestas), mapas e GPS (cidades = nós, estradas = arestas com pesos), a internet (servidores = nós, cabos = arestas), sistemas de recomendação, compiladores, jogos — todos modelam seus dados como grafos. Os dois algoritmos fundamentais de exploração de grafos são BFS (Busca em Largura) e DFS (Busca em Profundidade), e dominar ambos abre as portas para resolver dezenas de problemas importantes.

Representação de grafo: lista de adjacências

A forma mais comum e eficiente de representar grafos em código é a lista de adjacências — um dicionário onde cada chave é um nó e o valor é a lista de vizinhos:

# Grafo não-direcionado como lista de adjacências
grafo = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"]
}
#
#     A
#    / 
#   B   C
#  /    
# D   E - F

BFS (Busca em Largura) — usando fila

BFS explora o grafo nível por nível: primeiro todos os vizinhos diretos do nó inicial, depois os vizinhos dos vizinhos, e assim por diante. Usa uma fila para controlar a ordem de visita. Propriedade chave: BFS sempre encontra o menor caminho (em número de arestas) entre dois nós em grafos não-ponderados.

from collections import deque

def bfs(grafo, inicio, destino):
    """
    Retorna o menor caminho (em arestas) de inicio até destino.
    """
    fila = deque([(inicio, [inicio])])
    visitados = {inicio}

    while fila:
        no_atual, caminho = fila.popleft()

        if no_atual == destino:
            return caminho  # Encontrou o destino!

        for vizinho in grafo[no_atual]:
            if vizinho not in visitados:
                visitados.add(vizinho)
                fila.append((vizinho, caminho + [vizinho]))

    return None  # Não há caminho

caminho = bfs(grafo, "A", "F")
print(caminho)  # ['A', 'C', 'F'] — o menor caminho

DFS (Busca em Profundidade) — usando pilha/recursão

DFS vai o mais profundo possível em cada ramo antes de retroceder. Pode ser implementada com recursão (usando o call stack como pilha implícita) ou com uma pilha explícita. Útil para: detectar ciclos, encontrar componentes conexos, topological sort, labirintos.

def dfs(grafo, inicio, visitados=None):
    """
    DFS recursivo — visita todos os nós acessíveis a partir de inicio.
    """
    if visitados is None:
        visitados = set()

    visitados.add(inicio)
    print(inicio, end=" ")

    for vizinho in grafo[inicio]:
        if vizinho not in visitados:
            dfs(grafo, vizinho, visitados)

    return visitados

dfs(grafo, "A")  # A B D E F C (ordem possível — DFS não tem ordem única)

Aplicação prática: detectar ciclo em grafo direcionado

def tem_ciclo(grafo):
    """Detecta ciclo em grafo direcionado usando DFS com 3 estados."""
    BRANCO, CINZA, PRETO = 0, 1, 2
    cor = {no: BRANCO for no in grafo}

    def dfs_ciclo(no):
        cor[no] = CINZA  # Em processamento
        for vizinho in grafo.get(no, []):
            if cor[vizinho] == CINZA:  # Encontrou aresta de volta = ciclo!
                return True
            if cor[vizinho] == BRANCO and dfs_ciclo(vizinho):
                return True
        cor[no] = PRETO  # Finalizado
        return False

    return any(dfs_ciclo(no) for no in grafo if cor[no] == BRANCO)

BFS vs DFS: quando usar cada um

Use BFS quando: quer o menor caminho (em arestas) entre dois nós, quer explorar por níveis/camadas, ou o destino está próximo do ponto de partida. Use DFS quando: quer verificar conectividade ou detectar ciclos, precisa de ordenação topológica, está resolvendo labirintos/puzzles com backtracking, ou o destino provavelmente está no fundo da árvore. Para grafos ponderados (arestas com custos diferentes), o algoritmo de Dijkstra encontra o caminho de menor custo — é o próximo passo natural após dominar BFS e DFS.