A Pesquisa por Largura (BFS) é um dos algoritmos mais populares para pesquisar ou percorrer uma estrutura de dados em árvore ou gráfico. Neste tutorial, aprenderemos brevemente como o BFS funciona e exploraremos um padrão básico que pode ser usado para resolver alguns problemas médios e fáceis no Leetcode.

Vamos começar, sim?

Portanto, todos sabemos que um gráfico é um conjunto de vértices e arestas: G = {V, E}. Atravessar um gráfico significa visitar todos os vértices e arestas exatamente uma vez de maneira ordenada.

No BFS, somos obrigados a percorrer o gráfico em termos de largura ou nível. Isso significa que primeiro moveríamos horizontalmente e visitaríamos todos os nós da camada atual antes de passar para a próxima camada.

Portanto, sempre que somos solicitados a fazer alguma passagem de ordem de nível, nós podemos usar a técnica BFS.

image 154

No BFS, começamos a atravessar a partir de 1 (o nó raiz) e visitamos seus nós filhos 8, 5 e 2. Armazená-los na ordem em que foram visitados. Isso nos permitiria visitar os nós filhos de 8 primeiro (ou seja, 6, 4 e 3), depois de 5 (ou seja, nulo) e depois de 2 (ou seja, 9) e assim por diante.

Implementação

Para implementar o BFS, um fila estrutura de dados é usada. A fila armazena o nó e o marca como ‘visitado’ até que todos os seus vértices adjacentes sejam marcados.

A fila segue o método FIFO (primeiro a entrar, primeiro a sair). Isso significa que os vizinhos do nó serão visitados na ordem em que foram inseridos.

Feitiço BFS:

  1. Adicionar um nó à fila
  2. Remover nó
  3. Recupere vizinhos não visitados do nó removido e adicione-os à fila
  4. Repita as etapas 1, 2 e 3, desde que a fila não esteja vazia.

Agora, vamos examinar alguns problemas do Leetcode e aplicar o que aprendemos.

102. Transversal de ordem de nível de árvore binária (dificuldade: média)

A pergunta nos pede para percorrer o gráfico e imprimir os nós em cada nível em uma lista vinculada. Para resolver este, tudo o que precisamos fazer é aplicar nosso feitiço!

image 157

Certifique-se de entender bem o código, pois esse é o modelo básico usaremos para resolver vários problemas. Então, vamos passar por isso.

No código acima, primeiro inserimos o nó raiz na fila. Enquanto a fila não está vazia, removemos esse nó da fila e inserimos seu filho esquerdo e direito na fila.

Mas antes disso, verificamos se cada um de seus filhos é nulo ou não. Se nulo, teríamos recebido uma exceção de ponteiro nulo.

O processo é repetido novamente com os próximos elementos que permanecem na fila. o para laço é mantido para fornecer a lista de nós em cada nível em listas vinculadas separadas.

637. Média de níveis em uma árvore binária (Dificuldade: Fácil)

Esta pergunta nos diz para encontrar o valor médio dos nós em cada nível de uma árvore binária em uma matriz. Isso segue o mesmo procedimento que o nosso problema anterior, com um pequeno ajuste.

image 159

Como você pode ver, tudo o que fizemos foi copiar e colar o código do modelo. Em seguida, simplesmente colocamos uma variável sum no loop for que pode nos dar a soma dos valores dos nós em cada nível. É isso que usaremos para calcular nossa média desejada.

429. Ordem de nível de árvore N-ária, transversal (Dificuldade: Média)

Uma árvore na qual cada nó possui não mais que N número de filhos é chamado de árvore N-ária.

image 173

Isso segue exatamente o mesmo procedimento que a travessia de uma árvore binária, exceto pelo fato de que aqui inserimos todos os filhos de um nó na fila. Lembre-se de que, ao resolver problemas relacionados à árvore binária, apenas inserimos os filhos esquerdo e direito de qualquer nó na fila.

Isso é tudo! Espero que isso tenha ajudado você a entender melhor o BFS e que tenha gostado do tutorial. Por favor, recomende este post se você acha que pode ser útil para outra pessoa!



Fonte