Avertissement
Cette page reste ici pour des raisons historiques et elle peut contenir des informations périmées ou incorrectes.
Notes de modification : 2/22/98, 3/2/98, 12/4/00 : Cette version de cet essai corrige plusieurs bogues dans le code. 6/10/19 : Retrait defind_shortest_pathcomme « presque optimal ». 8/11/19 : Correction de l’utilisation accidentelle defind_graph()au lieu defind_path()
Copyright (c) 1998, 2000, 2003, 2019 Python Software Foundation.All rights reserved.Licensed under the PSF license.
Les graphes sont des réseaux composés de nœuds reliés par des arêtes ou des arcs. Dans les graphes orientés, les connexions entre les nœuds ont une direction et sont appelées arcs ; dans les graphes non orientés, les connexions n’ont pas de direction et sont appelées arêtes. Nous discutons principalement des graphes dirigés. Les algorithmes dans les graphes comprennent la recherche d’un chemin entre deux nœuds, la recherche du chemin le plus court entre deux nœuds, la détermination des cycles dans le graphe (un cycle est un chemin non vide d’un nœud à lui-même), la recherche d’un chemin qui atteint tous les nœuds (le fameux « problème du voyageur de commerce »), etc. Parfois, les nœuds ou les arcs d’un graphe ont des poids ou des coûts qui leur sont associés, et nous sommes intéressés à trouver le chemin le moins cher.
Il existe une littérature considérable sur les algorithmes de graphes, qui sont une partie importante des mathématiques discrètes. Les graphes ont également beaucoup d’utilisation pratique dans les algorithmes informatiques. Des exemples évidents peuvent être trouvés dans la gestion des réseaux, mais les exemples abondent dans de nombreux autres domaines. Par exemple, les relations appelant-calculé dans un programme informatique peuvent être vues comme un graphe (où les cycles indiquent la récursion, et les nœuds inaccessibles représentent le code mort).
Peu de langages de programmation fournissent un support direct pour les graphes en tant que type de données,et Python ne fait pas exception. Cependant, les graphes sont facilement construits à partir de listeset de dictionnaires. Par exemple, voici un graphe simple (je ne peux pas utiliser de dessins dans ces colonnes, donc j’écris les arcs du graphe):
A -> B A -> C B -> C B -> D C -> D D -> C E -> F F -> C
Ce graphe a six nœuds (A-F) et huit arcs. Il peut être représenté par la structure de données Python suivante :
graph = {'A': , 'B': , 'C': , 'D': , 'E': , 'F': }
C’est un dictionnaire dont les clés sont les nœuds du graphe. Pour chaque clé,la valeur correspondante est une liste contenant les nœuds qui sont reliés par un arc direct depuis ce nœud. C’est à peu près aussi simple que possible (encore plus simple, les nœuds pourraient être représentés par des nombres au lieu de noms, mais les noms sont plus pratiques et peuvent facilement être faits pour porter plus d’informations, comme les noms de ville).
Ecrivons une fonction simple pour déterminer un chemin entre deux nœuds. Elle prend un graphe et les nœuds de début et de fin comme arguments. Elle retournera une liste de nœuds (y compris les nœuds de début et de fin) comprenant le chemin.Lorsqu’aucun chemin ne peut être trouvé, elle retourne None. Le même noeud n’apparaîtra pas plus d’une fois sur le chemin retourné (c’est-à-dire qu’il ne contiendra pas de cycles). L’algorithme utilise une technique importante appelée backtracking : il essaie chaque possibilité à son tour jusqu’à ce qu’il trouve une solution.
def find_path(graph, start, end, path=): path = path + if start == end: return path if not graph.has_key(start): return None for node in graph: if node not in path: newpath = find_path(graph, node, end, path) if newpath: return newpath return None
Un exemple d’exécution (en utilisant le graphe ci-dessus):
>>> find_path(graph, 'A', 'D') >>>
La deuxième instruction ‘if’ est nécessaire uniquement dans le cas où il y a des nœuds qui sont répertoriés comme points d’extrémité pour les arcs mais qui n’ont pas d’arc sortant eux-mêmes, et ne sont pas répertoriés dans le graphe du tout. De tels nœuds pourraient également être contenus dans le graphe, avec une liste vide d’arcs sortants, mais parfois il est plus pratique de ne pas l’exiger.
Notez que si l’utilisateur appelle find_path() avec trois arguments,il s’appelle lui-même avec un quatrième argument : le chemin qui a déjà été traversé.La valeur par défaut de cet argument est la liste vide, », ce qui signifie qu’aucun nœud n’a encore été traversé. Cet argument est utilisé pour éviter les cycles (le premier ‘if’ dans la boucle ‘for’). L’argument ‘path’ n’est pas modifié : l’affectation « path = path + » crée une nouvelle liste. Si nous avions écrit « path.append(start) » à la place, nous aurions modifié la variable ‘path’ dans l’appelant, avec des résultats désastreux. (En utilisant des tuples, nous aurions pu être sûrs que cela ne se produirait pas, au prix de devoir écrire « path = path + (start,) » puisque « (start) » n’est pas un tuple singleton — c’est juste une expression entre parenthèses.)
Il est simple de modifier cette fonction pour qu’elle renvoie une liste de tous les chemins (sans cycles) au lieu du premier chemin qu’elle trouve:
def find_all_paths(graph, start, end, path=): path = path + if start == end: return if not graph.has_key(start): return paths = for node in graph: if node not in path: newpaths = find_all_paths(graph, node, end, path) for newpath in newpaths: paths.append(newpath) return paths
Un exemple d’exécution:
>>> find_all_paths(graph, 'A', 'D') , , ] >>>
Une autre variante trouve le chemin le plus court:
def find_shortest_path(graph, start, end, path=): path = path + if start == end: return path if not graph.has_key(start): return None shortest = None for node in graph: if node not in path: newpath = find_shortest_path(graph, node, end, path) if newpath: if not shortest or len(newpath) < len(shortest): shortest = newpath return shortest
Un exemple d’exécution:
>>> find_shortest_path(graph, 'A', 'D') >>>
Ces fonctions sont à peu près aussi simples qu’elles le sont. Pourtant, elles sont presque optimales (pour le code écrit en Python). Dans une autre colonne de Python Patterns, j’essaierai d’analyser leur vitesse d’exécution et d’améliorer leurs performances, au prix de plus de code.
MISE À JOUR : Eryk Kopczyński a fait remarquer que ces fonctions ne sont pas optimales. Au contraire, « ce programme s’exécute en temps exponentiel,alors que find_shortest_path peut être fait en temps linéaire en utilisant BFS . De plus, un BFS linéaire est plus simple : »
# Code by Eryk Kopczyński def find_shortest_path(graph, start, end): dist = {start: } q = deque(start) while len(q): at = q.popleft() for next in graph: if next not in dist: dist = , next] q.append(next) return dist.get(end)
Notez que cela renvoie le chemin dans un format bizarre, par exemple,, 'B'], 'D']. En particulier,len(find_shortest_path(graph, 'A', 'D'))donnera la réponse incorrecte (2, car la liste extérieure est de longueur 2). Ceci est dû au fait que l’ajout est effectué sous la forme, next]au lieu dedist+. La seconde méthode utiliserait un temps quadratique et de la mémoire, mais devrait quand même convenir pour des graphes relativement petits;sinon, il est facile de transformer la liste dans le format correct.
Une autre variation serait d’ajouter plus d’abstraction de données : créer une classe pour représenter les graphes, dont les méthodes implémentent les différents algorithmes. Bien que cela réponde au désir de programmation structurée, cela ne rend pas le code plus efficace (au contraire). En revanche, il est plus facile d’ajouter différentes étiquettes aux nœuds ou aux arcs et d’ajouter des algorithmes qui tiennent compte de ces étiquettes (par exemple, pour trouver le chemin le plus court entre deux villes sur une carte). Cela aussi fera l’objet d’une autre chronique.