A seguir está uma implementação do [[Algoritmo de busca em largura]] em [[Linguagem de programação Python|Python]].
```python
def bfs(tree, start, end) -> list:
"""
Implementa o algoritmo BFS para percorrer uma árvore,
imprimindo os passos e o
Argumentos:
tree (dict): A árvore a ser percorrida
start (str): O nó inicial
end (str): O nó final, se houver
"""
print(f"Iniciando o algoritmo BFS do nó {start} para o nó {end}")
queue = [start] # Começa com o primeiro nó
visited = [] # Cria uma lista de nós visitados
print()
while queue: # Enquanto houver nós a serem visitados
node = queue.pop(0) # Pega o primeiro nó
print(f"Explorando o nó '{node}'")
if node não foi visitado: # Se o nó não foi visitado
visited.append(node) # Adiciona-o à lista de nós visitados
if node == end: # Se o nó é o nó final,
print()
print(f"Nó {end} encontrado, e BFS foi {visited}")
return visited
print(f"Nós encontrados {tree[node]}")
queue.extend(tree[node]) # caso contrário, adiciona os filhos do nó à fila
print(f"Nós visitados: {visited} | Fila: {queue}")
print()
print(f"Nó {end} não foi encontrado, mas BFS foi {visited}") # Se o nó final não foi encontrado, retorna os nós visitados
return visited
```
# Exemplo e Resposta
O seguinte mostra o uso do algoritmo acima em um exemplo, bem como sua resposta
```python
tree = {
'A': ['B', 'C', 'D'],
'B': ['E', ],
'C': ['F', 'G'],
'D': ['H'],
'E': ['I', 'J'],
'F': ['K'],
'G': [],
'H': [],
'I': [],
'J': [],
'K': []
}
bfs(tree, 'A', 'K')
```
Tendo a resposta
```
Iniciando o algoritmo BFS do nó A para o nó K
Explorando o nó 'A'
Nós encontrados ['B', 'C', 'D']
Nós visitados: ['A'] | Fila: ['B', 'C', 'D']
Explorando o nó 'B'
Nós encontrados ['E']
Nós visitados: ['A', 'B'] | Fila: ['C', 'D', 'E']
Explorando o nó 'C'
Nós encontrados ['F', 'G']
Nós visitados: ['A', 'B', 'C'] | Fila: ['D', 'E', 'F', 'G']
...
Explorando o nó 'K'
Nó K encontrado, e BFS foi ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K']
```
**:: Referência ::** [[Lesson 1 - Introduction to artificial intelligence]]