NSI : la checklist pour réussir les graphes

Les graphes, c'est un peu le couteau suisse de l'informatique : ils permettent de modéliser des réseaux sociaux, des itinéraires GPS, des dépendances de tâches, et même des circuits électriques. En NSI, tu les rencontres en Première et surtout en Terminale. Pas de panique : avec cette checklist, tu vas tout déchirer !

Qu'est-ce qu'un graphe en NSI ?

Un graphe, c'est un ensemble de sommets (ou nœuds) reliés par des arêtes (ou arcs). On distingue deux grandes familles :

• Graphe non orienté : les arêtes n'ont pas de direction. Exemple : un réseau d'amis sur Facebook (si A est ami avec B, B est ami avec A).
• Graphe orienté : les arcs ont un sens. Exemple : Twitter (A suit B, mais B ne suit pas forcément A).

On peut aussi avoir des graphes pondérés (chaque arête a un poids, comme une distance) ou non pondérés.

Comment représenter un graphe en Python ?

En NSI, tu dois connaître deux représentations principales :

1. Liste d'adjacence

Un dictionnaire où chaque clé est un sommet, et la valeur est la liste de ses voisins.

graphe = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

2. Matrice d'adjacence

Un tableau 2D (liste de listes) où la case [i][j] vaut 1 s'il y a une arête entre i et j, 0 sinon.

sommets = ['A', 'B', 'C', 'D']
matrice = [
    [0, 1, 1, 0],  # A
    [1, 0, 0, 1],  # B
    [1, 0, 0, 1],  # C
    [0, 1, 1, 0]   # D
]

La liste d'adjacence est souvent plus pratique pour les parcours.

Les parcours de graphe : BFS et DFS

Les deux algorithmes fondamentaux sont le parcours en largeur (BFS) et le parcours en profondeur (DFS). Ils servent à explorer tous les sommets d'un graphe.

Parcours en largeur (BFS)

Il explore niveau par niveau. On utilise une file (FIFO).

from collections import deque

def bfs(graphe, depart):
    visites = set()
    file = deque([depart])
    while file:
        sommet = file.popleft()
        if sommet not in visites:
            visites.add(sommet)
            print(sommet)
            for voisin in graphe[sommet]:
                if voisin not in visites:
                    file.append(voisin)
    return visites

Parcours en profondeur (DFS)

Il explore le plus loin possible avant de revenir en arrière. On utilise une pile (ou récursivité).

def dfs(graphe, depart, visites=None):
    if visites is None:
        visites = set()
    visites.add(depart)
    print(depart)
    for voisin in graphe[depart]:
        if voisin not in visites:
            dfs(graphe, voisin, visites)
    return visites

Astuce : retiens que BFS = file, DFS = pile (ou récursif).

Cas d'usage concret : trouver le plus court chemin

Un grand classique : avec BFS, on peut trouver le plus court chemin dans un graphe non pondéré. Il suffit de stocker le prédécesseur de chaque sommet.

def plus_court_chemin(graphe, depart, arrivee):
    visites = set()
    file = deque([depart])
    parents = {depart: None}
    while file:
        sommet = file.popleft()
        if sommet == arrivee:
            # reconstruire le chemin
            chemin = []
            while sommet is not None:
                chemin.append(sommet)
                sommet = parents[sommet]
            return chemin[::-1]
        if sommet not in visites:
            visites.add(sommet)
            for voisin in graphe[sommet]:
                if voisin not in visites and voisin not in parents:
                    parents[voisin] = sommet
                    file.append(voisin)
    return None  # pas de chemin

Conseils pour le bac NSI et les révisions

Pour être au point sur les graphes, voici ma checklist :

• ✅ Savoir représenter un graphe en Python (liste d'adjacence et matrice).
• ✅ Implémenter BFS et DFS sans hésiter.
• ✅ Utiliser BFS pour le plus court chemin.
• ✅ Comprendre la complexité : O(n+m) pour BFS/DFS (n sommets, m arêtes).
• ✅ S'entraîner sur des exercices types bac.

Tu peux trouver des exercices corrigés sur notre page d'exercices et des fiches de révision sur les fiches NSI. N'oublie pas de consulter aussi les cours complets sur la page cours.

Si tu veux approfondir avec des vidéos ou des quiz, jette un œil à AlloBac et AlloLycée.

Erreurs fréquentes à éviter

• Oublier de marquer les sommets visités : sinon boucle infinie !
• Confondre BFS et DFS : retiens file vs pile.
• Mal gérer les graphes orientés : vérifie le sens des arcs.
• Ne pas tester sur un petit exemple : toujours vérifier avec un graphe simple.

Conclusion

Les graphes, c'est un chapitre clé en NSI. Avec cette checklist, tu as toutes les cartes en main pour réussir. Entraîne-toi régulièrement, et n'hésite pas à revenir sur les notions qui coincent. Tu vas y arriver !