Scribd
Importer
100 vues1 page

Algorithmes de parcours de graphes BFS et DFS

Ce document décrit deux algorithmes de parcours de graphe: le parcours en largeur d'abord (BFS) et le parcours en profondeur d'abord (DFS). Il présente les étapes pour implémenter ces algorithmes et affiche l'ordre de visite des sommets pour chaque méthode.

Transféré par

efgl12
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
100 vues1 page

Algorithmes de parcours de graphes BFS et DFS

Ce document décrit deux algorithmes de parcours de graphe: le parcours en largeur d'abord (BFS) et le parcours en profondeur d'abord (DFS). Il présente les étapes pour implémenter ces algorithmes et affiche l'ordre de visite des sommets pour chaque méthode.

Transféré par

efgl12
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Spé: Algorithmique et programmation 2/ BD CPGE TANGER

Parcours :
Le parcours en largeur d'abord :BFS (Breadh First Search )
Le parcours en profondeur d'abord DFS (Depht First Search)

Ecrire la fonction succ(g,s):


Ecrire la fonction succNonVisite(g,s,test):
Ecrire la fonction parcoursProfondeur(g) qui affiche le graphe g en utilisant le parcours DFS :

 Initialement tous les nœuds sont marqués " non visités".


 Choisir un nœud v de départ et le marquer " visité".
 Chaque nœud adjacent à v, non visité, est à son tour visité en utilisant DFS
 Une fois tous les nœuds accessibles à partir de v ont été visités, la recherche de v ( DFS(v) ) est complète.
 Si certains nœuds du graphe restent "non visités", sélectionner un comme nouveau nœud de départ et répéter
que tous les nœuds soient visités.

Ecrire la fonction parcoursLargeur(g) qui affiche le graphe g en utilisant le parcours BFS :

parcours en largeur du graphe précèdent visite les sommets dans l’ordre suivant : A, B, D, E, C, G, F, H, I

48 Prof : ZBAKH ABDEL ALI <[email protected]>

Vous aimerez peut-être aussi