O que são os algoritmos BFS e DFS e quando escolher cada um?
BFS e DFS são algoritmos de travessia de grafos que encontram sistematicamente vértices alcançáveis a partir de um vértice inicial. O BFS expande nível a nível a partir dos vértices próximos, o que o torna adequado quando você precisa de um caminho com o menor número de arestas em um grafo não ponderado. O DFS segue um ramo o mais longe possível antes de retroceder, por isso é usado como base para problemas como análise estrutural, detecção de ciclos e ordenação topológica. Nenhum é sempre melhor; a escolha depende do critério do caminho e do propósito do grafo. ocw.mit.edualgs4.cs.princeton.edu
O que BFS e DFS encontram na travessia de grafos?
Um grafo é uma estrutura de relações formada por vértices e arestas. Os vértices representam entidades como pessoas, cidades, páginas da web ou tarefas, enquanto as arestas representam conexões entre elas, como amizades, estradas, links ou relações de pré-requisito. O conjunto de vértices é denotado por , e o conjunto de arestas por .
Se as arestas não têm direção, o grafo é não direcionado. Por exemplo, uma amizade mútua normalmente pode ser vista como bidirecional. Em contraste, relações como A seguir B ou a tarefa A precisar ser concluída antes da tarefa B formam um grafo direcionado. Em um grafo direcionado, você só pode percorrer a direção de uma seta; não pode se mover automaticamente na direção oposta. ocw.mit.edu
A pergunta mais básica na travessia de grafos é: “Quais vértices podem ser alcançados a partir de um ponto inicial ?” Ao responder a essa pergunta, BFS e DFS também podem registrar informações adicionais, como se um vértice foi visitado, o caminho pelo qual cada vértice foi alcançado pela primeira vez e a ordem da travessia. Porém, uma travessia iniciada em um vértice processa apenas a parte que é de fato alcançável a partir dele. Ela não necessariamente visita todos os vértices do grafo. ocw.mit.edu
Uma árvore também é um tipo de grafo. Portanto, BFS e DFS podem ser usados em problemas que se parecem com árvores, como hierarquias de pastas ou organogramas. No entanto, é importante lembrar que um grafo geral pode conter ciclos que retornam a um vértice e vários caminhos para o mesmo vértice. Aplicar diretamente a um grafo geral uma implementação projetada apenas para travessia de árvores pode causar visitas duplicadas.
Como o BFS explora primeiro os vértices mais próximos?
BFS significa Breadth-First Search, ou busca em largura. Primeiro, ele encontra os vértices alcançáveis a partir do ponto inicial por uma aresta; depois, os vértices que exigem duas arestas; em seguida, três arestas, expandindo a busca nessa ordem. Aqui, distância não é distância física nem custo; é o número de arestas que precisam ser percorridas a partir do ponto inicial. algs4.cs.princeton.edu
O BFS normalmente usa uma fila para isso. Uma fila é uma estrutura de dados FIFO (First In, First Out), o que significa que o primeiro item adicionado é o primeiro item removido. Coloque o vértice inicial na fila e marque-o como visitado; depois, remova um vértice da frente da fila. Marque todos os vizinhos não descobertos desse vértice como visitados e adicione-os ao fim da fila. Repita até que a fila esteja vazia. Como os vértices próximos descobertos anteriormente são processados primeiro, a expansão nível a nível é preservada. gh.cp-algorithms.comalgs4.cs.princeton.edu
Por exemplo, suponha que, a partir de A, você descubra os vizinhos B e C de A. Quando o BFS processa B, ele descobre os vizinhos de B; depois, processa C e descobre os vizinhos de C. Mesmo que um vértice descoberto a partir de B esteja mais profundo, C, que já havia sido colocado na fila no mesmo nível, é processado primeiro ou logo em seguida. A ordem exata entre B e C pode variar conforme a ordem em que os vértices adjacentes são armazenados.
O ponto-chave do BFS é marcar um vértice como visitado assim que ele é descoberto. Se você adiar essa marcação até que ele seja removido da fila, dois vértices podem descobrir o mesmo vizinho e inseri-lo na fila mais de uma vez. Em um BFS típico, marcar um novo vizinho como descoberto no exato momento em que ele é adicionado à fila é mais simples e seguro.
Em quais condições o BFS fornece um caminho mais curto?
O BFS é frequentemente escolhido porque, em um grafo não ponderado, encontra um caminho com o menor número de arestas do vértice inicial até cada vértice alcançável. Ele examina todos os vértices a um passo do início antes de examinar os vértices a dois passos, de modo que um caminho com menos arestas que o caminho que primeiro descobre um vértice não pode aparecer depois. Se você registrar o vértice anterior como pai quando cada vértice for descoberto pela primeira vez durante o BFS, esses ponteiros de pai formarão uma árvore de caminhos mais curtos. algs4.cs.princeton.edu
Para reconstruir um caminho, siga os ponteiros de pai de trás para frente, do vértice de destino até o vértice inicial, e então inverta a ordem. Por exemplo, se parent[D] = B e parent[B] = A, o caminho descoberto de A até D é A → B → D. Use um marcador separado para indicar que o vértice inicial não tem pai.
No entanto, interpretar “mais curto” de forma ampla demais leva a erros. O BFS garante o menor número de arestas somente quando todas as arestas podem ser tratadas como tendo o mesmo custo. Se estradas têm tempos de viagem diferentes ou voos têm tarifas diferentes, um caminho que usa duas arestas pode ser mais barato ou mais rápido que outro que usa uma única aresta. Nesse caso, o BFS padrão não é um algoritmo de caminho mais curto por custo. Dependendo das propriedades dos pesos, considere métodos ponderados específicos, como o algoritmo de Dijkstra ou o algoritmo de Bellman-Ford. algs4.cs.princeton.edu
Portanto, o BFS é adequado para problemas como “Quantos graus de conexão separam dois amigos?” ou “Quantos movimentos são necessários para chegar a um ponto em uma grade quando mover uma célula para cima, para baixo, para a esquerda ou para a direita conta como um movimento?”. Em contraste, se o objetivo for o menor tempo ou custo, primeiro verifique se os pesos das arestas são realmente iguais.
Por que o DFS se aprofunda antes de retroceder?
DFS significa Depth-First Search, ou busca em profundidade. A partir do vértice atual, ele escolhe um vizinho não visitado e continua avançando até explorar um ramo o mais profundamente possível. Quando chega a um beco sem saída, retorna ao vértice anterior e procura outro vizinho ainda não explorado. Esse processo de retorno também é chamado de retrocesso. ocw.mit.edu
O DFS é fácil de implementar com chamadas recursivas. Ao entrar em um vértice, primeiro marque-o como visitado e depois chame a mesma função de travessia para cada vizinho não visitado desse vértice. Quando uma chamada recursiva termina, o controle retorna naturalmente ao ponto que a chamou, expressando o fluxo de se aprofundar e depois retroceder.
A recursão não é a única opção. O DFS também pode ser implementado de forma iterativa com uma pilha explícita. Uma pilha é uma estrutura de dados LIFO (Last In, First Out), o que significa que o último item adicionado é o primeiro item removido. Ao remover primeiro o vértice descoberto mais recentemente, você pode produzir um comportamento de busca em profundidade. Em uma implementação recursiva, a pilha de chamadas do programa desempenha esse papel implicitamente. ocw.mit.edugh.cp-algorithms.com
Os ponteiros de pai criados pelo DFS também podem mostrar um caminho do vértice inicial até um vértice. No entanto, esse caminho não tem garantia de possuir o menor número de arestas. Como o DFS segue seu primeiro ramo escolhido o mais profundamente possível, ele pode descobrir um caminho mais curto em outro ramo somente mais tarde. ocw.mit.edu
Que tipos de análise estrutural usam DFS?
O DFS mostra seu valor ao analisar a estrutura de um grafo, em vez de simplesmente verificar alcançabilidade. Encontrar componentes conexos é um exemplo representativo. Em um grafo não direcionado, executar DFS uma vez a partir de qualquer vértice não visitado encontra todos os vértices conectados a ele como um grupo. Iniciar DFS novamente a partir de outro vértice não visitado encontra outro grupo.
A detecção de ciclos é outra aplicação comum do DFS. Um ciclo é uma estrutura em que seguir arestas pode levar você de volta ao ponto inicial ou a um vértice que já está no caminho atual. Em um grafo direcionado, você pode detectar um ciclo ao distinguir se encontra um vértice que já está no caminho recursivo atual. É por isso que você deve distinguir entre um vértice que apenas foi visitado uma vez e um que está atualmente no caminho da travessia.
A ordenação topológica organiza dependências direcionadas, como relações de pré-requisito entre tarefas, em uma ordem. Ela é possível apenas em um grafo acíclico direcionado, ou DAG. Um DAG é um grafo direcionado sem ciclo que retorna ao ponto inicial ao seguir as direções das arestas. Se existir um ciclo, surge uma contradição — por exemplo, B deve terminar antes de A e A deve terminar antes de B —, então nenhuma ordenação linear poderá satisfazer todas as arestas. Um método que usa a ordem de término do DFS é uma das bases para a ordenação topológica. algs4.cs.princeton.edu
Encontrar componentes fortemente conexos também é um tópico importante baseado em DFS. Um componente fortemente conexo é um conjunto de vértices em um grafo direcionado no qual quaisquer dois vértices do mesmo grupo podem alcançar um ao outro. No entanto, esse problema não é resolvido com apenas um DFS simples; ele requer uma construção algorítmica que usa a ordem de travessia e as direções das arestas. algs4.cs.princeton.edu
Que problemas ocorrem sem marcadores de visitado?
Em um grafo geral, um vetor ou conjunto de visitados não é opcional; ele é essencial para a terminação e a correção. Por exemplo, se A e B estão conectados, você pode ir de A para B e depois voltar de B para A. Sem verificar o estado de visitado, o DFS pode alternar recursivamente entre A e B para sempre, e o BFS pode colocar o mesmo vértice na fila várias vezes. ocw.mit.edu
O termo visitado pode ser dividido de maneira ligeiramente diferente dependendo da implementação. No BFS, um vértice normalmente é marcado como “descoberto” no momento em que é adicionado à fila. No DFS, é comum marcar um vértice como visitado imediatamente ao entrar em sua função. Análises mais sofisticadas de grafos direcionados podem distinguir entre um estado não visitado, um estado que está sendo explorado no momento e um estado concluído.
O princípio de visitar cada vértice apenas uma vez está diretamente ligado à eficiência da travessia. Se você não expandir vértices que já foram processados, então, com listas de adjacência, inspecionará cada vértice e aresta apenas um número limitado de vezes. Além disso, se atribuir um ponteiro de pai somente quando um vértice for descoberto pela primeira vez, ficará claro qual caminho descobriu primeiro esse vértice.
Para percorrer um grafo inteiro, você precisa de um laço externo. Examine cada vértice por vez e, sempre que encontrar um que ainda não foi visitado, inicie um novo BFS ou DFS a partir dele. Em um grafo não direcionado, isso produz uma travessia por componente conexo. Em um grafo direcionado, processa sucessivamente as regiões alcançáveis nas direções de aresta escolhidas. ocw.mit.edu
Por que a complexidade de tempo depende da representação do grafo?
A complexidade de tempo de BFS e DFS costuma ser dada como . Essa é a análise padrão ao usar listas de adjacência. Uma lista de adjacência armazena a lista de vizinhos diretamente conectados para cada vértice. Com marcadores de visitado, cada vértice é processado uma vez e as arestas são verificadas ao percorrer as listas de vizinhos; portanto, o trabalho total é proporcional ao número de vértices mais o número de arestas. ocw.mit.edu
O espaço adicional normalmente é . Isso inclui o vetor de visitados, o vetor de pais e a fila do BFS ou a pilha do DFS. Para o DFS recursivo, a pilha de chamadas necessária para a profundidade da recursão também é incluída no espaço adicional. É útil distinguir entre o espaço usado para armazenar o próprio grafo e o espaço extra usado pelo algoritmo de travessia. ocw.mit.edu
Uma matriz de adjacência armazena a existência de uma aresta para cada par de vértices em uma tabela. Para encontrar os vizinhos de um vértice, talvez seja necessário inspecionar todos os vértices possíveis. Portanto, BFS ou DFS usando uma matriz de adjacência pode normalmente levar de tempo. Para grafos esparsos com poucas arestas, listas de adjacência são especialmente eficientes porque percorrem apenas os vizinhos efetivamente conectados. ocw.mit.edu
| Representação | Como os vizinhos são verificados | Tempo típico de travessia |
|---|---|---|
| Lista de adjacência | Iterar pela lista de vizinhos efetivamente conectados | |
| Matriz de adjacência | Verificar conexões com todos os vértices possíveis |
A notação de complexidade descreve como o uso de recursos tende a crescer à medida que o tamanho da entrada aumenta. O tempo de execução real também é afetado pelos identificadores dos vértices, pela implementação da lista de adjacência, pelo layout da memória e pelo tamanho da parte alcançável a partir do ponto inicial da travessia. Ainda assim, ao escolher um algoritmo, faz sentido verificar primeiro se o grafo é esparso e como ele está representado.
A ordem real de visitação do BFS ou DFS é fixa?
Não. O BFS segue o princípio de processar primeiro os níveis mais próximos, e o DFS segue o princípio de explorar profundamente o ramo atual, mas qual vértice é visitado primeiro dentro do mesmo nível ou qual ramo é explorado primeiro entre vários vizinhos depende da ordem de armazenamento dos vértices adjacentes. gh.cp-algorithms.comgh.cp-algorithms.com
Por exemplo, se a lista de vizinhos de A está na ordem B, C, o BFS geralmente descobre B primeiro. Se a lista for alterada para C, B, C poderá ser descoberto primeiro. Essa diferença pode ter um efeito maior no DFS. Se o primeiro vizinho escolhido mudar, o próprio ramo explorado profundamente muda, assim como a árvore de travessia e os caminhos de DFS criados pelos ponteiros de pai.
Esse fato importa ao avaliar o resultado de um algoritmo. Se um problema exigir “a ordem de visitação lexicograficamente primeira”, você deve ordenar as listas de adjacência ou especificar uma regra de prioridade. Em contraste, se você precisa apenas de alcançabilidade, do número de componentes conexos ou de distâncias mínimas em número de arestas, a ordem detalhada dentro do mesmo nível ou profundidade pode não ser central para o resultado.
Em particular, ao implementar DFS iterativamente com uma pilha, a ordem em que os vizinhos são inseridos na pilha pode ser o inverso da ordem em que eles são de fato removidos. Se você quiser a mesma ordem de visitação de uma implementação recursiva usando uma determinada ordem de lista de adjacência, precisa ajustar intencionalmente a direção em que os vizinhos são inseridos na pilha. Isso não é uma definição diferente de DFS; é uma diferença de implementação causada pelo comportamento LIFO.
Quais são os equívocos e erros comuns?
O primeiro é o equívoco de que o BFS resolve todo tipo de problema de caminho mais curto. Como discutido anteriormente, o BFS garante o menor número de arestas em um grafo não ponderado. Se os pesos forem diferentes, um movimento não necessariamente tem o mesmo valor que outro, então o próprio modelo do problema muda. algs4.cs.princeton.edualgs4.cs.princeton.edu
O segundo é a suposição de que o DFS sempre usa menos memória que o BFS. Incluindo vetores de visitados e o estado da travessia, ambos os algoritmos podem, em geral, usar de espaço adicional. O tamanho máximo da fila ou da pilha pode diferir para determinados formatos de grafo e implementações, mas somente a complexidade assintótica não estabelece uma vantagem incondicional para nenhum dos dois. ocw.mit.edu
O terceiro é a crença de que o DFS recursivo é seguro para toda entrada. Em um grafo com profundidade muito grande, a profundidade da recursão também se torna grande. Você deve considerar o limite da pilha de chamadas da linguagem e do ambiente de execução; nesses casos, uma implementação iterativa com uma pilha explícita pode ser mais prática. Também é importante entender que a pilha de chamadas recursivas faz parte do espaço adicional do DFS. ocw.mit.edu
O quarto é tratar um grafo direcionado como se fosse não direcionado. A existência de uma aresta de A para B não significa que você pode ir de B para A. Ao armazenar a entrada em listas de adjacência, um grafo não direcionado normalmente adiciona uma aresta às listas dos dois vértices, enquanto um grafo direcionado a adiciona apenas à lista do vértice de origem. Essa diferença muda o significado de alcançabilidade, conectividade e ciclos. ocw.mit.edu
O quinto é confundir um resultado de travessia com um único caminho correto. Quando vários caminhos têm o mesmo número mínimo de arestas, o BFS registra um deles por meio de ponteiros de pai. O DFS também pode produzir caminhos diferentes conforme a ordem dos vizinhos. Se o próprio caminho precisa obedecer a uma prioridade, regras de ordenação ou condições adicionais devem ser especificadas no problema.
Quais critérios você deve usar ao escolher para um problema?
É melhor primeiro expressar o objetivo em palavras. Se a pergunta apenas pede “É possível alcançá-lo a partir do ponto inicial?”, tanto BFS quanto DFS são possíveis, e você pode escolher com base no ambiente de implementação e na análise necessária depois. Se você precisa do menor número de arestas, como em “Quantos movimentos idênticos são necessários para chegar?”, BFS é a escolha natural. Se você precisa seguir profundamente um caminho ao analisar a estrutura, ou se o momento em que você retorna importa, o DFS provavelmente é apropriado.
Em seguida, verifique o que as arestas significam. Determine se todo movimento tem o mesmo custo ou se há pesos como tempo, distância ou custo envolvidos. Se existirem pesos, não aplique diretamente a propriedade de caminho mais curto do BFS. Verifique também antecipadamente se o grafo é direcionado, se ciclos são possíveis e se você precisa examinar o grafo inteiro. ocw.mit.edualgs4.cs.princeton.edu
Os critérios de seleção podem ser resumidos da seguinte forma.
| Situação ou pergunta | Método a considerar primeiro | Condições a observar |
|---|---|---|
| Menor número de movimentos, expansão nível a nível | BFS | Os custos das arestas devem ser iguais |
| Alcançabilidade simples | BFS ou DFS | Explora apenas a parte alcançável a partir do ponto inicial |
| Encontrar componentes conexos como grupos | DFS ou BFS | Repita a travessia para cada vértice não visitado |
| Analisar ciclos, ordem topológica ou estrutura fortemente conexa | Métodos baseados em DFS | A ordenação topológica só é possível em um DAG |
| Caminhos mais curtos com tempos ou custos diferentes | Outro método de caminho mais curto ponderado | As garantias do BFS padrão não se aplicam |
Por fim, considere o tamanho e a representação da entrada. Para um grafo esparso, listas de adjacência e a análise padrão de para BFS e DFS são adequadas. Em ambientes nos quais a profundidade de recursão pode ser um problema, considere o DFS iterativo. Se a ordem de visitação afeta a avaliação ou regras de negócio, a ordenação da lista de adjacência também faz parte do projeto.
Conclusão: os objetivos e as condições da travessia importam mais que os nomes
BFS e DFS são estratégias diferentes para percorrer um grafo de forma completa. O BFS usa uma fila para expandir a partir dos vértices próximos e tem a vantagem de fornecer caminhos com o menor número de arestas em grafos não ponderados. O DFS usa recursão ou uma pilha para explorar profundamente um ramo e retroceder, formando a base de muitos métodos que trabalham com a estrutura de grafos, incluindo componentes conexos, ciclos e ordenação topológica em DAGs. ocw.mit.edualgs4.cs.princeton.edu
Ambos exigem marcadores de visitado e, em geral, têm a mesma complexidade de tempo assintótica ao usar listas de adjacência. Portanto, a chave para escolher entre eles não é um único rótulo, como velocidade, mas o que define um caminho mais curto, se as arestas são ponderadas, como direção e ciclos devem ser interpretados e se o grafo inteiro precisa ser processado. Distinguir primeiro essas condições permite usar BFS e DFS para a finalidade correta.