Conhecendo Algoritmos de Grafos com NodeJS e Javascript
BFS e DFS em grafos com JavaScript: ordem de visita, fila vs pilha e exemplos visuais. Episódio da série de estruturas de dados.
Jonathan Juliani
Engenheiro de Software Sr - Full Stack · WithClutch Inc. | Juliani Tecnologia
Estruturas de DadosJavaScript
Grafo montado no ep. 7 não serve de nada sem . Este episódio implementa (largura) e (profundidade) — base de menor caminho sem peso, ciclo e ordenação topológica.
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:
Interactive Excalidraw view is not available in this build.
Control ou Command + rolar para ampliar. Clique e arraste para mover.
Control ou Command + rolar para ampliar. Clique e arraste para mover.
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.
Interactive Excalidraw view is not available in this build.
Control ou Command + rolar para ampliar. Clique e arraste para mover.
Control ou Command + rolar para ampliar. Clique e arraste para mover.
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.
Agora vamos adicionar o método BFS na classe Graph:
código
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:
código
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:
código
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:
código
node graph-algorithms.js
Resultado esperado:
código
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:
código
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).
