Nesta aula exploramos dois algoritmos fundamentais para percorrer grafos: a Busca em Largura (BFS) e a Busca em Profundidade (DFS). Eles são a base para resolver problemas como caminhos mínimos, detecção de ciclos, ordenação topológica e muito mais. Vamos entender o funcionamento, implementar em Python e comparar as abordagens.

O que é um grafo?

Um grafo é uma estrutura composta por vértices (ou nós) e arestas que conectam pares de vértices. Formalmente, definimos G = (V, E) onde V é o conjunto de vértices e E o conjunto de arestas. Grafos podem ser direcionados (as arestas têm sentido) ou não direcionados (arestas bidirecionais). Quando as arestas possuem pesos, chamamos de grafo ponderado.

Os algoritmos de busca percorrem os vértices a partir de um nó fonte, visitando cada vértice alcançável de forma sistemática.

Busca em Largura (BFS)

A BFS visita os vértices por camadas: primeiro o nó inicial, depois todos os seus vizinhos diretos, depois os vizinhos dos vizinhos, e assim por diante. Para isso utiliza uma fila (FIFO). A BFS é especialmente útil para encontrar o caminho mais curto em grafos não ponderados (menor número de arestas).

Implementação em Python

from collections import deque

def bfs(grafo, inicio):
    visitados = set()
    fila = deque([inicio])
    visitados.add(inicio)
    
    while fila:
        vertice = fila.popleft()
        print(f"Visitando: {vertice}")
        for vizinho in grafo[vertice]:
            if vizinho not in visitados:
                visitados.add(vizinho)
                fila.append(vizinho)
    return visitados

Exemplo

Considere um grafo não direcionado com vértices A, B, C, D, E e arestas: A-B, A-C, B-D, C-D, C-E. Executando BFS a partir de A, a ordem de visita é: A, B, C, D, E (considerando a ordem de inserção na fila).

Complexidade

A BFS possui complexidade de tempo O(V + E), onde V é o número de vértices e E o número de arestas. O espaço adicional é O(V) para a fila e o conjunto de visitados.

Busca em Profundidade (DFS)

A DFS explora o grafo indo o mais fundo possível em cada ramo antes de retroceder. Utiliza uma pilha (LIFO), que pode ser implementada recursivamente ou com uma pilha explícita. A DFS é útil para problemas como detecção de ciclos, ordenação topológica e exploração completa de componentes conexos.

Implementação recursiva

def dfs(grafo, vertice, visitados=None):
    if visitados is None:
        visitados = set()
    visitados.add(vertice)
    print(f"Visitando: {vertice}")
    for vizinho in grafo[vertice]:
        if vizinho not in visitados:
            dfs(grafo, vizinho, visitados)
    return visitados

Exemplo

Usando o mesmo grafo do exemplo anterior, a DFS a partir de A pode visitar: A, B, D, C, E (depende da ordem dos vizinhos). A diferença fundamental é que a DFS avança por um caminho antes de explorar alternativas.

Complexidade

Assim como a BFS, a DFS tem complexidade O(V + E) no tempo. O espaço é O(V) no pior caso (pilha de recursão ou pilha explícita).

Comparação BFS vs DFS

  • Estrutura de dados auxiliar: BFS usa fila; DFS usa pilha (ou recursão).
  • Ordem de visita: BFS visita por camadas; DFS vai até o fundo de cada ramo.
  • Caminho mínimo (grafos não ponderados): BFS encontra o caminho com menos arestas; DFS não garante.
  • Detecção de ciclos: Ambos podem detectar, mas DFS é mais direta com arestas de retorno.
  • Memória: BFS pode consumir mais memória em grafos largos; DFS em grafos profundos.
  • Aplicações típicas: BFS → menor caminho, redes sociais; DFS → ordenação topológica, puzzles, componentes fortemente conexos.

Resumo dos conceitos principais

  • BFS e DFS são algoritmos de busca cega (não usam informação do problema).
  • Ambos visitam todos os vértices alcançáveis a partir de uma fonte.
  • A escolha depende do problema: BFS para caminho mínimo em grafos não ponderados; DFS para exploração completa e problemas de backtracking.
  • É possível implementar DFS iterativamente com uma pilha explícita, evitando recursão profunda.

Perguntas Frequentes

Qual a diferença principal entre BFS e DFS?

A BFS visita os vértices por ordem de distância da fonte (níveis), enquanto a DFS segue um caminho até o fim antes de explorar outros.

Quando usar BFS?

Use BFS quando você precisa do caminho mínimo em grafos não ponderados, ou quando quer visitar os vértices mais próximos primeiro.

Quando usar DFS?

Use DFS para problemas que exigem exploração completa, como labirintos, detecção de ciclos, ordenação topológica, e quando a profundidade da solução é conhecida.

BFS e DFS funcionam em grafos ponderados?

Sim, ambos percorrem o grafo, mas a BFS não garante caminho mínimo com pesos. Para isso é necessário Dijkstra ou Bellman-Ford.

DFS recursiva pode estourar a pilha?

Sim, em grafos muito grandes a recursão pode causar stack overflow. Nesse caso, a implementação iterativa com pilha explícita é preferível.