Graphes : représentations et parcours : fiche de révision

1Vocabulaire et représentations

Un graphe est un ensemble de sommets reliés par des arêtes (graphe non orienté) ou des arcs (graphe orienté). Deux sommets reliés sont adjacents ; le degré d'un sommet est son nombre de voisins. Un chemin est une suite de sommets consécutivement reliés ; un cycle est un chemin qui revient à son sommet de départ. Un graphe est connexe si tout couple de sommets est relié par un chemin. Les graphes modélisent les réseaux routiers, sociaux, informatiques, les dépendances entre tâches.

Deux représentations au programme. La matrice d'adjacence : un tableau n × n où M[i][j] vaut 1 (ou le poids) s'il existe une arête de i vers j, 0 sinon ; symétrique pour un graphe non orienté. Test d'adjacence en O(1), mais mémoire en O(n²) et énumération des voisins en O(n). La liste d'adjacence : un dictionnaire qui associe à chaque sommet la liste de ses voisins. Mémoire en O(n + m) avec m le nombre d'arêtes, énumération des voisins immédiate — c'est la représentation privilégiée pour les graphes peu denses.

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

2Parcours en largeur (BFS) et en profondeur (DFS)

Le parcours en largeur explore les sommets par distance croissante depuis le départ : on utilise une file et un ensemble des sommets déjà vus (pour ne pas boucler sur les cycles).

def parcours_largeur(g, depart):

vus = {depart} ; file = [depart] ; ordre = []

while file:

s = file.pop(0) ; ordre.append(s)

for v in g[s]:

if v not in vus: vus.add(v) ; file.append(v)

return ordre

Le parcours en profondeur suit un chemin le plus loin possible avant de revenir en arrière. Version récursive : on marque le sommet, puis on se rappelle sur chaque voisin non vu ; version itérative : même algorithme que le BFS avec une pile à la place de la file.

def parcours_profondeur(g, s, vus=None):

if vus is None: vus = set()

vus.add(s)

for v in g[s]:

if v not in vus: parcours_profondeur(g, v, vus)

return vus

Les deux parcours visitent chaque sommet et chaque arête une fois : complexité O(n + m) avec des listes d'adjacence. Le BFS trouve le plus court chemin en nombre d'arêtes (graphe non pondéré) ; le DFS sert à détecter les cycles, à tester la connexité et à explorer un labyrinthe.

3Applications : chemin, cycle, connexité

Recherche d'un chemin entre deux sommets : un parcours (BFS ou DFS) depuis le départ ; l'arrivée est atteignable si et seulement si elle figure dans les sommets visités. Pour reconstituer le chemin, on mémorise pour chaque sommet son prédécesseur au moment de sa découverte, puis on remonte depuis l'arrivée.

Détection de cycle dans un graphe non orienté : lors d'un DFS, si l'on rencontre un voisin déjà vu qui n'est pas le sommet d'où l'on vient, il y a un cycle. Dans un graphe orienté, on distingue les sommets en cours de visite (sur la pile d'appels) : retomber sur l'un d'eux révèle un cycle.

Composantes connexes : on lance un parcours depuis un sommet non vu, on obtient une composante ; on répète tant qu'il reste des sommets non vus. Le nombre de lancements est le nombre de composantes.

Le programme ne demande pas les algorithmes de plus court chemin pondéré (Dijkstra) ni les arbres couvrants, mais des sujets peuvent les présenter avec le code fourni à analyser.

4Exercice type et pièges

Énoncé type : « À partir de la matrice d'adjacence donnée, dessiner le graphe, donner le degré de chaque sommet, puis l'ordre de visite d'un parcours en largeur depuis A en supposant les voisins traités dans l'ordre alphabétique. » Méthode : lire ligne par ligne (les 1 de la ligne i sont les voisins de i), compter les 1 par ligne pour le degré, dérouler le BFS en tenant à jour la file et l'ensemble des vus sur le brouillon.

Pièges : oublier l'ensemble des sommets vus (boucle infinie sur un cycle) ; confondre file et pile (BFS et DFS donnent des ordres différents) ; croire que le DFS trouve le plus court chemin ; dans une matrice d'un graphe orienté, lire la colonne au lieu de la ligne ; oublier que pop(0) est en O(n) — à l'écrit on le signale, à l'épreuve pratique on utilise deque.