Problème — Exhiber un cycle

Problème — Exhiber un cycle.

La fonction a_un_cycle_non_oriente du cours indique si un graphe non orienté contient un cycle, mais ne dit pas lequel. On veut écrire une fonction trouver_cycle(G) qui renvoie la liste des sommets d'un cycle, ou None s'il n'y en a pas.

• Lors du parcours en profondeur, on mémorise dans un dictionnaire parent le sommet depuis lequel chaque sommet a été découvert. Quand on rencontre, depuis $u$, un voisin $v$ déjà visité et différent du parent de $u$, expliquer comment retrouver le cycle.
• Écrire la fonction et la tester sur G = \{0: [1], 1: [0, 2, 4], 2: [1, 3], 3: [2, 4], 4: [3, 1, 5], 5: [4]\}.