Légende de la leçon
Vert : définitions
I. Algorithmes de parcours de graphes
Dans les graphes, les algorithmes de parcours permettent de visiter les sommets et les arêtes du graphe de manière systématique.
1) Parcours en largeur d'abord (Breadth-First Search, BFS)
- Fonctionnement : BFS commence par un sommet source et explore tous les sommets voisins avant de passer aux sommets de niveau suivant. Il utilise une file d'attente pour garder la trace des sommets à visiter.
- Applications : Trouver le chemin le plus court dans un graphe non pondéré, tester la bipartition d'un graphe, etc.
2) Parcours en profondeur d'abord (Depth-First Search, DFS)
- Fonctionnement : DFS commence par un sommet source et explore aussi loin que possible le long de chaque branche avant de revenir en arrière. Il utilise une pile : explicitement avec une structure de pile, ou implicitement via la récursivité.
- Applications : Topologie de tri, composantes fortement connexes, puzzles et problèmes de labyrinthe, etc.
II. Algorithmes de parcours d'arbres
Les arbres, un type spécial de graphes, ont également des algorithmes de parcours spécifiques.
1) Parcours en ordre (Inorder Traversal)
- Fonctionnement : Dans les arbres binaires, il visite d'abord le sous-arbre gauche, puis le nœud racine, et enfin le sous-arbre droit. Cela donne une sortie triée pour les arbres binaires de recherche.
- Application : Affichage trié des données dans un arbre binaire de recherche.
2) Parcours préordre (Preorder Traversal)
- Fonctionnement : Visite d'abord le nœud racine, puis les sous-arbres gauche et droit. Utile pour copier un arbre.
- Application : Création d'une copie de l'arbre, représentation des expressions arithmétiques.
3) Parcours postordre (Postorder Traversal)
- Fonctionnement : Visite les sous-arbres gauche et droit avant de visiter le nœud racine. Utilisé pour supprimer un arbre.
- Application : Suppression ou libération de l'arbre, calcul de la valeur d'une expression arithmétique.
III. Complexité et optimisation
- La complexité de ces algorithmes dépend généralement du nombre de sommets (V) et du nombre d'arêtes (E) dans le graphe.
- BFS et DFS ont une complexité temporelle de O(V + E) dans le cas des graphes représentés par des listes d'adjacence.
Je retiens
