GPS - Algorithme de parcours en largeur

Exemple de parcours en largeur

Présentation :

Cet algorithme nous permet de parcourir un graphe de manière itérative, en utilisant une file. Ce dernier peut nous servir à déterminer la connexité d'un graphe.

Remarque :Lorsque l'algorithme est appliqué à un graphe quelconque, les sommets déjà visités doivent être marqués afin d'éviter qu'un même sommet soit exploré plusieurs fois. Dans le cas particulier d'un arbre, ce n'est pas nécessaire.

Étapes de l'algorithme :

1. Mettre le nœud de départ dans la file.

2. Retirer le nœud du début de la file pour l'examiner.

3. Mettre tous les voisins non examinés dans la file (à la fin).

4. Si la file n'est pas vide reprendre à l'étape 2.

Pseudo code de l'algorithme de parcours en largeur :

ParcoursLargeur(Sommet s):

{

f = CreerFile();

f.enfiler(s);

marquer(s);

Tant que non f.vide() faire

s = f.defiler();

afficher(s);

Pour tout voisin de s faire

si voisin non marqué faire

f.enfiler(voisin);

marquer(voisin);

Fin si

Fin pour tout

Fin tant que

}