⌨ Spécialité NSI · Numérique et sciences informatiques Terminale Générale · Chapitre 4

Graphes : représentations et parcours

Vocabulaire des graphes (sommets, arêtes, arcs, degré, chemin, cycle, graphe orienté ou pondéré), représentations par matrice et liste d'adjacence, parcours en largeur et en profondeur, recherche d'un chemin et détection de cycle.

1. Vocabulaire

Définition

Un graphe est un ensemble de sommets reliés par des arêtes (ou des arcs s'il est orienté). Le degré d'un sommet est le nombre d'arêtes qui le touchent. Un chemin est une suite de sommets reliés ; un cycle est un chemin qui revient à son départ. Un graphe est pondéré si ses arêtes portent des valeurs (distances, coûts).

ABCDEFliste d'adjacenceA : B, DB : A, C, EC : B, FD : A, EE : B, D, FF : C, E
Un graphe non orienté de 6 sommets et 7 arêtes, et sa liste d'adjacence.

2. Représentations

Propriété · Matrice et liste d'adjacence

Matrice d'adjacence : tableau $n \times n$ où la case $(i, j)$ vaut $1$ s'il y a une arête entre $i$ et $j$. Liste d'adjacence : pour chaque sommet, la liste de ses voisins ; en Python, un dictionnaire {"A": ["B", "D"], "B": ["A", "C", "E"], ...}. La liste est plus économe pour les graphes peu denses.

3. Parcours

Méthode · Parcours en largeur (BFS)

from collections import deque
def largeur(g, depart):
    vus, ordre, f = {depart}, [], deque([depart])
    while f:
        s = f.popleft()
        ordre.append(s)
        for v in g[s]:
            if v not in vus:
                vus.add(v)
                f.append(v)
    return ordre

Il visite les sommets par distance croissante au départ : il donne les plus courts chemins (en nombre d'arêtes).

Méthode · Parcours en profondeur (DFS)

def profondeur(g, s, vus=None):
    if vus is None:
        vus = []
    vus.append(s)
    for v in g[s]:
        if v not in vus:
            profondeur(g, v, vus)
    return vus

Il va le plus loin possible avant de revenir en arrière ; il sert à détecter des cycles ou à tester la connexité.

Activité · Plus court chemin dans un labyrinthe

MatérielPython ; labyrinthe modélisé par un graphe (cases = sommets, passages = arêtes).
ConsigneAdapter le parcours en largeur pour mémoriser le prédécesseur de chaque sommet, puis reconstituer le chemin de l'entrée à la sortie.
RésultatUn dictionnaire pred rempli lors du parcours ; on remonte de la sortie à l'entrée grâce à pred.
BilanLe BFS donne un chemin comportant le moins de déplacements possible.

Attention · Sommets déjà visités

Sans mémoriser les sommets visités, un parcours tournerait indéfiniment dans les cycles.

⚠️ Une erreur dans ce cours ? Signalez-la

S'entraîner

Exercices corrigés

🎓 20 exercices corrigés et un quiz vous attendent dans ce chapitre.

Créez votre compte gratuit pour voir les corrections, faire les quiz et suivre votre progression.

2

Somme des degrés

★★☆

Calculer la somme des degrés des sommets du graphe ci-dessous. Lien avec le nombre d'arêtes ?

ABCDEF
Un graphe non orienté de 6 sommets (A à F).
🔒 Correction réservée aux membres Créer un compte gratuit →
5

Matrice d'adjacence

★★☆

Écrire la ligne de la matrice d'adjacence du sommet B du graphe ci-dessous (sommets dans l'ordre A à F).

ABCDEF
Un graphe non orienté de 6 sommets (A à F).
🔒 Correction réservée aux membres Créer un compte gratuit →
8

Parcours en largeur

★★☆

Donner l'ordre de visite du parcours en largeur du graphe ci-dessous depuis A (voisins dans l'ordre alphabétique).

ABCDEF
Un graphe non orienté de 6 sommets (A à F).
🔒 Correction réservée aux membres Créer un compte gratuit →
9

Parcours en profondeur

★★☆

Donner l'ordre du parcours en profondeur (récursif) du graphe ci-dessous depuis A (voisins dans l'ordre alphabétique).

ABCDEF
Un graphe non orienté de 6 sommets (A à F).
🔒 Correction réservée aux membres Créer un compte gratuit →

Vérifier

Avez-vous bien compris ?

Répondez au quiz : la correction s'affiche immédiatement.