10.4. Recherche en largeur

L'algorithme de recherche en profondeur ("Depth-First-Search") permet d'explorer un graphe, d'en déterminer les composantes connexes et de découvrir s'il contient des cycles. Cependant, cet algorithme n'est pas le seul algorithme fondamental des graphes. Il faut mentionner un autre algorithme de parcours qui est à la base de la résolution de problèmes tels que celui du chemin minimum. Cet algorithme est dit de recherche en largeur ("Breadth-First-Search").

Considérons le graphe de la figure 10.9 comme support à la description de l'algorithme de parcours en largeur. Ce graphe est connexe, c'est-à-dire formé d'une seule composante, il est obtenu en ajoutant à l'exemple de la figure 10.1 les arcs : GC, GH, JG, LG.

NB : Ce graphe contient quatre points d'articulation, c'est-à-dire un sommet qui, s'il est éliminé, "casse" le graphe en deux ou plusieurs morceaux.

Ce sont :
A qui déconnecte B
H qui déconnecte I
J qui déconnecte K
G qui produit 3 composantes.

Nous obtenons pour ce graphe les chaînes de connectivité suivantes :

A
: F C G B
B
: A
C
: G A
D
: E F
E
: G F D
F
: D E A
G
: L J H A C E
H
: G I
I
: H
J
: L M K G
K
: J
L
: M J G
M
: J L

Fig. 10.10. Chaînes de connectivité correspondant au graphe de la figure 10.9.

Si l'on fait l'analogie avec le parcours d'un labyrinthe, à chaque fois que l'on se trouve seul face à un choix de plusieurs sommets possibles vers lesquels se diriger, on ne peut qu'emprunter un seul chemin vers l'un d'entre eux et laisser les autres chemins en attente afin de les explorer plus tard (parcours en profondeur : DFS). Si l'on suppose, par contre, que tout un groupe de personnes entreprennent l'exploration, à chaque carrefour, le groupe pourra se partager pour aller dans toutes les directions à la fois (parcours en largeur : BFS).

10.4.1. Méthode générale de parcours de graphe

Afin de décrire un algorithme de parcours en largeur, nous allons étudier une méthode plus générale de parcours de graphe que l'on puisse utiliser pour implanter le DFS aussi bien que le BFS. Cette méthode consiste à classer les sommets en 3 catégories :

Les différentes variantes de parcours dépendront de la manière dont on fait passer les sommets de la catégorie C à la catégorie B et de la B dans la A. Sur la base de cette généralisation et dans le but d'implanter la procédure "Visite" vue précédemment, on construit l'état initial suivant :

On répète alors les opérations suivantes :

Plusieurs méthodes de parcours de graphes peuvent ainsi être envisagées en fonction de :

  1. Quel sommet de B va dans A (si B en contient plusieurs).
  2. Comment place-t-on les sommets dans B.

10.4.2. Méthode générale appliquée au DFS

Pour l'algorithme de "DFS", on choisira toujours le sommet qui a été mis le plus récemment dans la catégorie B pour l'ajouter à l'arbre de parcours (c.à.d. le faire passer en A). Ceci peut être réalisé en :

a)
faisant passer le premier sommet (x) de B dans A;
b)
insérant au début de B les sommets de C adjacents à x;
c)
déplaçant dans B vers le début les sommets adjacents à x qui se trouvaient déjà dans B.

NB : Sans ce dernier point, on obtient un algorithme de parcours tout à fait différent qui n'est plus le DFS.

La figure 10.11 qui suit montre le contenu des catégories A et B au fur et à mesure de l'avancement de l'algorithme. 

	 	catégorie A 		catégorie B
	 1-ère étape 	- 		A
	 2-ème étape 	A 		B G C F
	 3-ème étape	AB 		G C F
	 4-ème étape	ABG 		E C H J L F
	 5-ème étape	ABGE 		D F C H J L
	 6-ème étape	ABGED 		F C H J L
	 7-ème étape	ABGEDF 		C H J L
	 8-ème étape	ABGEDFC 	H J L
	 9-ème étape	ABGEDFCH 	I J L
	10-ème étape	ABGEDFCHI 	J L
	11-ème étape	ABGEDFCHIJ 	K M L
	12-ème étape	ABGEDFCHIJK 	M L
	13-ème étape	ABGEDFCHIJKM 	L
	14-ème étape	ABGEDFCHIJKML 	-
Fig. 10.11. Etapes du parcours en profondeur.

