Algorithme de parcours en largeur

Algorithme de parcours en largeur
Page d'aide sur l'homonymie Pour les articles homonymes, voir BFS.

L'algorithme de parcours en largeur (ou BFS, pour Breadth First Search) permet le parcours d'un graphe de manière itérative, en utilisant une file. Il peut par exemple servir à déterminer la connexité d'un graphe.

Sommaire

Principe

Cet algorithme diffère de l'algorithme de parcours en profondeur par le fait que, à partir d'un sommet S, il liste d'abord les voisins de S pour ensuite les explorer un par un. Ce mode de fonctionnement utilise donc une file dans laquelle il prend le premier sommet et place en dernier ses voisins non encore explorés.

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

BFS(graphe G, sommet s):
{
  f = CreerFile();
  Marquer(s);
  Enfiler(f, s);
  TANT-QUE NON FileVide(f) FAIRE
      x = Défiler(f);
      Afficher(x)
      TANT-QUE ExisteFils(x) FAIRE
          z = FilsSuivant(x);
          SI NonMarqué(z) ALORS 
              Marquer(z);
              Enfiler(f, z);
          FIN-SI
      FIN-TANT-QUE
  FIN-TANT-QUE
}

Exemple

Sur le graphe suivant, cet algorithme va alors fonctionner ainsi :

Graphes.dfs-bfs.exemple.png

Il explore dans l'ordre les sommets A, B, C, E, D, F, G, contrairement à l'algorithme de parcours en profondeur qui cherche dans cet ordre : A, B, D, F, C, G, E.

Applications

Le parcours en largeur explore tous les sommets accessibles depuis le sommet initial. Il permet de calculer les composantes connexes du graphe avec une complexité linéaire.

De plus, lors de ce parcours, les sommets sont explorés par distance croissante au sommet de départ. Grâce à cette propriété, on peut utiliser l'algorithme pour résoudre le plus simple des problèmes de cheminement : calculer le plus court chemin entre deux sommets dans un graphe non pondéré.

Voir aussi


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de parcours en largeur de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Algorithme De Parcours En Largeur — Pour les articles homonymes, voir BFS. L algorithme de parcours en largeur (ou BFS, pour Breadth First Search) permet le parcours d un graphe de manière itérative, en utilisant une file. Il peut par exemple servir à déterminer la connexité d un… …   Wikipédia en Français

  • Algorithme De Parcours En Profondeur — L algorithme de parcours en profondeur (ou DFS, pour Depth First Search) est le principe qui s abstrait de ce qu on connait comme la façon simple de parcourir un labyrinthe sans tourner en rond. La pédagogie de l informatique l enseigne aujourd… …   Wikipédia en Français

  • Algorithme de parcours en profondeur — L algorithme de parcours en profondeur (ou DFS, pour Depth First Search) est un algorithme de parcours de graphe qui se décrit naturellement de manière récursive. Son application la plus simple consiste à déterminer s il existe un chemin d un… …   Wikipédia en Français

  • Parcours (graphe) — Pour les articles homonymes, voir Parcours (homonymie).  Pour l’article homophone, voir parkour. En théorie des graphes, un parcours de sommets (resp. d arêtes, d arcs) dans un graphe G est une liste ordonnée de sommets (resp. d arêtes, d… …   Wikipédia en Français

  • Algorithme De Dijkstra — En théorie des graphes, l algorithme de Dijkstra sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer le plus court chemin pour se rendre d une ville à une autre connaissant le réseau routier d une région. Il s… …   Wikipédia en Français

  • Algorithme de dijkstra — En théorie des graphes, l algorithme de Dijkstra sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer le plus court chemin pour se rendre d une ville à une autre connaissant le réseau routier d une région. Il s… …   Wikipédia en Français

  • Algorithme de recherche en faisceau — En informatique, la recherche en faisceau est un algorithme de recherche heuristique qui explore un graphe en ne considérant qu un ensemble limité de fils de chaque nœud. La recherche en faisceau est une optimisation de l algorithme de parcours… …   Wikipédia en Français

  • Algorithme de Dijkstra — En théorie des graphes, l algorithme de Dijkstra (prononcer [dɛjkstra]) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer le plus court chemin pour se rendre d une ville à une autre connaissant le réseau… …   Wikipédia en Français

  • Parcours de graphe —  Pour l’article homophone, voir parkour. En théorie des graphes, un parcours de graphe est un algorithme consistant à explorer les sommets d un graphe de proche en proche à partir d un sommet initial. Le mot parcours est également utilisé… …   Wikipédia en Français

  • Parcours de graham — Le parcours de Graham est un algorithme déterminant l enveloppe convexe d un ensemble de points. Son principal intérêt est sa complexité algorithmique en O(n log n). Cet algorithme doit son nom à Ronald Graham, qui a publié l algorithme original… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”