Parcours en largeur BFS en Python
BFS visite d’abord les voisins directs grâce à une queue.
Qu’est-ce que Parcours en largeur BFS en Python ?
BFS visite d’abord les voisins directs grâce à une queue.
Explorer un graphe niveau par niveau.
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 largeur BFS en Python
O(V+E)Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.
Code d’exemple
main.py
from collections import deque
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
queue = deque(["A"])
visited = {"A"}
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
print(order)Résultat attendu
['A', 'B', 'C', 'D', 'E']Fonctionnement
Un ensemble visited évite les répétitions : temps O(V+E), mémoire O(V).
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.