DFS e BFS em Grafos

A única linha nova

Aqui está o DFS de grafo, e a diferença para o de árvore cabe numa linha:

def dfs(u, g, visitados):
    if u in visitados:      # <- não existe em árvore
        return
    visitados.add(u)
    processa(u)
    for v in g[u]:
        dfs(v, g, visitados)

Numa árvore, cada nó tem um pai só e nunca existe caminho de volta, então você nunca chega duas vezes no mesmo lugar. Num grafo, um ciclo simples como A → B → C → A faz a recursão girar para sempre.

O conjunto de visitados também é o que garante o custo. Cada vértice entra uma vez e cada aresta é olhada uma vez (duas em grafo não dirigido), então os dois percursos custam O(V + E) de tempo. Não O(V²): a soma dos graus de todos os vértices é 2E, e é isso que você percorre.

Pilha ou fila, e o que muda

As duas versões iterativas são o mesmo código com uma palavra trocada:

pilha = [inicio]
while pilha:
    u = pilha.pop()      # último que entrou
    ...

fila = deque([inicio])
while fila:
    u = fila.popleft()   # primeiro que entrou
    ...

pop() contra popleft(). Só isso separa dois algoritmos com propriedades completamente diferentes.

Rode o BFS primeiro no grafo com ciclo e acompanhe a coluna de distância. Depois rode o DFS no mesmo grafo e compare: os dois visitam os sete vértices, mas o DFS chega no C com distância 3, enquanto o BFS chega com 2. Os dois caminhos existem; só o BFS garante achar o curto.

Repare também nos passos em que o percurso encontra um vizinho já visitado e simplesmente o ignora. É o ciclo sendo cortado ao vivo. E troque para o preset desconexo: partindo de A, quatro vértices ficam em infinito, o que mostra que um percurso só não cobre o grafo inteiro.

Por que o BFS acha o caminho mais curto

Esta é a propriedade que faz o BFS aparecer em metade dos problemas de grafo, e vale entender o porquê, não só decorar.

O BFS processa os vértices em ordem não decrescente de distância: primeiro os que estão a 0 arestas da origem, depois os a 1, depois os a 2. A fila garante isso, porque um vértice só entra depois do pai, e o pai já estava na ordem certa.

Então, quando o BFS alcança um vértice pela primeira vez, ele chegou pelo caminho com menos arestas. Não existe caminho mais curto que tenha ficado para trás: ele teria sido explorado numa camada anterior.

def caminho_minimo(inicio, g):
    dist = {inicio: 0}
    fila = deque([inicio])
    while fila:
        u = fila.popleft()
        for v in g[u]:
            if v not in dist:          # primeira vez que vejo v
                dist[v] = dist[u] + 1  # e já é a menor
                fila.append(v)
    return dist

E a letra miúda que separa este tópico do próximo: isso só vale em grafo sem peso, onde toda aresta custa 1. Assim que as arestas têm custos diferentes, o caminho com menos arestas deixa de ser o mais barato, e você precisa de Dijkstra.

Onde cada um brilha

O DFS ganha nas perguntas sobre estrutura, porque a recursão dele expõe naturalmente a relação de ancestralidade: quando você está em um vértice, todos os que estão na pilha são ancestrais dele no caminho atual. É daí que saem detecção de ciclo, pontes, pontos de articulação e componentes fortemente conexos.

O BFS ganha nas perguntas sobre distância, pelo motivo da seção anterior.

Detectar ciclo: onde os dois divergem

Vale ver um caso em que a escolha não é preferência. Em grafo dirigido, existe ciclo se o DFS encontrar um vértice que está no caminho atual, e não simplesmente já visitado:

BRANCO, CINZA, PRETO = 0, 1, 2

def tem_ciclo(u, g, cor):
    cor[u] = CINZA                  # entrou no caminho atual
    for v in g[u]:
        if cor[v] == CINZA:         # voltei em quem ainda está aberto
            return True
        if cor[v] == BRANCO and tem_ciclo(v, g, cor):
            return True
    cor[u] = PRETO                  # terminou, saiu do caminho
    return False

As três cores são o detalhe que importa. Cinza quer dizer "estou dentro dele agora"; preto quer dizer "já terminei com ele". Achar um preto é normal (você chegou por outro caminho); achar um cinza é ciclo.

Em grafo não dirigido a regra é diferente: como toda aresta vale nos dois sentidos, você sempre volta ao pai. Aí a checagem é "vizinho já visitado e diferente do pai".

Um percurso não cobre o grafo

Um detalhe que o preset desconexo mostra: se o grafo tem mais de um componente, um único DFS ou BFS visita só o componente da origem.

Para cobrir tudo, o laço externo é obrigatório, e ele já vem com um brinde: o contador de componentes.

def componentes(g, n):
    visitados = set()
    total = 0
    for u in range(n):
        if u not in visitados:
            total += 1              # começou um componente novo
            dfs(u, g, visitados)
    return total

Esse esqueleto de nove linhas resolve uma família inteira de problemas: Number of Islands, Number of Provinces, contar grupos em rede social, achar regiões de uma imagem. Sempre que o enunciado perguntar "quantos grupos", é isso.

Complexidade e memória

Tempo é o mesmo para os dois: O(V + E) com lista de adjacência. Com matriz de adjacência vira O(V²), porque olhar os vizinhos de um vértice custa varrer uma linha inteira, e é mais um argumento para a lista.

Espaço é onde eles diferem, e é o mesmo trade-off da árvore:

• DFS: O(V) no pior caso, mas na prática proporcional à profundidade do caminho mais longo. Cuidado com a recursão em grafo grande e comprido: a pilha do Python estoura perto de mil níveis.
• BFS: O(V) também, mas o pico da fila é a largura do grafo, ou seja, quantos vértices existem a uma mesma distância. Em grafo largo, a fila fica grande cedo.

Compare o "pico da pilha" e o "pico da fila" no visualizador trocando de modo: são números diferentes no mesmo grafo.

Como praticar

Comece pelos dois esqueletos deste artigo em problemas diretos: Number of Islands e Number of Provinces são o laço de componentes conexos, e a grade do primeiro é o grafo implícito de que fala a introdução.

Depois vá para os que exigem o BFS por causa da distância: Rotting Oranges é BFS multi origem (comece com todas as laranjas podres na fila ao mesmo tempo, um truque que vale ouro), e Word Ladder é o caso em que o grafo nem existe até você inventá-lo.

Para o lado do DFS, Course Schedule é detecção de ciclo em grafo dirigido, com as três cores, e é a porta de entrada do próximo tópico.

Uma dica que economiza tempo: antes de escolher, releia o enunciado procurando as palavras "mínimo", "menor número de", "mais curto". Se elas estiverem lá e as arestas não tiverem peso, é BFS, e você já sabe escrever. Se as arestas tiverem peso, o próximo tópico é Dijkstra.

Vídeo da aula

Direto do canal da comunidade Craft & Code Club · 2:06:45.

▶

Problemas para praticar

Na ordem em que recomendamos resolver. Marque os que você já fez, fica salvo aqui.

Referências

Artigos e materiais externos para se aprofundar.