Conhecendo Algoritmos de Grafos com NodeJS e Javascript

Grafo montado no ep. 7 não serve de nada sem travessia. Este episódio implementa BFS (largura) e DFS (profundidade) — base de menor caminho sem peso, ciclo e ordenação topológica.

O que você vai aprender:

• BFS com fila e Set de visitados
• DFS recursivo e iterativo
• Quando BFS acha caminho mais curto (sem peso)
• Por que DFS detecta ciclo

Pré-requisitos: grafos (ep. 7) e pilhas/filas (eps. 4–5).

BFS e DFS: percorrer grafo sem loop infinito

Lá no Post 7 a gente construiu uma estrutura de Graph com nós e arestas. Ter a estrutura de dados é ótimo, mas sem algoritmos pra navegar nela, é como ter um mapa que você não consegue usar. É disso que se trata esse post: Busca em Largura (BFS) e Busca em Profundidade (DFS)—os dois algoritmos fundamentais pra explorar um grafo.

Pra deixar as coisas concretas, vamos usar esse grafo em todos os exemplos:

graph LR
  A --- B
  A --- C
  B --- D
  B --- E
  C --- F
  C --- G

Começando pelo nó A, BFS e DFS vão visitar todos os nós—mas em ordens completamente diferentes.

Mão na Massa

A Teoria um Pouco Mais Funda

BFS — Busca em Largura

BFS usa uma fila. Ele visita todos os vizinhos do nó atual antes de ir mais fundo. Pensa como uma onda se expandindo: primeiro todos os nós a um passo de distância, depois todos a dois passos, e assim por diante.

graph LR
  A["A (1º)"] --- B["B (2º)"]
  A --- C["C (3º)"]
  B --- D["D (4º)"]
  B --- E["E (5º)"]
  C --- F["F (6º)"]
  C --- G["G (7º)"]

Ordem de visita BFS a partir de A: A → B → C → D → E → F → G

DFS — Busca em Profundidade

DFS usa uma pilha (ou recursão). Ele mergulha o mais fundo possível em um caminho antes de voltar. Pensa como explorar um labirinto: vai até o fundo de um corredor, bate na parede, volta e tenta o próximo.

graph LR
  A["A (1º)"] --- B["B (2º)"]
  A --- C["C (5º)"]
  B --- D["D (3º)"]
  B --- E["E (4º)"]
  C --- F["F (6º)"]
  C --- G["G (7º)"]

Ordem de visita DFS a partir de A: A → B → D → E → C → F → G

Agora a Prática

A gente vai reaproveitar o Graph do Post 7. Cola o arquivo completo pra começar:

class Graph {
  constructor() {
    this.numberOfNodes = 0
    this.adjacentList = {}
  }
 
  add(node) {
    this.adjacentList[node] = []
    this.numberOfNodes++
  }
 
  addEdge(node1, node2) {
    this.adjacentList[node1].push(node2)
    this.adjacentList[node2].push(node1)
  }
}

Agora vamos adicionar o método BFS na classe Graph:

  bfs(start) {
    const visited = new Set()
    const queue = [start]
    const order = []
 
    visited.add(start)
 
    while (queue.length) {
      const node = queue.shift()
      order.push(node)
 
      for (const neighbour of this.adjacentList[node]) {
        if (!visited.has(neighbour)) {
          visited.add(neighbour)
          queue.push(neighbour)
        }
      }
    }
 
    return order
  }

Explicando:

• Começamos com um Set pra rastrear nós visitados (pra não entrar em loop infinito em grafos com ciclos) e uma queue inicializada com o nó de partida.
• A cada iteração a gente pega o nó da frente da fila (shift()), registra ele, e enfileira todos os seus vizinhos não visitados.
• Por processar a fila de frente pra trás, visitamos os nós naturalmente nível por nível.

Agora vamos adicionar o DFS:

  dfs(start) {
    const visited = new Set()
    const order = []
 
    const explore = (node) => {
      visited.add(node)
      order.push(node)
      for (const neighbour of this.adjacentList[node]) {
        if (!visited.has(neighbour)) {
          explore(neighbour)
        }
      }
    }
 
    explore(start)
    return order
  }

