Parcours

Question

Ajoutez à votre class, Graphe, une méthode visiter_sommet, telle que :

  • Entrées :

    • sommet - le sommet à visiter

    • coupe - une structure équipée de pop et push, qui représente la coupe actuelle

    • marque - une liste qui contient les sommets déjà visité

    • fn - une fonction qui prend en paramètre un sommet et réalise une action

  • Sortie : Aucune

  • Effet : Visite le sommet, ie, ajoute ses voisins, au besoin, dans la coupe, exécute fn sur le sommet et marque le sommet comme visité.

Indice

Par exemple, la fonction ci-dessous affiche le sommet traité :

1
def affiche_sommet(sommet):
2
    print(sommet)

Indice

Pour passer une fonction en paramètre d'une autre fonction, faites comme suit :

1
def fonction1(salut):
2
    salut()
3
4
def fonction2():
5
    print("Coucou")
6
7
fonction1(fonction2)
Question
Ajoutez à votre classe, Graphe, une fonction parcours_profondeur, telle que :
  • Entrées :
    • sommet - un sommet, de type quelconque, la source de notre parcours
    • fn - une fonction qui prend un paramètre un sommet et réalise une action
  • Sortie : Aucune
  • Effet : Parcours le graphe en profondeur depuis sommet et exécute fn sur tout les sommets rencontrés.
Indice
Elle utilisera avantageusement la méthode visiter_sommet.
Question
Ajoutez à votre classe, Graphe, une fonction parcours_largeur, telle que :
  • Entrées :
    • sommet - un sommet, de type quelconque, la source de notre parcours
    • fn - une fonction qui prend un paramètre un sommet et réalise une action
  • Sortie : Aucune
  • Effet : Parcours le graphe en largeur depuis sommet et exécute fn sur tout les sommets rencontrés.
Indice
Elle utilisera avantageusement la méthode visiter_sommet.
Graphes et labyrinthe
Réaliser l'activité Capytale numéro 75b3-3126659 qui vous apprendra à générer un labyrinthe grâce au parcours en profondeur !