Parcours

Le parcours d'un graphe consiste, comme les arbres, à parcourir l'ensemble des sommets d'un graphe. On doit simplement préciser un sommet de départ.

Parcours en largeur

Il s'agit du même parcours que pour celui des arbres, fonctionnant avec une file stockant les voisins des sommets traités.

Ce parcours n'est pas unique, sauf si on précise l'ordre de sélection des sommets adjacents.

Exemple

En partant de 6 :

• 6 - 4 - 2 - 1 - 5 - 3
• 6 - 1 - 2 - 4 - 3 - 5
• ...

Parcours en profondeur

Ce parcours consiste à aller le plus loin possible avant de revenir aux sommets précédents.

Ce parcours n'est pas unique, sauf si on précise l'ordre de sélection des sommets adjacents.

Exemple

En partant de 6 :

• 6 - 1 - 2 - 3 - 4 - 5
• 6 - 4 - 5 - 3 - 2 - 1
• ...

Exercice

Rédigez deux fonctions (ou méthodes si vous utilisez des classes) pour réaliser les deux parcours sur les graphes rédigés en liste d'adjacence.

Vos fonctions (ou méthodes) prendront en paramètre le sommet de départ, et une fonction qui prendra en paramètre le graphe et le sommet traité afin d'y réaliser une action.

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

def affiche_sommet(graphe, sommet):
    print(sommet)

Un indice ?

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

def fonction1(x, salut):
    y = x*2
    salut(y)

def fonction2(n):
    for i in range(n):
        print("Coucou")

fonction1(3, fonction2)