NSIChapitre 5

Algorithmique : arbres et graphes

L'essentiel en 30 secondes

Les arbres se parcourent en profondeur (préfixe: R-G-D, infixe: G-R-D, suffixe: G-D-R) ou en largeur (niveau par niveau avec une file). Les graphes se représentent par matrice d'adjacence ($O(V^2)$) ou liste d'adjacence ($O(V+E)$) et se parcourent en profondeur (DFS, pile, $O(V+E)$) ou en largeur (BFS, file, $O(V+E)$). BFS donne le plus court chemin non pondéré. L'algorithme de Dijkstra trouve le plus court chemin pondéré (poids $\\geq 0$, complexité $O(V^2)$).

Les notions à connaître

Parcours préfixe (préordre): Racine $\to$ sous-arbre gauche $\to$ sous-arbre droit. On traite le nœud AVANT ses fils. Utile pour copier un arbre ou évaluer une expression préfixée.
Parcours infixe (inordre): Sous-arbre gauche $\to$ Racine $\to$ sous-arbre droit. Sur un ABR, donne les valeurs dans l'ordre croissant. C'est le parcours naturel pour afficher un arbre trié.
Parcours suffixe (postordre): Sous-arbre gauche $\to$ sous-arbre droit $\to$ Racine. On traite le nœud APRÈS ses fils. Utile pour supprimer un arbre ou évaluer une expression postfixée (notation polonaise inverse).
Parcours en largeur (BFS): Parcours niveau par niveau avec une file (FIFO). Permet de trouver le plus court chemin en nombre d'arêtes dans un graphe non pondéré. Complexité $O(V + E)$ .
Parcours en profondeur (DFS): Explore le plus loin possible avant de revenir en arrière. Utilise une pile ou la récursion. Complexité $O(V + E)$ . Utile pour détecter des cycles, faire un tri topologique.
Graphe: Structure composée de sommets (vertices, V) reliés par des arêtes (edges, E). Orienté (arcs avec direction) ou non orienté. Pondéré (poids sur les arêtes) ou non pondéré.
Matrice d'adjacence: Tableau 2D de taille $V \times V$ . M[i][j] = 1 (ou poids) si arête entre i et j, 0 sinon. Avantage : test d'adjacence en $O(1)$ . Inconvénient : espace $O(V^2)$ .
Liste d'adjacence: Dictionnaire {sommet: [voisins]}. Plus économe en mémoire pour les graphes peu denses : $O(V + E)$ . Parcours des voisins en $O(degré)$ .

Les erreurs à éviter en nsi

Utiliser une pile au lieu d'une file pour BFS (ou inversement pour DFS)
BFS = file (deque + popleft). DFS = pile (list + pop). Confondre les deux change complètement l'ordre de parcours.
Oublier de marquer les sommets visités dans un parcours de graphe
Sans ensemble visités, on boucle indéfiniment sur les cycles. Toujours ajouter au set AVANT $d'enfiler/empiler.$
Appliquer Dijkstra sur un graphe à poids négatifs
Dijkstra suppose tous les poids $\geq 0$ . Avec des poids négatifs, le résultat peut être faux.
Confondre matrice d'adjacence et liste d'adjacence
Matrice : tableau 2D, bon pour graphes denses. Liste : dictionnaire de listes, bon pour graphes peu denses (creux).
Oublier la symétrie dans un graphe non orienté
Si A—B existe, il faut ajouter B dans les voisins de A ET A dans les voisins de B.

Sais-tu répondre à ces questions ?

Les corrigés détaillés sont dans le quiz du chapitre.

Comment appelle-t-on un graphe dont les arêtes ont une direction (un sens) ?
Quelle structure de données utilise l'algorithme de parcours en largeur (BFS) ?
Quelle structure de données est naturellement associée au parcours en profondeur (DFS) d'un graphe ?
On représente un graphe par un dictionnaire d'adjacence : graphe = { 'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D', 'E'], 'D': ['B', 'C'], 'E': ['C'] } Combien d'arêtes possède ce graphe non orienté ?
On effectue un BFS sur le graphe suivant à partir du sommet A : graphe = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } Dans quel ordre les sommets sont-ils visités ? (On traite les voisins dans l'ordre de la liste)

Accède à la fiche complète

Crée ton compte gratuit pour lire la fiche en entier et accéder à 7 000+ contenus de révision.

Créer un compte gratuit Se connecter