Busca em profundidade DFS em Python
DFS usa recursão ou um stack explícito.
O que é Busca em profundidade DFS em Python?
DFS usa recursão ou um stack explícito.
Siga um caminho antes de retroceder.
Quando usar?
- Entender algoritmos e estruturas de dados.
- Observar cada etapa e tratar casos de borda.
- Comparar tempo de execução e memória.
Visualizador de Busca em profundidade DFS em Python
O(V+E)Use Executar ou Passo para acompanhar cada comparação e movimento dos dados.
Código de exemplo
main.py
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
def depth_first(node, visited=None):
visited = visited or set()
visited.add(node)
order = [node]
for neighbor in graph[node]:
if neighbor not in visited:
order.extend(depth_first(neighbor, visited))
return order
print(depth_first("A"))Saída esperada
['A', 'B', 'D', 'C', 'E']Como funciona
Cada vértice e aresta é processado no máximo uma vez: O(V+E).
Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.
Exercícios práticos
Altere as entradas e teste casos de borda antes de usar conjuntos de dados maiores.
- Teste entrada vazia, um elemento e duplicados.
- Mostre o estado após cada etapa.
- Compare o desempenho com outra solução.