Parcours en largeur Python – Algorithme sur les Graphes

Parcours en largeur Python - Algorithme sur les Graphes

Le parcours en largeur python d’un graphe (BFS) est un algorithme utilisé pour parcourir les structures de donnée de graphe. BFS met en œuvre une stratégie spécifique pour visiter tous les sommets d’un graphe.

Introduction – Parcours en largeur python

BFS commence par un sommet, puis il vérifie les voisins du sommet initial, puis les voisins des voisins, etc.

En entrée de l’algorithme il y a le graphe G et un sommet de départ D pour lequel on considère que la distance est 0.

En sortie de l’algorithme sont calculées toutes les distances entre le sommet D et chaque sommet du graphe G ainsi que l’arbre couvrant si le graphe G est connexe (c’est à dire que pour toute paire de sommet il existe un chemin entre eux dans le graphe).

Description de l’algorithme

On utilise les tableaux suivants :

  • Distance[.] : Stocke la distance entre D (sommet de départ) et un autre sommet du graphe.
  • Father[.] : Stocke le sommet père d’un sommet du graphe parcouru.
  • Visite[.] : Stocke l’état de visite du sommet, liste des valeurs possible 0:pas encore visité,1:Visite en cours,2:Visité

On utilise les fonctions suivantes pour une file F :

  • First(F) : Retourne l’élément en tête de la file F sans le supprimer.
  • Dequeue(F) : Retourne l’élément en tête de la file F en le supprimant.
  • Append(F, A) : Mettre l’élément A dans la file F en queue de la file.

Les étapes de l’algorithme :

  • Phase d’initialisation
    • 1. Pour tous les sommets faire
      • Visite = 0 (Pas encore visité)
      • Pere = null (Initialise le tableau)
      • Distance = -1
    • 2. Append(F,D) (ajoute l’élément de départ)
    • 3. Distance[R] = 0 (postulat de départ)
  • Phase d’action (parcours du graphe G)
    • Tant que la file F n’est pas vide
      • t = First(F)
      • Pour tous les voisins v de t faire
        • Si Visite[v] = 0 (sommet non visité) alors
          • Visite[v] = 1 (Visite en cours)
          • Distance[v] = Distance[t] + 1
          • Father[v] = t
          • Append(F,v)
      • Dequeue(F)
      • Visite[t] = 2

Si on détaille les étapes avec le cas du graphe exemple ci-dessous.

Phase d’initialisation :

Parcours en largeur Python - Algorithme sur les Graphes

Initialisation l’élément A est l’élément de départ à distance 0, il est coloré en orange pour indiquer que la visite est en cours.

Visite des voisins du sommet A (Visite du sommet B)

Parcours en largeur Python - Algorithme sur les Graphes
Le sommet B passe à en cours de visite, sa distance de A est calculée et le sommet A est ajouté comme sommet père. Il est ajouté à la file.

Visite des voisins du sommet A (Visite du sommet C)

Parcours en largeur Python - Algorithme sur les Graphes
Le sommet C passe à en cours de visite, sa distance de A est calculée et le sommet A est ajouté comme sommet père. Il est ajouté à la file.

Marquage de A comme visité et suppression de la file

Parcours en largeur Python - Algorithme sur les Graphes
A est marqué comme visité (couleur bleue) et retiré de la tête de la file

Visite des voisins du sommet B (Visite du sommet D)

Parcours en largeur Python - Algorithme sur les Graphes
Le sommet C etant marqué comme en cours de visite il ne sera pas visité, on visite le sommet D on calcule sa distance = 2 et on note le sommet B comme père du sommet B.

Marquage de B et C comme visité et suppression de la file

B est marqué comme visité (couleur bleue) et retiré de la tête de la file
C est marqué comme visité (couleur bleue) et retiré de la tête de la file (son voisin D est marqué en cours de visite)

Marquage de D comme visité et fin de l’algorithme

Parcours en largeur Python - Algorithme sur les Graphes
D est marqué comme visité (couleur bleue) et retiré de la tête de la file.
Fin de l’algorithme

Construction de l’arbre couvrant si le graphe est connexe

Parcours en largeur Python - Algorithme sur les Graphes
Si le graphe est connexe on déplie le résultat du parcours et on obtient l’arbre couvrant du graphe qui contient tous les sommets.

Application : Le parcours en largeur d’un graphe (BFS) est utile pour :

  • Vérifier si un graphe est connexe (tous les sommets sont alors marqués comme visités à la fin de l’algorithme).
  • Calculer les distances à partir d’un sommet donné
  • Construire un arbre couvrant du graphe

Parcours en largeur python – Liens externes

https://fr.wikipedia.org/wiki/Python_(langage)

https://www.python.org/

https://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_largeur

Parcours en largeur python – Liens internes

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/2021/01/21/algorithme-glouton-python/

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *