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.

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 FIFO dans laquelle il prend le premier sommet et place en dernier ses voisins non encore explorés.

Si le graphe est cyclique, il faudra en outre marquer les sommets déjà visités pour que l'algorithme puisse se terminer.


  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.

Implémentation

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.

Ce document provient de « Algorithme de parcours en largeur ».

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

  • 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 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 (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

  • 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 Graham — 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… …   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

  • 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

Share the article and excerpts

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