Algorithmes sur arbres et graphes

Parcours d'arbres, arbres de recherche, BFS, DFS, Dijkstra.

Parcours d'arbres binaires

Trois ordres de parcours: Préfixe (pré-ordre) : Racine → Gauche → Droite — utile pour copier ou sérialiser un arbre. Infixe (in-ordre) : Gauche → Racine → Droite — donne les valeurs dans l'ordre croissant pour un ABR. Suffixe (post-ordre) : Gauche → Droite → Racine — utile pour calculer la taille ou supprimer un arbre.
Arbre binaire de recherche (ABR): Propriété : pour tout nœud, toutes les valeurs du sous-arbre gauche sont strictement inférieures, celles du sous-arbre droit strictement supérieures. Recherche, insertion, suppression en O(log n) si l'arbre est équilibré. Dégénère en O(n) si les insertions sont triées (arbre filiforme = liste chaînée).

BFS — parcours en largeur: Breadth-First Search : explore tous les voisins du nœud courant avant de descendre plus profondément. Utilise une file (FIFO). Trouve le chemin le plus court en nombre d'arêtes dans un graphe non pondéré. Applications : réseaux sociaux (degrés de séparation), jeux (arbre de décision en largeur).
DFS — parcours en profondeur: Depth-First Search : explore aussi loin que possible avant de revenir en arrière (backtracking). Utilise une pile (LIFO) ou la récursion. Applications : détection de cycles, tri topologique, exploration de labyrinthes, composantes connexes. Plus économe en mémoire que BFS pour les graphes très larges.
Algorithme de Dijkstra: Trouve le plus court chemin depuis un sommet source vers tous les autres dans un graphe pondéré à poids positifs. Principe : à chaque étape, sélectionner le sommet non visité de distance minimale connue, puis mettre à jour les distances de ses voisins. Complexité O((V+E) log V) avec un tas min. Utilisé par les GPS et le routage réseau.

Matrice vs liste d'adjacence: Matrice d'adjacence : tableau n×n, [i][j]=1 si arête. Espace O(n²), accès en O(1). Adapté aux graphes denses. Liste d'adjacence : liste de voisins par sommet. Espace O(V+E), adapté aux graphes creux (peu d'arêtes — cas le plus fréquent). Le choix impacte la complexité des algorithmes.

Flashcards, mode examen et suivi de progression — gratuit pour commencer.