Explicando:

• Usamos uma função auxiliar recursiva explore que marca o nó como visitado, registra ele, depois imediatamente recursea em cada vizinho não visitado.
• Como vamos fundo no primeiro vizinho antes de considerar os irmãos, obtemos a ordem em profundidade.

Vamos testar os dois. Depois da classe, adiciona:

const g = new Graph()
g.add('A')
g.add('B')
g.add('C')
g.add('D')
g.add('E')
g.add('F')
g.add('G')
 
g.addEdge('A', 'B')
g.addEdge('A', 'C')
g.addEdge('B', 'D')
g.addEdge('B', 'E')
g.addEdge('C', 'F')
g.addEdge('C', 'G')
 
console.log('BFS a partir de A:', g.bfs('A'))
console.log('DFS a partir de A:', g.dfs('A'))

Roda o arquivo:

node graph-algorithms.js

Resultado esperado:

BFS a partir de A: [ 'A', 'B', 'C', 'D', 'E', 'F', 'G' ]
DFS a partir de A: [ 'A', 'B', 'D', 'E', 'C', 'F', 'G' ]

Os dois algoritmos visitaram os 7 nós, mas em ordens completamente diferentes. BFS foi largo (todos os vizinhos diretos de A primeiro), enquanto DFS foi fundo (seguiu o galho de B até o fim antes de tocar em C).

Jon, posso fazer DFS iterativo em vez de recursivo?

Sim! Substitui a função explore por uma pilha:

  dfsIterative(start) {
    const visited = new Set()
    const stack = [start]
    const order = []
 
    while (stack.length) {
      const node = stack.pop()
      if (visited.has(node)) continue
      visited.add(node)
      order.push(node)
      for (const neighbour of this.adjacentList[node]) {
        if (!visited.has(neighbour)) stack.push(neighbour)
      }
    }
 
    return order
  }

A versão iterativa usa uma pilha explícita em vez da call stack—mais seguro pra grafos muito grandes ou profundos onde a recursão pode estourar o limite de chamadas.

Aonde Você Pode Usar/Ver

BFS — Menor Caminho em Grafos Sem Peso

Como BFS se expande nível por nível, a primeira vez que ele chega num nó alvo, encontrou o caminho mais curto em termos de número de arestas. Essa é a base de algoritmos de menor caminho sem peso—pensa em "graus de separação" numa rede social, ou o mínimo de movimentos pra resolver um puzzle.

BFS — Rastreamento Web

Crawlers de buscadores começam de uma URL semente e percorrem a web via BFS seguindo links. BFS garante que eles descubram páginas próximas antes de mergulhar fundo em um domínio.

DFS — Detecção de Ciclos

Se o DFS visitar um nó que já está na pilha de recursão atual, existe um ciclo. É assim que gerenciadores de dependências detectam importações circulares.

DFS — Ordenação Topológica

Em um grafo direcionado acíclico (DAG), o DFS pode produzir uma ordenação topológica—uma sequência onde cada nó vem antes de todos os nós para os quais ele aponta. Sistemas de build e agendadores de tarefas usam isso pra determinar a ordem de execução.

Edge cases: visitados, shift e stack overflow

Sem Set de visitados, ciclo = loop infinito. Sempre marque ao enfileirar/empilhar, não só ao processar.

DFS recursivo em grafo profundo estoura call stack no Node (~10k frames). Versão iterativa com pilha explícita é mais segura.

BFS com arestas ponderadas não garante menor custo — aí entra Dijkstra (fila de prioridade).

TL;DR — BFS vs DFS

Próximos passos

• Ordenação (ep. 15): preparar array pra busca — Ordenando arrays
• Busca binária (ep. 16): fechamento da série — Busca binária

Antes de fechar

BFS ou DFS — qual você usou em produção? Se viu erro no grafo de exemplo, comenta.