🚕Parcours

On rappelle d'abord comment parcourir un arbre (qui est un graphe connexe, et sans cycle)

Parcours d'arbre

On utilise print, mais cela pourrait être n'importe quelle action lors du parcours.

🐍 Script Python

class Arbre:
    def __init__(self, racine, enfants):
        self.racine = racine
        self.enfants = enfants


def parcours(arbre):
    """Parcours récursif d'un arbre, (parcours en profondeur).
    """
    print(arbre.racine)
    for enfant in arbre.enfants:
        parcours(enfant)


def parcours(arbre):
    """Parcours itératif d'un arbre en profondeur.
    On utilise une pile.
    """
    suite = Pile()
    suite.empile(arbre)
    while not suite.est_vide():
        noeud = suite.dépile()
        print(noeud.racine)
        for enfant in noeud.enfants:
            suite.empile(enfant)

def parcours(arbre):
    """Parcours itératif d'un arbre en largeur.
    On utilise une file, et un code similaire !!!
    """
    suite = File()
    suite.enfile(arbre)
    while not suite.est_vide():
        noeud = suite.défile()
        print(noeud.racine)
        for enfant in noeud.enfants:
            suite.enfile(enfant)

Exercice

Vérifier sur un arbre écrit à la main que les parcours proposés sont bons.

Parcours de graphe

Exercice

1. Quels problèmes avons-nous à appliquer ces parcours sur des graphes ?

   Réponse

   Le parcours peut entrer dans un cycle, et il ne parcourt que la composante connexe !

2. Comment éviter de rentrer dans un cycle ?

   Réponse

   On va stocker dans une structure de données, des booléens pour indiquer si un sommet a déjà (ou va bientôt) être visité. On pourra alors faire un test avant de l'enfiler ou de l'empiler.

🐍 Script Python

# Exemple de graphe d'ordre n, où
# les sommets sont numérotés de 0 inclus à n exclu. 

def parcours(sommet_départ):
    """Parcours itératif d'un graphe,
    parcours en profondeur, en partant de 'sommet',
    uniquement de sa composante connexe.
    """
    visité = [False for _ in range(n)]
    suite = Pile()
    suite.empile(sommet_départ)
    visité[sommet_départ] = True
    while not suite.est_vide():
        sommet = suite.dépile()
        print(sommet) # ou autre action
        for enfant in sommet.enfants:
            if visité[enfant] == False:
                visité[enfant] = True
                suite.empile(enfant)

Exercice

1. Obtenir le parcours en largeur d'un graphe.
2. Obtenir la distance du sommet le plus éloigné de sommet_départ.
3. Obtenir la distance la plus courte entre sommet_départ et sommet_destination.

Éléments de réponses

France-IOI

Il faut atteindre le niveau 4 pour trouver beaucoup d'exercices sur les graphes.

C'est le début de la grande aventure !!!