Parcours dans un graphe

Le parcours d’un graphe consiste à énumérer les sommets qui sont accessibles (par un chemin) à partir d’un sommet donné.

13.5.1 Parcours en largeur (BFS)

On cherche donc à énumérer les sommets accessibles depuis un sommet {i} d’un graphe {G(S,A).}

On suppose ici que le graphe {G} est représenté par le tableau des listes d’adjacence.

Le parcours en largeur (BFS : Breadth First Search ) consiste à maintenir deux listes :

  • la liste voir des sommets qui restent à visiter, et qui est initialisée par le sommet {i.}
  • la liste vus des sommets déjà visités, et qui est initialisée par la liste vide.

À chaque étape, on retire le premier sommet {j} de la liste des sommets à voir :

  • si {j} fait partie de la liste des sommets visités, alors on passe au sommet suivant dans la liste voir
  • sinon on ajoute {j} à la liste vus, on ajoute les voisins de {j} à la fin de la liste voir, et on recommence.

Voici un exemple avec le graphe orienté {G_{1}.} On marque les étapes successives du parcours à partir du sommet 0 (à chaque fois, on indique la liste voir des éléments qui doivent être visités et la liste vus de ceux qui l’ont déjà été :

Figure du chapitre 13, page 7

déjà visités à visiter déjà visités à visiter

[] [0] [2; 1; 5; 4; 0] [3; 3; 4; 0]

[0] [4; 5] [3; 2; 1; 5; 4; 0] [3; 4; 0; 5]

[4; 0] [5; 1] [3; 2; 1; 5; 4; 0] [4; 0; 5]

[5; 4; 0] [1; 0; 2; 3] [3; 2; 1; 5; 4; 0] [0; 5]

[1; 5; 4; 0] [0; 2; 3; 3; 4] [3; 2; 1; 5; 4; 0] [5]

[1; 5; 4; 0] [2; 3; 3; 4] [3; 2; 1; 5; 4; 0] [] {G_{1}:} graphe orienté à 8 sommets

Même chose, mais avec le graphe non orienté {G_{2}.} On marque les étapes successives du parcours à partir du sommet 0 :

déjà visités à visiter

Figure du chapitre 13, page 7

[] [_] {\frac{\frac{\frac{\frac{\mathtt{0}}{\mathtt{2}}}{\mathtt{4}}}{\mathtt{5}}}{\mathtt{0}}} [0] [_; 4; 5] [2; 0] [_; 5; 0; 5] [4; 2; 0] [_; 0; 5; 0; 1; 7] [5; 4; 2; 0] [ ; 5; 0;_; 7; 0; 2; 3; 6; 7] {\frac{\mathtt{1}}{\mathtt{3}}} [1; 5; 4; 2; 0] [_; 0; 2; ; 6; 7; 3; 4; 7] {\frac{\mathtt{7}}{\mathtt{0}}} [7; 1; 5; 4; 2; 0] [ ; 2;_; 6; 7; 3; 4; 7; 1; 3; 4; 5] {\frac{\mathtt{3}}{\mathtt{3}}} [3; 7; 1; 5; 4; 2; 0] [_; 7; ; 4; 7; 1; 3; 4; 5; 1; 5; 6; 7] {\frac{\mathtt{6}}{\mathtt{7}}} [6; 3; 7; 1; 5; 4; 2; 0] [ ; 3; 4; 7; 1; 3; 4; 5; 1; 5; 6; 7; 3; 5] {G_{2}:} non orienté à 8 sommets [6; 3; 7; 1; 5; 4; 2; 0] []

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :