Busca em largura e em profundidade

Busca em largura e em profundidade

Buscar em um grafo é visitar, a partir de um vértice inicial, todos os vértices que podem ser alcançados seguindo arestas. As duas buscas básicas diferem só em qual vértice pega da fila de vizinhos.

Busca em largura (BFS)

A BFS usa uma fila: visita o vértice mais antigo da fila primeiro. Por isso ela visita primeiro tudo a distância 1, depois tudo a distância 2, e assim por diante. O nível de cada vértice é exatamente a distância em arestas até a origem.

A árvore formada pelas arestas que descobriram vértices novos é a árvore da busca em largura, e os caminhos dessa árvore são caminhos mínimos em número de arestas.

Busca em profundidade (DFS)

A DFS usa uma pilha (ou recursão): desce pelo primeiro vizinho não visitado até travar e só então volta. Ela produz uma árvore mais "comprida", e os tempos de entrada e saída de cada vértice mostram a ordem em que a busca entrou e saiu dele. Esses tempos são a base de vários algoritmos mais avançados, como a detecção de ciclos em grafos dirigidos.

O que observar na animação

• A cor do vértice atual muda para destaque, e as arestas que formaram a árvore ficam mais grossas.
• A narração diz quando uma aresta é rejeitada porque o vizinho já foi visto. Isso não é erro: são as arestas que fecham ciclos.
• Em um grafo desconexo, a busca a partir de um vértice cobre só a sua componente. A DFS completa, que começa em todos os vértices, produz uma floresta.

Custo

Cada vértice entra na fila (ou na pilha) no máximo uma vez, e cada aresta é olhada uma ou duas vezes. Por isso o tempo é proporcional a n + m, o número de vértices mais o de arestas.