Recherche de cycle dans un graphe

Question

Implémentez une méthode, dans Graphe, contient_cycle_non_oriente, telle que :

  • Entrée : aucune

  • Sortie : Un booléen qui vaut True s'il y a un cycle dans le graphe considéré comme non-orienté, False sinon

Indice

On pourra choisir un parcours en largeur ou en profondeur.

Indice

Il faudra penser au cas où le graphe n'est pas connexe.

Question

Implémentez une méthode, dans Graphe, contient_cycle, telle que :

  • Entrée : aucune

  • Sortie : Un booléen qui vaut True s'il y a un cycle dans le graphe, False sinon

Question

Pour ceux qui ont finit en avance.

Implémentez une méthode, dans Graphe, cycle, telle que :

  • Entrée :

    • sommet : un sommet quelconque

  • Sortie : Si sommet fait parti d'un cycle, une liste de sommet représentant ce cycle, None sinon