# Par exemple pour Fool et Sage vous devez renvoyez le résultat suivant : # # FOOL # POOL # POLL # POLE # PALE # SALE # SAGE # # SOLUTION: graph = {'A': ['B', 'C'], 'B': ['C', 'D'], 'C': ['D'], 'D': ['C'], 'E': ['F'], 'F': ['C'] } class Graphe(dict): def __init__(self, liens, noeuds): for v in liens: self[v] = set() for e in noeuds: self.ajout_noeud(e) def ajout_lien(self, lien): self[lien[0]].add(lien[1]) self[lien[1]].add(lien[0]) def ajout_noeud(self, noeud): self[noeud] = set() def simGraphe(mots): d = {} g = Graphe(mots, []) for mot in mots: for i in range(len(mot)): groupe = mot[:i] + '_' + mot[i+1:] if groupe in d: d[groupe].append(mot) else: d[groupe] = [mot] for groupe in d.keys(): for mot1 in d[groupe]: for mot2 in d[groupe]: if mot1 != mot2: g.ajout_lien([mot1, mot2]) return g def chemin(graphe, source, destination, visite=None): if source == destination: return [destination] else: visite = visite or set() for s in graphe[source]: if s not in visite: visite.add(s) print("trace:", source + " > " + s) sous_chemin = chemin(graphe, s, destination, visite) if sous_chemin is not None: return [source] + sous_chemin print(chemin(simGraphe(["AA", "AB", "BC", "AC", "DD"]), "AA", "BC")) # ['AA', 'AB', 'AC', 'BC']