Busca em Grafos (BFS e DFS)

Percorrendo vértices por largura ou profundidade

Definição

As buscas em grafos são técnicas fundamentais para explorar e percorrer estruturas como árvores e grafos. As duas abordagens mais comuns são:

BFS (Breadth-First Search) — Busca em Largura
DFS (Depth-First Search) — Busca em Profundidade

Ambas são amplamente usadas em algoritmos de caminhos, detecção de ciclos, conectividade e muito mais.

Por que usar

Busca em Largura ideal para encontrar o menor caminho em número de arestas;
Busca em Profundidade útil para explorar todo o grafo, identificar ciclos e dependências;
Ambas são bases para algoritmos mais complexos, como Dijkstra, Topological Sort e Tarjan.

Exemplo prático (Python) — Grafo não direcionado

grafo = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

Busca em Largura (BFS)

Percorre o grafo por níveis, usando uma fila. Visita os vizinhos mais próximos antes de avançar.

from collections import deque

def bfs(grafo, inicio):
    visitados = set()
    fila = deque([inicio])

    while fila:
        vertice = fila.popleft()
        if vertice not in visitados:
            print(vertice, end=" ")
            visitados.add(vertice)
            fila.extend(v for v in grafo[vertice] if v not in visitados)

# Exemplo
bfs(grafo, 'A')  # Saída: A B C D E F

Busca em Profundidade (DFS)

Percorre o grafo o mais fundo possível antes de voltar. Pode ser implementada com recursão ou pilha.

def dfs(grafo, vertice, visitados=None):
    if visitados is None:
        visitados = set()

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

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

# Exemplo
dfs(grafo, 'A')

Visualização

Suponha o grafo:

     A
    / \
   B   C
  / \   \
 D   E - F

BFS (A) visita: A B C D E F
DFS (A) pode visitar: A B D E F C

(A ordem da DFS pode variar dependendo da ordem dos vizinhos na lista)

Saída

A B C D E F  - Busca em Largura
A B D E F C  - Busca em Profundidade