BFS x DFS: quando cada um
Pergunta
Qual a diferença entre busca em largura (BFS) e em profundidade (DFS) num grafo/árvore, e o que cada uma é boa pra resolver?
Resposta esperada
BFS explora nível por nível a partir da origem, usando uma fila; DFS vai fundo por um caminho até não dar mais, usando uma pilha (ou recursão) e faz backtrack. BFS é a escolha pra menor número de arestas / caminho mais curto em grafo não-ponderado (o primeiro caminho que chega ao alvo é o mais curto), e pra explorar 'o que está perto'. DFS é natural pra: existência de caminho, detecção de ciclo, ordenação topológica, explorar todas as combinações (backtracking), e problemas de árvore que casam com recursão. Custo de espaço: BFS guarda a 'franja' inteira (pode ser larga); DFS guarda só o caminho atual (profundidade) — mas DFS recursivo pode estourar a pilha em grafos muito profundos.
Por que perguntam isso
Pergunta pleno. Sinal de domínio: 'BFS dá o caminho mais curto em grafo não-ponderado' e os usos típicos de DFS (ciclo, topo-sort, backtracking).