A seguir está a implementação do [[Algoritmo de busca em profundidade]] em [[Linguagem de programação Python|Python]]
```python
def dfs(tree, start, end):
"""
Implementa o algoritmo DFS
Args:
tree (dict): A árvore
start (str): O vértice inicial
end (str): O vértice final
Retorna:
list: O caminho do início ao fim
"""
stack = [(start, [start])] # Tupla (vértice, caminho)
while stack: # enquanto a pilha não estiver vazia
(vertex, path) = stack.pop() # Pega o último elemento
print(f"Explorando nó {vertex}")
print(f"Nó encontrado ", end="")
for next in set(tree[vertex]) - set(path): # Pega o próximo vértice
print(f"{next} ", end="")
if next == end: # Se o próximo vértice for o final, retorna o caminho
return path + [next]
else: # Senão, adiciona o próximo vértice à pilha
stack.append((next, path + [next]))
print()
```
# Exemplo de Execução e Resposta
Abaixo está um exemplo de uma árvore e a resposta do algoritmo apresentado anteriormente.
```python
tree = {
'A': ['B', 'C', 'D'],
'B': ['E', ],
'C': ['F', 'G'],
'D': ['H'],
'E': ['I', 'J'],
'F': ['K'],
'G': [],
'H': [],
'I': [],
'J': [],
'K': []
}
dfs(tree, 'A', 'K')
```
Resultado em:
```
Exploring node A
Found node C D B
Exploring node B
Found node E
Exploring node E
Found node I J
Exploring node J
Found node
Exploring node I
Found node
Exploring node D
Found node H
Exploring node H
Found node
Exploring node C
Found node G F
Exploring node F
Found node K
['A', 'C', 'F', 'K']
```