Dans cet exemple la catégorie B est essentiellement organisée "comme une pile" à ceci près que certains éléments déjà dans B sont changés de place (ramenés vers l'avant de la pile). Sont marqués en pointillés dans l'arbre de parcours de la figure 10.12 les arcs inutilisés car aboutissant à un sommet déjà traité.

Il faut remarquer que l'arbre de parcours est différent de celui qu'on obtiendrait en exécutant la procédure récursive "DFS" vue précédemment. Il y a en effet plusieurs manières de parcourir un graphe en profondeur (en largeur aussi) puisqu'il n'y a pas d'ordre particulier pour le traitement des arcs partant d'un même sommet.

Cependant la structure représentant les sommets de catégorie B ne contient pas suffisamment d'informations pour permettre la construction de l'arbre de parcours; pour cela, il faut accompagner chaque élément entré dans la structure du nom de son "père", c'est-à-dire du nom du sommet qui l'introduit parce qu'il figure dans sa liste de connectivité. Il faut éventuellement modifier cette information si le sommet est déplacé à l'intérieur de B.

10.4.3. Méthode générale appliquée au BFS

Une autre manière classique d'organiser les sommets de la catégorie B est d'avoir recours à une structure de file d'attente. Dans ce cas, on extrait de B l'élément le plus ancien et on insère les nouveaux éléments en fin de liste. Cette méthode est celle qui conduit à l'algorithme de parcours en largeur (Breadth-First-Search) :

a)
on visite un sommet x;
b)
on visite tous les sommets qui lui sont adjacents;
c)
ensuite tous les sommets adjacents à ceux-ci; etc.

Sur la base de notre graphe-exemple, ceci produit l'effet suivant : 

 	  	catégorie A	catégorie B
	 1-ère étape	- 		A
	 2-ème étape	A 		F C B G
	 3-ème étape	AF 		C B G D E
	 4-ème étape	AFC 		B G D E
	 5-ème étape	AFCB 		G D E
	 6-ème étape	AFCBG 		D E L J H
	 7-ème étape	AFCBGD 		E L J H
	 8-ème étape	AFCBGDE 	L J H
	 9-ème étape	AFCBGDEL 	J H M
	10-ème étape	AFCBGDELJ 	H M K
	11-ème étape	AFCBGDELJH 	M K I
	12-ème étape	AFCBGDELJHM 	K I
	13-ème étape	AFCBGDELJHMK 	I
	14-ème étape	AFCBGDELJHMKI 	-
Fig. 10.13. Etapes du parcours en largeur.

On extrait un sommet x du début de B (à gauche), on explore la liste de connectivité de x en insérant à la fin de B (à droite) les sommets encore invisibles. Cela donne l'arbre de parcours suivant :

L'algorithme correspondant est le suivant: 

procedure BFS(NbSommets: integer);

{ On suppose, pour cet algorithme, que
  l'on a accès à des primitives de gestion
  de file d'attente, telles qu'on les a
  vues au chapitre sur les structures
  dynamiques linéaires. }

const Inexplore = -1;
      EnAttente = 0;

var File: FileDAttenteDEntiers;
    Index: integer:
    CmptrVisite,
    IndexSommet : 0..MaxNbSommets;
    NumeroDOrdre: array[1..MaxNbSommets]
                  of integer;

procedure Visite (IndexSommet : integer);
var Voisin : Ref;
begin { Visite }
  { attribue un numéro d'ordre au sommet }
  CmptrVisite := CmptrVisite + 1;
  NumeroDOrdre[IndexSommet]:=CmptrVisite;
  { parcoure la chaîne de connectivité }
  Voisin := PremierVoisin[IndexSommet];
  while Voisin <> nil do
    with Voisin^ do begin
      { met chaque voisin inexploré sur la
        file d'attente }
      if NumeroDOrdre[IndexVoisin]=Inexplore
      then begin
        Met(File,IndexVoisin);
        NumeroDOrdre[IndexVoisin]:=EnAttente;
        end; { if }
      Voisin := Suivant;
      end; { with }
end; { Visite }

begin { BFS }
  { initialisations }
  CmptrVisite := 0;
  Initialise(File);

  for IndexSommet:= 1 to NbSommets do
    NumeroDOrdre[IndexSommet]:=Inexplore;

  { visite chaque sommet non exploré }
  for IndexSommet := 1 to NbSommets do
    if NumeroDOrdre[IndexSommet]=Inexplore
    then begin
      { visite toute la composante connexe
        liée au sommet non-exploré. }
      Visite (IndexSommet);
      while not Vide(File) do begin
        Ote(File,Index);
        Visite(Index);
        end; { while }
      end; { if }
end; { BFS }

10.5. Parcours d'un labyrinthe

Table des matières.

Site Hosting: Bronco