Parcours en profondeur DFS en Python
DFS utilise la récursion ou une stack.
Qu’est-ce que Parcours en profondeur DFS en Python ?
DFS utilise la récursion ou une stack.
Explorer un chemin avant de revenir en arrière.
Quand l’utiliser ?
- Comprendre les algorithmes et structures de données.
- Observer chaque étape et traiter les cas limites.
- Comparer temps d’exécution et mémoire.
Visualisation de Parcours en profondeur DFS en Python
O(V+E)Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.
Code d’exemple
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"))Résultat attendu
['A', 'B', 'D', 'C', 'E']Fonctionnement
Chaque sommet et arête est traité au plus une fois : O(V+E).
Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.
Exercices pratiques
Modifiez les entrées et testez les cas limites avant d’utiliser des données plus volumineuses.
- Testez une entrée vide, un élément et des doublons.
- Affichez l’état après chaque étape.
- Comparez les performances avec une autre solution.