Rafael Alves ITM

Algoritmo de busca em profundidade em Python

Leitura de 3 min

🎯 Algoritmo de Busca em Profundidade em Python

Em poucas palavras

Note que os nós são explorados na ordem inversa em que foram adicionados ao dicionário, pois a estrutura de pilha remove sempre o último elemento inserido (stack.pop()).

📝 Notas e Desenvolvimento

🔗 Conexões e Contexto

📚 Referências e Fontes

Citações Diretas

📂 Outros Conteúdos Preservados

Busca em Profundidade (DFS) em Python

Abaixo está a implementação padrão do Algoritmo de busca em profundidade utilizando a Python. Esta versão utiliza uma estrutura de dados de Pilha (stack) iterativa para simular o comportamento de recursão do algoritmo.

Python

def dfs(tree: Dict[str, List[str]], start: str, end: str) -> Optional[List[str]]:
    """Implementa o algoritmo DFS iterativo de forma otimizada utilizando uma
 
    pilha e rastreamento de nós visitados.
 
    Args:
        tree (Dict[str, List[str]]): Lista de adjacência representando o grafo
          ou árvore.
        start (str): O vértice inicial de exploração.
        end (str): O vértice destino.
 
    Retorna:
        Optional[List[str]]: O caminho do início ao fim se encontrado, senão
        None.
    """
    if start == end:
        return [start]
 
    # Estruturas para otimização de performance
    stack: List[str] = [start]
    visited: Set[str] = {start}
 
    # Dicionário para reconstruir o caminho eficiente: {nó_filho: nó_pai}
    parent_map: Dict[str, str] = {}
 
    while stack:
        vertex = stack.pop()
 
        if vertex == end:
            # Reconstrói o caminho de trás para frente a partir do parent_map
            path = []
            current = end
            while current != start:
                path.append(current)
                current = parent_map[current]
            path.append(start)
            return path[::-1]  # Inverte para o sentido correto (start -> end)
 
        # Processa os vizinhos na ordem inversa para manter o padrão visual de exploração (Esquerda -> Direita)
        for neighbor in reversed(tree.get(vertex, [])):
            if neighbor not in visited:
                visited.add(neighbor)
                parent_map[neighbor] = vertex
                stack.append(neighbor)
 
    return None

💻 Exemplo de Execução e Resposta

Para testar o algoritmo, definimos uma estrutura de árvore enraizada em A utilizando um dicionário, onde o objetivo final é encontrar o caminho até o nó K. A exemplo do grafo a seguir:

graph TD
    A --> B
    A --> C
    A --> D
    
    B --> E
    
    C --> F
    C --> G
    
    D --> H
    
    E --> I
    E --> J
    
    F --> K

 
### Representação da estrutura em árvore
 
tree: Dict[str, List[str]] = {
	"A": ["B", "C", "D"],
	"B": ["E"],
	"C": ["F", "G"],
	"D": ["H"],
	"E": ["I", "J"],
	"F": ["K"],
	"G": [],
	"H": [],
	"I": [],
	"J": [],
	"K": [],
}
 
caminho_encontrado = dfs(tree, "A", "K")
print(f"Caminho final: {caminho_encontrado}")

📄 Saída do Terminal

Comportamento da Pilha (LIFO)

Note que os nós são explorados na ordem inversa em que foram adicionados ao dicionário, pois a estrutura de pilha remove sempre o último elemento inserido (stack.pop()).

Explorando nó A
Nós adjacentes descobertos:  C B D
Explorando nó D
Nós adjacentes descobertos:  H
Explorando nó H
Nó folha ou sem novas ramificações.
Explorando nó B
Nós adjacentes descobertos:  E
Explorando nó E
Nós adjacentes descobertos:  I J
Explorando nó J
Nó folha ou sem novas ramificações.
Explorando nó I
Nó folha ou sem novas ramificações.
Explorando nó C
Nós adjacentes descobertos:  G F
Explorando nó F
Nós adjacentes descobertos:  K
Explorando nó K
 
Caminho final: ['A', 'C', 'F', 'K']

Visão de gráfico

Backlinks