Les graphes sont partout : dans les réseaux sociaux, les cartes GPS, le web lui-même. En spécialité NSI, savoir les coder en Python est une compétence clé pour le bac. Dans cet article, on va démystifier les graphes : comment les représenter, les parcourir, et les utiliser dans des exercices concrets. Pas de panique, on va y aller pas à pas, avec des exemples que tu pourras tester toi-même.
Qu'est-ce qu'un graphe en informatique ?
Un graphe est une structure de données composée de sommets (ou nœuds) reliés par des arêtes (ou arcs). Si les arêtes ont une direction, on parle de graphe orienté ; sinon, on dit qu'il est non orienté. On peut aussi pondérer les arêtes (par exemple avec une distance).
En NSI, on manipule souvent des graphes pour modéliser des problèmes : un réseau routier, un réseau social, un labyrinthe, etc. Savoir les coder permet de résoudre des problèmes comme trouver le plus court chemin ou détecter une connexion entre deux sommets.
Représenter un graphe en Python
Il existe plusieurs façons de représenter un graphe en Python. Les deux plus courantes en NSI sont la liste d'adjacence et la matrice d'adjacence.
Liste d'adjacence
La liste d'adjacence consiste à associer à chaque sommet la liste de ses voisins. En Python, on peut utiliser un dictionnaire où les clés sont les sommets et les valeurs sont des listes de voisins.
# Graphe non orienté
adj = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}Pour un graphe orienté, on liste les successeurs. Cette représentation est efficace en mémoire pour les graphes peu denses.
Matrice d'adjacence
La matrice d'adjacence est un tableau à deux dimensions où M[i][j] vaut 1 (ou le poids) s'il existe une arête du sommet i au sommet j, sinon 0. En Python, on utilise une liste de listes.
# Graphe non orienté avec 4 sommets : 0,1,2,3
M = [
[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[0, 1, 1, 0]
]La matrice est symétrique pour un graphe non orienté. Cette représentation est simple mais peut être coûteuse en mémoire si le graphe est grand.
Les parcours de graphe : BFS et DFS
Un parcours de graphe consiste à visiter tous les sommets d'un graphe de manière systématique. Deux algorithmes fondamentaux : le parcours en largeur (BFS) et le parcours en profondeur (DFS).
Parcours en largeur (BFS)
Le BFS explore les sommets par niveaux : on part d'un sommet, puis on visite tous ses voisins, puis les voisins des voisins, etc. On utilise une file (FIFO).
from collections import deque
def bfs(adj, depart):
visites = set()
file = deque([depart])
visites.add(depart)
while file:
sommet = file.popleft()
print(sommet) # Traitement
for voisin in adj[sommet]:
if voisin not in visites:
visites.add(voisin)
file.append(voisin)
# Test avec notre graphe
bfs(adj, 'A') # A B C D E FLe BFS est utile pour trouver le plus court chemin dans un graphe non pondéré.
Parcours en profondeur (DFS)
Le DFS explore aussi loin que possible dans une branche avant de revenir en arrière. On utilise une pile (LIFO) ou la récursivité.
def dfs(adj, depart, visites=None):
if visites is None:
visites = set()
visites.add(depart)
print(depart)
for voisin in adj[depart]:
if voisin not in visites:
dfs(adj, voisin, visites)
# Test
dfs(adj, 'A') # A B D E F CLe DFS est utilisé pour la détection de cycles, la recherche de composantes connexes, etc.
Exemple concret : le plus court chemin avec BFS
Un cas d'usage classique : déterminer la distance minimale entre deux sommets dans un graphe non pondéré. Le BFS peut nous donner cela en modifiant légèrement le code.
def distance_bfs(adj, depart, arrivee):
if depart == arrivee:
return 0
visites = {depart}
file = deque([(depart, 0)])
while file:
sommet, dist = file.popleft()
for voisin in adj[sommet]:
if voisin == arrivee:
return dist + 1
if voisin not in visites:
visites.add(voisin)
file.append((voisin, dist + 1))
return -1 # pas de chemin
print(distance_bfs(adj, 'A', 'F')) # 2Ce genre d'algorithme est très demandé au bac, alors entraîne-toi à l'implémenter de mémoire.
Mise en pratique : exercices types
Voici quelques idées d'exercices que tu pourrais rencontrer en NSI :
- Écrire une fonction qui vérifie si deux sommets sont adjacents.
- Compter le nombre de composantes connexes d'un graphe (en utilisant DFS).
- Détecter un cycle dans un graphe orienté (avec DFS et couleurs).
- Implémenter l'algorithme de Dijkstra pour les graphes pondérés (en Terminale).
Pour t'entraîner, consulte nos exercices interactifs et nos fiches de révision sur les graphes.
Conseils pour le bac NSI
Au bac, tu devras souvent écrire un parcours de graphe ou l'utiliser pour résoudre un problème. Voici quelques conseils :
- Maîtrise les deux représentations (liste et matrice) et sache passer de l'une à l'autre.
- Entraîne-toi à écrire BFS et DFS sur papier, sans documentation.
- Comprends la différence entre file et pile, et pourquoi on les utilise.
- Teste ton code sur des petits graphes que tu dessines toi-même.
- Si tu bloques, revois les bases avec les cours en ligne.
N'oublie pas que la pratique régulière est la clé. Tu peux aussi consulter des ressources complémentaires sur AlloBac pour des annales corrigées.
Aller plus loin
Les graphes sont un vaste sujet. En Terminale, tu verras les graphes pondérés et l'algorithme de Dijkstra. En attendant, explore les algorithmes de tri et de recherche, et n'hésite pas à expérimenter avec des graphes plus grands.
Pour approfondir, tu peux aussi jeter un œil à AlloLycée qui propose des cours et exercices supplémentaires.
Conclusion
Voilà, tu as maintenant les bases pour coder les graphes en Python. On a vu les représentations, les parcours BFS et DFS, et un exemple concret. N'oublie pas : la clé, c'est de pratiquer. Reprends les exemples, modifie-les, et tu verras que ça devient naturel. Bon courage pour tes révisions, tu es sur la bonne voie !
