BFS Python

A pesquisa no campo da programação é dividida principalmente em dois tipos, Pesquisa em profundidade (DFS) e Pesquisa Primeira Livre (BFS). Estes são os algoritmos de pesquisa usados ​​para pesquisar ou atravessar no gráfico.

A primeira pesquisa é o fenômeno de atravessar todos os nó do gráfico ou uma árvore, então cada nó é atravessado por duas partes. Um é a parte 'visitada', e a outra é a parte 'não visitada'. Isso significa que esta pesquisa tem como objetivo atingir todos os nó do gráfico.

Pseudocódigo e algoritmo BFS

• O primeiro passo é colocar qualquer nó de primeira fonte na fila da parte traseira.
• Crie a lista ou matriz visitado e depois coloque os nós.
• Use um loop de tempo para verificar se a fila não está vazia e continue removendo itens na lista visitada.
• Todos os itens removidos são marcados como visitados e agora também removem os vizinhos que não são visitados da fila também.

Aplicações do BFS

• É usado para navegação por GPS.
• É utilizado para encontrar o caminho.
• É utilizado para construir o índice por índice de pesquisa.
• Implementação de BFs.

Exemplo 1

Primeiro, apresentamos o gráfico; Queremos ter os valores que devem ser atravessados. Cada nó contém ainda os valores. Por exemplo, aqui, o primeiro número 5 se conectará aos dois nós 3 e 7. Da mesma forma, todos os outros números estão conectados com outros nós para formar um gráfico. Após definir o gráfico, conteremos dois tipos de dados inteiros para armazenar os valores numéricos do gráfico que devem ser visitados. Enquanto o outro inclui os nós que estão próximos dos que são visitados.

Visitado = []
Fila = []

Ambas as matrizes estão vazias no momento de iniciar a grande pesquisa. Mas gradualmente, essas matrizes contêm os valores dos nós, como descrevemos no gráfico.

Depois de introduzir duas matrizes, definiremos uma função para acessar e pesquisar todos os nós em termos de linha. Esta função leva os valores da matriz visitada, o gráfico e o terceiro é o nó. Dentro da função, adicionaremos valores nas duas matrizes, conforme descrito no algoritmo; Primeiro, os valores são inseridos dentro da 'fila'; Quando é visitado, esse nó em particular é transferido para a fila visitada. Então, por enquanto, essa função adicionará os valores nas matrizes usando uma função de apêndice para cada matriz. Esta função contém os nós como um parâmetro nela.

Visitado.Anexar (nó)
Fila.Anexar (nó)

Depois disso, agora vamos acessar e visitar os nós através de uma abordagem. Essa maneira de acessar os nós é semelhante ao acesso a matrizes, porque sempre aplicamos um loop para visitar cada índice iterativamente. No caso do BFS, usaremos um loop de tempo e, dentro disso, o loop, um loop for adicionado para satisfazer a condição usada pelo loop while.

Enquanto o loop atingirá diretamente a fila, porque os nós serão adicionados à fila primeiro e depois à matriz visitada. Portanto, os valores serão extraídos através da função pop () e serão armazenados nas respectivas variáveis.

M = fila. Pop (0)

Este valor será exibido na chamada da função de impressão. Agora, quando os valores da fila forem extraídos, esse valor será usado para localizar seus vizinhos a serem inseridos na fila. Então, usaremos o loop aqui para alocar cada vizinho até o final do gráfico. A condição aplicada aqui é que, se o valor não estiver na matriz visitada, significa que não foi acessada anteriormente, a matriz visitada será adicionada por esses novos valores (vizinho) através da função de apêndice. E da mesma forma, a fila também receberá o valor dos novos vizinhos.

Visitado. Anexar (vizinho)

A chamada de função é feita junto com a matriz visitada, o gráfico inteiro e o nó como um parâmetro.

BFS (visitado, gráfico, '5')

Depois de usar este código, você pode ver a saída relevante através do console resultante usando o botão de execução na parte superior da barra de ferramentas.

Você pode ver que todo o caminho será acessado através dos nós. Uma coisa pode ser observada aqui: todos esses nós iniciais são exibidos apenas porque cada vez antes do recurso de impressão, esses nós são exibidos da fila.

Exemplo 2

Este exemplo funciona na mesma técnica: pesquisar dentro do gráfico ou uma árvore. Mas aqui, usamos a abordagem do OOP (programação orientada a objetos) em Python usando o sistema de classe. Então, primeiro, vamos importar alguns recursos da biblioteca de coleções. Esses recursos incluem o "DefaultDict" que contém o dicionário na linguagem Python.

Movendo -se em direção à classe, primeiro, definimos o nome da classe e dentro da classe, aqui está o construtor. Como os construtores são os recursos executados automaticamente à medida que criamos o objeto da classe. O objeto da classe é necessário para acessar os recursos da classe. Também criaremos o objeto para a classe de gráfico posteriormente no artigo. Primeiro, o construtor é definido aqui para inicializar a lista tomada como um gráfico.

DefaultDict (lista)

"Is" usado para armazenar o gráfico no dicionário padrão.

Depois disso, uma função é usada aqui, 'adicionada' para adicionar o novo nó ou borda ao gráfico. Os nós também são conhecidos como bordas e são representados por 'u,.'Por outro lado, a distância entre as bordas é representada pelo vértice e é mencionada por' V.'Então, dentro da função, o gráfico será entretido com novos nós através da função de apêndice.

Auto.Gráfico [U]. Anexar (V)

Aqui também usamos uma função para exibir o BFS de um gráfico. Inicialmente, todos os nós são declarados como não são visitados. Na primeira etapa da pesquisa, declararemos o status como falso.

Visitado = [false] * (max (self.gráfico) + 1)

Da mesma forma, a fila é inicializada como zero no momento da criação.

Fila = []

Vamos agora falar sobre o nó de origem, que é o primeiro; Vamos entrar na matriz visitada e extraí -la da fila como fizemos no primeiro exemplo.

Fila.Anexar (s)
Visitado [s] = true

Agora, há um tempo, o loop é usado para despedir todos os nós da fila e depois imprimirá o valor.

S = fila.pop (0)

Depois disso, todos os nós do vizinho adjacente serão extraídos da fila; Se algum nó já estiver visitado, isso será inserido na fila visitada. Se a estatura for usada para verificar se o nó ainda não foi visitado, anexe-o da fila e digite-a na matriz visitada.

G = Graph () é de alguma forma uma maneira da criação de objetos do construtor, e esse objeto é ainda mais usado para chamar a função adicionada junto com os valores do vizinho.

Conclusão

O artigo 'BFS-Python' contém uma breve descrição da pesquisa de largura no gráfico para atravessar cada nó. Esse processo de pesquisa é feito com duas listas que contêm os nós visitados e não visitados neles. Elaboramos o conceito adicionando dois exemplos elementares no guia.