Busca em grafos: BFS e DFS

Em 1736, Leonhard Euler mostrou que nenhum passeio atravessa cada uma das sete pontes de Königsberg exatamente uma vez, e a teoria dos grafos começou com essa resposta.

Pontos e linhas

Um grafo é um conjunto de pontos, chamados vértices ou nós, ligados por linhas, chamadas arestas. A ideia é simples e serve para uma variedade enorme de coisas: cidades ligadas por estradas, páginas web ligadas por links, pessoas ligadas por amizades, quadrados de um labirinto ligados onde não há parede. Depois que um problema é desenhado como grafo, o mesmo punhado de algoritmos responde a perguntas como "dá para ir daqui até lá?" e "qual é o caminho mais curto?"

Guardando um grafo no código

Um jeito comum de guardar um grafo é a lista de adjacência: para cada vértice, uma lista dos seus vizinhos. As notas do curso 6.006 do MIT usam exatamente isso, um array ou dicionário Adj em que Adj[u] lista os vértices ligados a u. Para o grafo acima, fica assim:

const graph = {   // lista de adjacência
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D", "E"],
  D: ["B", "C", "F"],
  E: ["C", "F"],
  F: ["D", "E"],
};

Busca em largura: anel por anel

A busca em largura (BFS) explora um grafo em anéis em volta do início. Primeiro o próprio início, à distância 0. Depois todos os vizinhos dele, à distância 1. Depois todo vértice novo ao lado desses, à distância 2, e assim por diante. Para isso ela mantém uma fila, em que o primeiro a entrar é o primeiro a sair. Pegue o vértice da frente da fila, visite-o e acrescente os vizinhos ainda não vistos no fim. A partir de A, no exemplo, a BFS visita A, depois B e C, depois D e E, depois F. Como ela avança para fora um anel por vez, a primeira vez que a BFS chega a um vértice ela encontrou um caminho com o menor número de arestas. F está a 3 arestas de A, por exemplo A, B, D, F.

function bfs(graph, start) {
  const seen = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length) {
    const u = queue.shift();        // primeiro a entrar, primeiro a sair
    order.push(u);
    for (const v of graph[u]) {
      if (!seen.has(v)) { seen.add(v); queue.push(v); }
    }
  }
  return order;   // A B C D E F
}

Busca em profundidade: até onde der, depois volte

A busca em profundidade (DFS) se comporta como alguém num labirinto que mantém uma mão na parede. Ela segue um caminho o mais fundo possível. Quando chega a um beco sem saída ou a um lugar já visto, ela volta até o último ponto de escolha e tenta a próxima opção. Ela usa uma pilha em vez de uma fila, último a entrar, primeiro a sair, e é muito natural de escrever com recursão, em que a pilha de chamadas faz o trabalho de lembrar. A partir de A, uma DFS recursiva visita A, B, D, C, E, F. A DFS chega a todo vértice a que a BFS chega, mas o caminho que ela segue não é necessariamente o mais curto.

function dfs(graph, u, seen = new Set(), order = []) {
  seen.add(u);
  order.push(u);
  for (const v of graph[u]) if (!seen.has(v)) dfs(graph, v, seen, order);
  return order;   // ordem: A B D C E F
}

Qual usar

No primeiro labirinto do laboratório, a BFS visita 105 quadrados e acha um caminho de 22 movimentos, o mais curto possível. A DFS por acaso mergulha na direção do objetivo e visita só 31 quadrados, mas o caminho dela leva 28 movimentos. Nenhuma é sempre mais barata. As duas tratam cada vértice e cada aresta um número fixo de vezes, então as duas rodam em tempo O(V + E) para V vértices e E arestas. Escolha a BFS quando precisar do menor número de passos: o menor número de movimentos num quebra-cabeça, o menor número de ligações entre duas pessoas. Escolha a DFS quando precisar explorar tudo ou seguir escolhas até o fim: conferir se todas as salas de um labirinto se ligam, ou testar as jogadas de um quebra-cabeça uma linha de cada vez e voltar quando travar. Quando as arestas têm comprimentos diferentes, como as estradas, nenhuma das duas basta sozinha; métodos como o algoritmo de Dijkstra estendem a ideia da BFS com distâncias.