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
voirdes sommets qui restent à visiter, et qui est initialisée par le sommet {i.} - la liste
vusdes 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 listevoir, et on recommence.
|
1 2 3 4 5 6 7 8 9 |
let bfs_gl g i = (* parcourir le graphe g à partir du sommet i, en mode "breadth first search" *) let rec aux vus voir = (* vus = liste des sommets déjà visités *) match voir with (* voir = liste des sommets qui restent à visiter *) | [] -> List.rev vus (* si plus rien à voir, renvoie vus, i en t^ete *) | j :: q -> if List.mem j vus (* si le sommet j à voir a en fait déjà été vu *) then aux vus q (* on l'ignore, et on visite les suivants *) (* sinon, ajouter j à "vus", ajouter voisins g.(j) après "voir", et recommencer *) else aux (j :: vus) (q @ g.(j)) in aux [] [i];; |
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é :
|
1 2 3 |
let gl1 = [|[4; 5]; [3; 4]; [0]; [5]; [1]; [0; 2; 3]; [3; 5]; [1; 3; 4; 5]|] in bfs_gl gl1 0;; - : int list = [0; 4; 5; 1; 2; 3] (* à partir de 0, on ne peut atteindre ni 6 ni 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 :
|
1 2 3 |
let gl2 = [| [2;4;5]; [3;4;7]; [0;5]; [1;5;6;7]; [0;1;7]; [0;2;3;6;7]; [3;5]; [1;3;4;5]|] in bfs_gl gl2 0;; - : int list = [0; 2; 4; 5; 1; 7; 3; 6] (* à partir de 0, on peut atteindre tous les sommets *) |
déjà visités à visiter

[] [_] {\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] []
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres