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).
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 ordreIl 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 vusIl 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
pred rempli lors du parcours ; on remonte de la sortie à l'entrée grâce à pred.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.
Degrés
★☆☆Donner le degré de chaque sommet du graphe ci-dessous.
Somme des degrés
★★☆Calculer la somme des degrés des sommets du graphe ci-dessous. Lien avec le nombre d'arêtes ?
Chemin
★☆☆Donner un chemin de A à F dans le graphe ci-dessous.
Cycle
★☆☆Donner un cycle du graphe ci-dessous.
Matrice d'adjacence
★★☆Écrire la ligne de la matrice d'adjacence du sommet B du graphe ci-dessous (sommets dans l'ordre A à F).
Matrice symétrique
★★☆Pourquoi la matrice d'un graphe non orienté est-elle symétrique ?
Dictionnaire
★☆☆Écrire en Python (dictionnaire) la liste d'adjacence des sommets A et E du graphe ci-dessous.
Parcours en largeur
★★☆Donner l'ordre de visite du parcours en largeur du graphe ci-dessous depuis A (voisins dans l'ordre alphabétique).
Parcours en profondeur
★★☆Donner l'ordre du parcours en profondeur (récursif) du graphe ci-dessous depuis A (voisins dans l'ordre alphabétique).
Distance
★★☆Dans le graphe ci-dessous, quelle est la distance (en nombre d'arêtes) de A à F ?
Graphe orienté
★★☆Donner un exemple concret de graphe orienté.
Graphe pondéré
★☆☆Que représentent les poids d'un graphe routier ?
Nombre d'arêtes maximal
★★★Combien d'arêtes au plus dans un graphe non orienté simple de $n$ sommets ?
Taille mémoire
★★☆Un réseau social a $10^6$ utilisateurs et en moyenne $200$ amis par personne. Matrice ou liste d'adjacence ?
Visités
★★☆Pourquoi utiliser un ensemble vus dans les parcours ?
Connexité
★★☆Comment savoir si un graphe est connexe avec un parcours ?
Reconstituer un chemin
★★★Avec un dictionnaire pred rempli par le BFS, écrire la reconstitution du chemin de depart à arrivee.
Détecter un cycle
★★★Lors d'un DFS dans un graphe non orienté, à quel moment détecte-t-on un cycle ?
Applications
★☆☆Citer trois domaines où l'on utilise des graphes.
Vrai ou faux
★★☆a) Le BFS utilise une pile. b) La somme des degrés est le double du nombre d'arêtes. c) Un arbre est un graphe connexe sans cycle.
Vérifier
Avez-vous bien compris ?
Répondez au quiz : la correction s'affiche immédiatement.