Graphes : parcours en largeur, en profondeur et Dijkstra

Informatique de gestion · Bachelor 3

Représenter un graphe, le parcourir (BFS, DFS) et calculer un plus court chemin pondéré.

Introduction

Un graphe modélise des objets (sommets) et leurs relations (arêtes) : réseau routier, organigramme, dépendances entre tâches, flux logistiques, réseaux sociaux. Il peut être orienté ou non, pondéré ou non. On le représente en mémoire par une matrice d'adjacence, rapide pour tester l'existence d'une arête mais coûteuse en espace, ou par des listes d'adjacence, plus économes pour les graphes peu denses.

Le parcours en largeur (BFS) utilise une file et explore les sommets par distance croissante en nombre d'arêtes ; il donne donc les plus courts chemins dans un graphe non pondéré. Le parcours en profondeur (DFS) utilise une pile ou la récursivité et sert à détecter les cycles, trier topologiquement ou trouver les composantes connexes.

Pour un graphe pondéré à poids positifs, l'algorithme de Dijkstra calcule les plus courts chemins depuis une source en choisissant à chaque étape le sommet non traité de plus petite distance, typiquement avec une file de priorité. Il sert à planifier des tournées, des itinéraires ou des routages de réseaux.

Objectifs d'apprentissage

Choisir entre matrice et listes d'adjacence selon la densité du graphe
Dérouler un parcours BFS et un parcours DFS sur un exemple
Associer chaque parcours à ses applications (plus court chemin, cycles, tri topologique)
Appliquer l'algorithme de Dijkstra et en donner la complexité
Expliquer pourquoi Dijkstra exige des poids non négatifs

Concepts clés

Représentations: Matrice d'adjacence : O(V²) en espace, test d'arête en O(1) ; listes d'adjacence : O(V+E), adaptées aux graphes peu denses.
BFS: Parcours par niveaux avec une file ; trouve le plus court chemin en nombre d'arêtes dans un graphe non pondéré, en O(V+E).
DFS: Parcours qui va le plus loin possible avant de revenir en arrière ; détecte les cycles, calcule un tri topologique d'un graphe orienté acyclique.
Dijkstra: Pour des poids positifs, fixe progressivement la distance minimale de chaque sommet ; avec file de priorité, coût en O((V+E) log V).

Conclusion

Les graphes unifient des problèmes très variés : itinéraires, dépendances, réseaux. Savoir choisir la représentation et l'algorithme de parcours adaptés est une compétence de base de l'algorithmique appliquée.

En gestion, ces notions interviennent dans la planification de projets, la logistique et l'analyse de réseaux relationnels.

Cartes

Qu'est-ce qu'un graphe ?: Un ensemble de sommets reliés par des arêtes, orientées ou non, éventuellement pondérées.
Quand préférer les listes d'adjacence ?: Pour les graphes peu denses : espace en O(V+E) au lieu de O(V²).
Quelle structure de données utilise le BFS ?: Une file : on explore d'abord tous les voisins avant d'aller plus loin.
Quelle structure utilise le DFS ?: Une pile, explicite ou via la récursivité.
Que garantit le BFS dans un graphe non pondéré ?: Le plus court chemin en nombre d'arêtes depuis la source.
À quoi sert un tri topologique ?: Ordonner les sommets d'un graphe orienté acyclique pour que chaque dépendance précède ce qui en dépend (ordre des tâches d'un projet).
Quelle est la complexité d'un BFS ou d'un DFS ?: O(V+E) avec des listes d'adjacence.
Quel est le principe de Dijkstra ?: Fixer à chaque étape le sommet non traité de plus petite distance connue, puis relâcher les distances de ses voisins.
Pourquoi Dijkstra échoue-t-il avec des poids négatifs ?: Un chemin plus long peut devenir plus court via une arête négative, ce qui invalide l'hypothèse qu'une distance fixée est définitive.
Quel algorithme utiliser avec des poids négatifs ?: Bellman-Ford, qui tolère les poids négatifs et détecte les cycles de poids négatif.

Glossaire

Sommet: Point du graphe représentant un objet.
Arête: Lien entre deux sommets, orienté (arc) ou non.
Degré: Nombre d'arêtes incidentes à un sommet.
Composante connexe: Ensemble de sommets mutuellement atteignables.
Graphe orienté acyclique (DAG): Graphe orienté sans cycle, qui admet un tri topologique.
File de priorité: Structure qui fournit toujours l'élément de plus petite clé.