Busca em Largura

Anteriormente, introduzimos brevemente o problema de caminhamentos em grafos. Relembrando, o problema é o seguinte:

Problema: Dado um grafo $G(V, E)$, direcionado ou não-direcionado, em um vértice de origem $s \in V$, precisamos identificar todos os vértices de $G$ que são alcançáveis a partir de $s$. Dizer que um vértice $u$ é alcançável a partir de um vértice $v$ significa que existe uma sequência de arestas no grafo permitindo que se saia de $u$ e se chegue a $v$.

Novamente, tomaremos como base uma representação do grafo como lista de listas, conforme discutido nas seções anteriores:

grafo = [ [1],           # Vizinhos do vértice 0.
          [2, 3],        # Vizinhos do vértice 1.
          [1, 4],        # Vizinhos do vértice 2.
          [0],           # Vizinhos do vértice 3.
          [1]            # Vizinhos do vértice 4.
        ]

A ideia geral da busca em largura é explorar o grafo visitando os vértices por níveis. O primeiro nível é formado pelos vértices que estão conectados diretamente ao vértice de origem. O segundo nível é formado pelos vértices adjacentes aos vértices do primeiro nível. O terceiro nível é formado pelos vértices vizinhos aos vértices do segundo nível. E assim por diante. Note que, na busca em largura, antes de explorarmos vértices mais distantes do vértice atual, exploramos os vértices em ordem crescente de distância (em número de arestas) do vértice atual.

A busca em largura pode ser implementada usando uma fila para manter registro dos próximos vértices a serem visitados. Inicialmente, inserimos o vértice de origem, $s$, na fila. Depois, enquanto ainda houver vértices na fila, removemos o primeiro vértice da fila e visitamos todos os vértices adjacentes a ele (que ainda não tenham sido visitados). Sempre que visitamos um novo vértice, o adicionamos ao final da fila, para termos certeza de que visitaremos seus vizinhos no futuro.

Refinando um pouco mais as ideias acima, podemos resumir a ideia centrao do algoritmo como:

  • Enquanto houver vértices na fila:

  • Remova um vértice v da fila

  • Se v ainda não tiver sido visitado:

  • Marque v como visitado

  • Adicione à fila todos os vizinhos de v que ainda não tenham sido visitados

Vejamos como traduzir as ideias acima para implementar o algoritmo de busca em largura.

def bfs(grafo, vertice_fonte):
    visitados, fila = set(), [vertice_fonte]
    while fila:
        vertice = queue.pop(0)
        if vertice not in visitados:
            visitados.add(vertice)
            fila.extend(grafo[vertice] - visitados)
    return visitados

A função acima pode ser invocada assim:

bfs(grafo, 'A')
{'B', 'C', 'A', 'F', 'D', 'E'}

Uma das principais aplicações de busca em largura é determinar o caminho mínimo entre dois vértices de um grafo. Assumindo que as arestas do grafo não tenham pesos associados a elas, é possível modificar a implementação de busca em largura para determinar se um vértice é alcançável a partir de outro e contar o número de arestas entre dois vértices (caminho mínimo). A próxima seção (que será disponibilizada em breve) explicará caminhos mínimos em grafos em mais detalhes.

Playground

# Use este espaço para praticar o que você aprendeu nesta seção. # Basta digitar o código no espaço abaixo e clicar 'run'.
Anterior Início Próximo