C12 : Exercices

C12.E1 : Construire un chemin entre deux nœuds

On souhaite non seulement savoir s'il existe un chemin entre deux sommets d'un graphe, mais également connaitre ce chemin.

Pour cela, on va reprendre et adapter la fonction du "12.2 - III.1" et écrire une deuxième fonction sur le modèle du "12.2 - III.2.b".

• Dans la fonction du "12.2 - III.1", il s'agit de remplacer la liste des sommets déjà vus par un dictionnaire. Les clés seront les sommets déjà vus. La valeur d'une clé sera le sommet qui a permis d'atteindre la clé. Par ailleurs, la fonction recursive aura un paramètre de plus : le sommet de départ lors de l'appel de la fonction. Ce paramètre permettra de connaitre le sommet parent lorsqu'un sommet sera ajouté au dictionnaire. Lors du premier appel de la fonction, on donnera à ce paramètre la valeur None afin de distinguer le sommet de départ des autres.

• Il s'agit ensuite d'encapsuler la récursivité dans une autre fonction. Dans cette deuxième fonction, le dictionnaire construit par récusivité permettra de reconstruire un chemin en "remontant" les sommets de proche en proche du sommet d'arrivé au sommet de départ.
Dans le cas où il n'existe pas de chemin, la fonction doit renvoyer None.

• Remarque : L'algorithme proposé ici ne renvoie pas le chemin le plus court !

A faire : compléter les deux fonctions ci-dessous, ainsi que le programme principale qui permet de tester ces fonctions.

def parcours_rec_prof(g, sommet, sommet_parent, dico_sommets_déja_vus):
    """
    """
    pass

def chemin(g, s1, s2):
    """
    Paramètres
        g (Graphe) : graphe dans lequel on recherche un chemin
        s1 : sommet de départ, qui doit être présent dans g
        s2 : sommet d'arrivé, qui doit être présent dans g
    Valeur renvoyée :
        None si aucun chemin n'existe ou une liste (list) des sommets qui permettent d'aller de s1 à s2
    """
    pass

C12.E2 : Parcours en profondeur d'abord, sans récursivité

Proposer une fonction itérative (non récursive) parcours_it_profondeur(g, sommet, liste_sommets_visites), équivalente à la fonction def parcours_rec_profondeur(g, sommet, liste_sommets_visites) du 12.3. On pourra pour cela utiliser une pile.

C12.E3 : Chemin de longueur minimale

Dans cet exercice, on souhaite déterminer le plus court chemin entre deux sommets (sommet de départ et sommet d'arrivée) d'un graphe.

L'algorithme se découpe en deux parties.

• La première partie consiste à construire un dictionnaire dont les clés sont les sommets du graphe et les valeurs les parents de ces sommets. La construction de ce dictionnaire se fera avec un parcours en largeur d'abord, sur le modèle de la fonction parcours_it_larg(g,s0) du 12.2_IV en remplaçant le dictionnaire dico_dist par le dictionnaire dico_sommets. Le parcours en largeur permet d'être sûr que le chemin suivi pour atteindre chaque sommet du graphe depuis le sommet de départ est le plus court possible.

• La deuxième partie consiste à construire la liste des sommets pour aller du sommet de départ au sommet d'arrivée. Cela se fait à l'aide du dictionnaire précédent, en "remontant" les sommets de proche en proche du sommet d'arrivée jusqu'au sommet de départ.

A faire : compléter le code ci-dessous.

def chemin(g, s0, s1):
    """
    Paramètres
        g (Graphe) : graphe dans lequel on recherche un chemin
        s0 : sommet de départ, qui doit être présent dans g
        s1 : sommet d'arrivée, qui doit être présent dans g
    Valeur renvoyée
        None si aucun chemin n'existe ou une liste (list) des sommets qui permettent d'aller de s1 à s2
    """
    # ===== Construction du dictionnaire des sommets du graphe
    # à partir de s0 avec un parcours en largeur d'abord =====
    dico_sommets = {s0: None}
    # à compléter

    # ===== Création de la liste des sommets du chemin de s0 à s1 =====
    # à compléter