Introduction
Les graphes sont des structures de données fondamentales en informatique, utilisées pour modéliser des relations complexes entre objets. Un graphe est composé d’un ensemble de sommets (ou nœuds) et d’un ensemble de relations entre ces sommets. Ces relations sont appelées arêtes dans un graphe non orienté, et arcs dans un graphe orienté.
Un graphe non orienté relie deux sommets sans notion de direction : une arête {A, B} signifie que A est lié à B et réciproquement. Un graphe orienté, en revanche, associe une direction à chaque relation : un arc (A → B) indique une liaison allant de A vers B uniquement.
Les graphes peuvent être pondérés si une valeur (ou poids) est associée à chaque arête ou arc, ce qui permet de modéliser des distances, des coûts ou des durées. Ils sont omniprésents dans des domaines tels que les réseaux sociaux, les systèmes de recommandation ou les réseaux de transport.
Pour représenter un graphe en programmation, on utilise couramment la liste d’adjacence, qui associe à chaque sommet la liste de ses voisins. Exemple :
Une autre représentation possible est la matrice d’adjacence, mais elle est moins efficace en mémoire pour les grands graphes peu denses.
Dans cette leçon, nous allons explorer trois aspects essentiels des algorithmes sur les graphes : le parcours de graphe (en largeur ou en profondeur), la détection de cycles, et la recherche de chemin le plus court.
Parcours de graphe
Parcours en largeur
Le parcours en largeur (ou BFS pour Breadth-First Search) est une méthode systématique pour explorer un graphe en visitant tous les sommets à une distance donnée avant de passer à ceux plus éloignés. Cette approche est particulièrement utile pour trouver le chemin le plus court dans un graphe non pondéré.
Considérons un graphe non orienté représentant un réseau de transport urbain, où chaque sommet est une station et chaque arête une connexion directe entre stations. Pour déterminer le chemin le plus court entre deux stations, le parcours en largeur est adapté.
Voici un exemple de code Python illustrant un parcours en largeur avec une liste d’adjacence :
Parcours en profondeur
Le parcours en profondeur (ou DFS pour Depth-First Search) explore aussi loin que possible le long de chaque branche avant de revenir en arrière. Cette méthode est utile pour détecter des cycles ou explorer toutes les possibilités dans un graphe.
Prenons un graphe orienté représentant un réseau de dépendances entre tâches. Le parcours en profondeur permet de vérifier s’il existe des cycles, ce qui indiquerait des dépendances circulaires problématiques.
Voici un exemple de code Python pour un parcours en profondeur :
Détection de cycles
La détection de cycles dans un graphe est cruciale pour de nombreuses applications, notamment en planification de tâches, où un cycle indiquerait une impasse.
Dans un graphe non orienté, un cycle est détecté si, lors d’un parcours, on rencontre un sommet déjà visité qui n’est pas le parent direct.
Dans un graphe orienté, la présence d’un cycle peut être déterminée en maintenant un ensemble temporaire de sommets en cours d’exploration. Cet ensemble simule la pile d’appels récursifs : si on revisite un sommet déjà présent dans cet ensemble, un cycle est détecté.
Voici un exemple en Python pour un graphe orienté :
Recherche de chemin le plus court
La recherche de chemin le plus court dans un graphe consiste à déterminer une suite de sommets connectés par des arêtes, allant d’un sommet de départ à un sommet d’arrivée, tout en minimisant un critère (distance, nombre d’étapes, coût…).
Dans un graphe pondéré, on utilise classiquement l’algorithme de Dijkstra pour trouver le chemin le plus court en tenant compte des poids. Cet algorithme n’est pas détaillé ici.
Dans un graphe non pondéré, le parcours en largeur permet de trouver un chemin minimal en nombre d’arêtes. Il faut veiller à ne pas revisiter les sommets déjà explorés pour éviter les redondances ou boucles.
Voici un exemple de recherche de chemin le plus court avec gestion explicite des sommets visités dès l’enfilage :
Conclusion
Les algorithmes sur les graphes sont des outils puissants pour résoudre une grande variété de problèmes informatiques. Le parcours en largeur ou en profondeur permet d’explorer les graphes de façon efficace, la détection de cycles garantit la cohérence des structures de dépendance, et la recherche de chemin le plus court permet de naviguer dans des réseaux complexes. La compréhension de ces techniques est essentielle pour modéliser, analyser et résoudre des problèmes reposant sur des relations entre objets.