Comment organiser ses révisions des graphes en NSI

Les graphes sont une notion centrale en NSI, que ce soit en Première ou en Terminale. Ils modélisent des relations entre objets : réseaux sociaux, itinéraires, dépendances de tâches... Pour le bac, tu dois maîtriser les parcours de graphe (BFS et DFS) et savoir les implémenter en Python. Pas de panique : avec une bonne organisation, ces notions deviennent claires. Voici un plan de révision pas à pas.

1. Comprendre ce qu'est un graphe en NSI

Un graphe est un ensemble de sommets (ou nœuds) reliés par des arêtes (ou arcs). En NSI, on distingue :

• Graphe non orienté : les arêtes sont symétriques (ex : amitié Facebook).
• Graphe orienté : les arcs ont un sens (ex : follow Twitter).
• Graphe pondéré : chaque arête a un poids (ex : distance).

On représente un graphe en Python avec une liste d'adjacence (dictionnaire) ou une matrice d'adjacence. La liste est plus efficace en mémoire pour les graphes creux.

# Exemple : graphe non orienté (liste d'adjacence)
graphe = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

2. Maîtriser les parcours de graphe

Les deux algorithmes fondamentaux sont le parcours en largeur (BFS) et le parcours en profondeur (DFS). Ils permettent de visiter tous les sommets accessibles depuis un sommet de départ.

BFS (Breadth-First Search)

Il explore niveau par niveau, en utilisant une file. Utile pour trouver le plus court chemin dans un graphe non pondéré.

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

DFS (Depth-First Search)

Il explore en profondeur en utilisant une pile (ou récursivement). Utile pour la détection de cycles, le tri topologique, etc.

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

3. Cas d'usage concrets

Les graphes sont partout :

• Réseaux sociaux : trouver les amis d'amis (BFS).
• GPS : calcul d'itinéraire (algorithme de Dijkstra).
• Ordonnancement de tâches : tri topologique (DFS).
• Jeux : résolution de labyrinthe.

Pour t'entraîner, tu peux télécharger des exercices corrigés sur les graphes et consulter les fiches de révision.

4. Méthode de révision efficace

Voici une routine en 4 étapes :

1. Théorie : relis ton cours sur les cours NSI et note les définitions clés.
2. Implémentation : code toi-même BFS et DFS sur des exemples simples.
3. Exercices : fais des exercices d'application (parcours, plus court chemin, détection de cycle).
4. Annales : entraîne-toi sur des sujets de bac : ils tombent souvent en exercice 3 ou 4.

Pour approfondir, tu peux aussi regarder des vidéos sur Allo Lycée ou consulter Allo Bac pour des conseils supplémentaires.

5. Pièges à éviter

• Confondre BFS et DFS : retiens que BFS utilise une file, DFS une pile.
• Oublier de marquer les visites : sans cela, tu boucles infiniment.
• Ne pas tester sur des graphes orientés : adapte les voisins en conséquence.
• Implémenter sans comprendre : dessine le graphe et simule l'algorithme à la main.

6. Conclusion

Les graphes sont un chapitre passionnant et très valorisé au bac. En suivant cette méthode, tu seras capable de coder les parcours les yeux fermés. N'oublie pas de t'entraîner régulièrement et de consulter les ressources du site nsi-lycee.fr. Bonnes révisions !