TP : Parcours en largeur

File¶

On rappelle l'utilisation d'une file en Python, avec la classe deque :

In [1]:

from collections import deque

q = deque() # file vide
q.appendleft(4) # ajoute 4 au début
q.appendleft(7)
q.pop() # supprime et renvoie le dernier élément (4)
q.appendleft(-5)
q.pop() # supprime et renvoie le dernier élément (7)
from collections import deque

q = deque() # file vide
q.appendleft(4) # ajoute 4 au début
q.appendleft(7)
q.pop() # supprime et renvoie le dernier élément (4)
q.appendleft(-5)
q.pop() # supprime et renvoie le dernier élément (7)

Out[1]:

Exercice

Deviner ce que renvoie la dernière instruction du code suivant, puis vérifier.

q = deque()
q.appendleft(2)
q.appendleft(3)
q.pop()
q.appendleft(5)
q.appendleft(7)
q.pop()
q.pop()
q.appendleft(11)
q.pop()
q.appendleft(13)
q.pop()

Implémentation du parcours en largeur¶

Voici un graphe G_ex représenté par liste d'adjacence que vous pourrez utiliser dans ce TP pour tester vos fonctions (vous pouvez réexecuter cette case pour générer un nouveau graphe aléatoire) :

In [1]:

import networkx as nx

options = {"font_size": 20, "node_size": 700, "edgecolors": "black"}
G_ex = nx.fast_gnp_random_graph(10, 0.35)
nx.draw(G_ex, with_labels= True, node_color= "white", **options)
import networkx as nx

options = {"font_size": 20, "node_size": 700, "edgecolors": "black"}
G_ex = nx.fast_gnp_random_graph(10, 0.35)
nx.draw(G_ex, with_labels= True, node_color= "white", **options)

Exercice

Écrire une fonction bfs(G, s) affichant les sommets du graphe G lors d'un parcours en largeur depuis le sommet s. Vérifier sur le graphe G_ex précédent.
Indice : Essayer de compléter le code ci-dessous. Ne regarder le cours que si vous ne voyez pas du tout comment faire.

In [ ]:

from collections import deque

def bfs(G, s):
    # définir une file q contenant s
    # définir une liste visited contenant n False, où n est le nombre de sommets
    # tant que q est non vide
        # extraire le dernier élément de q dans une variable u
        # si u n'a pas été visité:
            # afficher u
            # mettre True dans visited[u]
            # pour chaque voisin v de u
                # ajouter v au début de q
from collections import deque

def bfs(G, s):
    # définir une file q contenant s
    # définir une liste visited contenant n False, où n est le nombre de sommets
    # tant que q est non vide
        # extraire le dernier élément de q dans une variable u
        # si u n'a pas été visité:
            # afficher u
            # mettre True dans visited[u]
            # pour chaque voisin v de u
                # ajouter v au début de q 

Calcul de distance¶

Exercice

Écrire une fonction distances(G, s) qui renvoie une liste dist telle que dist[v] soit la distance (en nombre d'arêtes) du sommet s au sommet v. Vérifier sur le graphe G_ex précédent.
Indice : Définir une liste dist avec que des -1 initialement. Stocker des couples (sommet, distance) dans la file q. À chaque fois qu'un couple (u, d) est retiré, mettre d dans dist[u] et ajouter (v, d + 1) à la file q, pour tout voisin v de u.

Plus court chemin dans une matrice 0 - 1¶

Exercice

Résoudre ce problème sur LeetCode (site de programmation).
Vous devez vous inscrire, sélectionner "Python3" comme langage et écrire le code puis vérifier directement sur ce site.
Il faut afficher (print(...)) le résultat, c'est-à-dire la distance entre la case en haut à gauche et la case en bas à droite.

Calcul de plus court chemin¶

Exercice

Écrire une fonction predecessors(G, s) qui effectue un BFS sur G en partant de s et qui renvoie une liste pred telle que pred[v] soit le sommet prédécesseur de v dans le parcours en largeur.

Exercice

En déduire une fonction shortest_path(G, s, t) qui renvoie une liste correspondant aux sommets d'un plus court chemin de s à t dans G.