Parcours en largeur et calcul de distances

Contenu

Parcours en largeur et calcul de distances#

Dans cette feuille, nous raffinons l’algorithme de parcours de graphe vu précédemment pour calculer des distances simples entre sommets d’un graphe, ne tenant pas compte des poids des arêtes. Nous suivons la même démarche que pour notre premier algorithme: invariants, test sur des exemples, visualisation, complexité, preuve de correction.

Définition : distance simple dans un graphe

La distance entre deux sommets \(u\) et \(v\) d’un graphe \(G\) est le plus petit entier \(l\) tel qu’il existe un chemin avec \(l\) arêtes allant de \(u\) à \(v\). S’il n’y a pas de tel chemin, alors la distance est \(\infty\).

Exercice :

  1. Complétez la fonction suivante qui implante un parcours en largeur, en vous laissant guider par les invariants fournis:

from graph import Graph, Node
from typing import Dict

def parcours_en_largeur(G: Graph, u: Node) -> Dict[Node, int]:
    """
    INPUT:
    - 'G' - un graphe
    - 'u' - un sommet du graphe
    
    OUTPUT: un dictionnaire associant à chaque sommet `v` accessible depuis `u` sa distance depuis `u`
    """
    distances = {u: 0} # L'ensemble des sommets déjà rencontrés
    todo      = [u]    # Une liste de sommets à traiter
    
    while todo:
        # Invariants:
        # - Si `v` est dans `distance`, alors il y a un chemin de `u` à `v`,
        #   et distance[v] contient la distance de `u` à `v`;
        # - Si `v` est dans `distance` et pas dans `todo`
        #   alors tous les voisins de `v` sont dans `distance`
        # VOTRE CODE ICI
        raise NotImplementedError()
    return distances

  1. Testez que votre fonction est correcte sur les exemples suivants. Si elle ne l’est pas, utilisez la question suivante pour déboguer!

from graph import Graph, examples

C3 = examples.C3()
C3.edges()

assert parcours_en_largeur(C3, 0) == {0: 0, 1: 1, 2: 2}

T3 = examples.T3()
T3.edges()

assert parcours_en_largeur(T3, 0) == {0: 0, 1: 1, 2: 1}

from graph import examples
G = examples.parcours_directed()

assert parcours_en_largeur(G, "H") == {'H': 0, 'F': 1, 'G': 2}

assert parcours_en_largeur(G, "A") == {'A': 0, 'B': 1, 'G': 1, 'F': 1, 'C': 2, 'H': 2, 'D': 3}

  1. Instrumentez votre code comme dans la feuille précédente pour visualiser son exécution

Exercice : Complexité

Donnez une borne de complexité pour votre implantation de l’algorithme parcours_en_largeur. Comme précédemment, vous donnerez le modèle de complexité, le coût de vos opérations, et vous argumenterez.

Pour aller plus loin

Pour simplifier, nous avons utilisé une liste pour todo. Pour avoir une bonne complexité, il faudrait utiliser une file (FIFO), typiquement implantée au moyen d’une liste chaînée et non un tableau comme dans les listes Python. Voir par exemple queue.SimpleQueue.

VOTRE RÉPONSE ICI

Exercice : pour aller plus loin

Chronométrez votre code sur des graphes de taille croissante afin de tracer une courbe de complexité pratique et vérifier empiriquement que votre code a la complexité voulue.

Indication

Vous pouvez par exemple utiliser les outils time.time, %timit, timeit ou bleachermark (note : ce dernier n’est pas encore compatible Python 3).

Exercice : Preuve de correction

VOTRE RÉPONSE ICI

Conclusion#

Dans cette feuille, vous avez mené en toute autonomie l’implantation et l’étude d’un autre parcours de graphe pour mettre en pratique tout ce que nous avions vu dans la fiche précédente. Bravo!

Vous pouvez maintenant aborder les parcours en profondeur.

Contenu