EazyReviz

L'essentiel en 30 secondes

Les arbres se parcourent en profondeur (préfixe, infixe, suffixe) ou en largeur (niveau par niveau avec une file). Les graphes se représentent par matrice ou liste d'adjacence et se parcourent en profondeur (DFS, pile/récursion) ou en largeur (BFS, file). L'algorithme de Dijkstra trouve le plus court chemin dans un graphe pondéré à poids positifs.

Notions clés

Parcours préfixe (préordre): Racine $\to sous-arbre$ gauche $\to sous-arbre$ droit. Ordre de visite : on traite le nœud AVANT ses fils.
Parcours infixe (inordre): $Sous-arbre$ gauche $\to$ racine $\to sous-arbre$ droit. Sur un ABR, donne les valeurs dans l'ordre croissant.
Parcours en largeur (BFS): Parcours niveau par niveau avec une file. Permet de trouver le plus court chemin en nombre d'arêtes.
Graphe orienté / non orienté: Orienté : les arêtes ont un sens (arcs). Non orienté : les arêtes sont symétriques.
Algorithme de Dijkstra: Trouve le plus court chemin depuis un sommet source dans un graphe pondéré $à$ poids $\geq 0$ . Complexité $O(n^2)$ version simple.

Formules

Parcours préfixe (récursif)

`def prefixe(arbre):\n if arbre is None:\n return\n print(arbre.valeur) # traitement\n prefixe(arbre.gauche)\n prefixe(arbre.droit)`

Condition : Infixe : déplacer print entre les deux appels. Suffixe : après les deux appels.

Parcours en largeur (arbre ou graphe)

`from collections import deque\ndef bfs(graphe, depart):\n file = deque([depart])\n visites = {depart}\n while file:\n s = file.popleft()\n for voisin in graphe[s]:\n if voisin not in visites:\n visites.add(voisin)\n file.append(voisin)\n return visites`

Condition : Utilise une file (deque). Complexité O(V + E) avec V sommets et E arêtes.

Dijkstra (simplifié)

`def dijkstra(graphe, src):\n dist = {s: float('inf') for s in graphe}\n dist[src] = 0\n visites = set()\n while len(visites) < len(graphe):\n s = min((s for s in dist if s not in visites), key=dist.get)\n visites.add(s)\n for voisin, poids in graphe[s]:\n if dist[s] + poids < dist[voisin]:\n dist[voisin] = dist[s] + poids\n return dist`

Condition : graphe = dict de listes de (voisin, poids). Ne fonctionne PAS avec des poids négatifs.

A retenir

BFS utilise une FILE, DFS utilise une PILE (ou la récursion). Moyen mnémo : BFS = Breadth = File (F/F).
Le parcours infixe d'un ABR donne les valeurs triées dans l'ordre croissant.
Dijkstra ne fonctionne PAS avec des poids négatifs — condition à vérifier systématiquement.

Erreurs classiques

Erreur : Utiliser une pile au lieu d'une file pour BFS (ou inversement pour DFS)

Correction : BFS = file (deque + popleft). DFS = pile (list + pop). Confondre les deux change complètement le parcours.

Erreur : Oublier de marquer les sommets visités dans un parcours de graphe

Correction : Sans ensemble visités, on boucle indéfiniment sur les cycles. Toujours ajouter au set AVANT d'enfiler.

Erreur : Appliquer Dijkstra sur un graphe à poids négatifs

Correction : Dijkstra suppose tous les poids $\geq 0$ . Avec des poids négatifs, utiliser $Bellman-Ford$ (hors programme).

Astuce méthode