######################################################################## ## Voici un cours programme en python pour illustrer l'exercice sur le ## parcours en profondeur recursif vu en TD. Vous aurez besoin de ## la version 3 de python a cause du mot cle "nonlocal" ## usage : python3 pprecursif.py ## pour toute question ou commentaire sur le code n'hesitez pas a me ## joindre par mail : ## guillaume [point] guegan [chez] l i r m m [point] fr ######################################################################## # on utilise un dictionnaire de listes pour representer un graphe # ici le graphe de petersen petersen = { 1 : [ 2, 3, 4 ], 2 : [ 1, 5, 9 ], 3 : [ 1, 7, 8 ], 4 : [ 1, 6, 0 ], 5 : [ 2, 6, 8 ], 6 : [ 4, 5, 7 ], 7 : [ 3, 6, 9 ], 8 : [ 3, 5, 0 ], 9 : [ 2, 7, 0 ], 0 : [ 4, 8, 9 ], } # petersen moins l'arete 12 petersen2 = { 1 : [ 3, 4 ], 2 : [ 5, 9 ], 3 : [ 1, 7, 8 ], 4 : [ 1, 6, 0 ], 5 : [ 2, 6, 8 ], 6 : [ 4, 5, 7 ], 7 : [ 3, 6, 9 ], 8 : [ 3, 5, 0 ], 9 : [ 2, 7, 0 ], 0 : [ 4, 8, 9 ], } # un graphe non connexe nconnexe = { 0 : [ 1, 2 ], 1 : [ 0, 2 ], 2 : [ 0, 1 ], 3 : [ 4 ], 4 : [ 3 ] } ## notre beau parcours recursif def parcoursProfondeur(v, G): # les initialisations n = len(G); t = 1 # n nbr de sommets de G, t sert a remplir ordre ordre = n * [-1]; pere = list( range(n) ) # les 2 tbls que l'on retourne dejaVu = n * [ False ] # dejaVu[x]=Vrai ssi on a deja visite le sommet x # definition d'une fonction locale def pp(x, G): nonlocal t # nonlocal n'existe qu'en python _3_ dejaVu[x] = True ordre[x] = t t += 1 for y in G[x]: # pour tous les voisins du sommet x if not dejaVu[y]: pere[y] = x pp(y, G) # appel de la fonction locale et retour des resultats pp(v, G) return (ordre, pere) ## le code execute par l'appel du programme print( str( parcoursProfondeur(8, petersen2) ) ) print( str( parcoursProfondeur(0, nconnexe) ) ) ## note 1 : python c'est cool ## note 2 : pourquoi je dois utiliser "nonlocal" pour t et pas pour les ## listes ordre, pere et dejavu : # http://stackoverflow.com/questions/11164149/python-closure-global-strangeness # http://stackoverflow.com/questions/12182068/python-closure-function-losing-outer-variable-access # http://stackoverflow.com/questions/4851463/python-closure-write-to-variable-in-parent-scope # etc...