ULUMINE · Numérique et sciences informatiques (NSI) · Terminale
Les graphes : représentations et parcours
Un graphe modélise des relations ; on le représente par une matrice ou des listes d’adjacence, et on l’explore par des parcours.
Vocabulaire
- Sommets, arêtes (non orienté) ou arcs (orienté) ; graphe pondéré si les arêtes ont un poids.
- Degré = nombre de voisins ; somme des degrés = 2 × nombre d’arêtes.
- Chemin, cycle, graphe connexe.
Représentations
- Matrice d’adjacence : M[i][j] = 1 si i est relié à j ; n² cases ; symétrique si non orienté.
- Listes d’adjacence : dictionnaire sommet → liste des voisins.
Parcours
- Largeur : file, distance croissante, plus courts chemins en nombre d’arêtes.
- Profondeur : récursivité ou pile, détection de cycles.
- Mémoriser les sommets visités pour ne pas boucler.
Pièges à éviter
- Oublier de marquer les sommets visités : le parcours tourne indéfiniment dans un cycle.
- Confondre file (largeur) et pile (profondeur).
- Lire une ligne au lieu d’une colonne pour compter les arcs entrants.
- Oublier qu’une arête compte deux fois dans la somme des degrés.