Travaux Pratiques : Algorithme DFS
Licence 2 Génie Logiciel
Institut Supérieur Informatique
Objectif
Les étudiants doivent implémenter et comparer les deux versions de l’algorithme de parcours en profondeur
(DFS) : récursive et itérative. Ce TP vise également à encourager les étudiants à apprendre à se documenter
et à utiliser des ressources externes pour approfondir leurs connaissances.
Organisation des groupes
Formez des groupes de trois étudiants.
Ressources fournies
• Un document explicatif sur l’algorithme DFS, contenant des informations théoriques, des pseudocodes
et des exemples de graphes.
• Le site de Wikipedia pour des informations supplémentaires : Depth-First Search on Wikipedia.
Étapes du TP
1. Étude des ressources fournies
• Lire et comprendre le document explicatif sur l’algorithme DFS.
• Consulter l’article Wikipedia pour des informations complémentaires et des exemples supplémentaires.
• Étudier les pseudocodes des versions récursive et itérative de DFS.
2. Implémentation de la version récursive
• Choisir un langage de programmation.
• Implémenter l’algorithme DFS récursif selon le pseudocode fourni.
• Tester l’implémentation avec des graphes fournis.
3. Implémentation de la version itérative
• Implémenter l’algorithme DFS itératif selon le pseudocode fourni.
• Tester l’implémentation avec les mêmes graphes.
4. Analyse et Présentation
• Comparer les deux versions en termes de complexité, lisibilité et performance.
• Préparer une présentation des résultats, comprenant des exemples d’exécution, les avantages et les
inconvénients de chaque version.
Livrables
• Code source des implémentations récursive et itérative.
1
• Résultats des tests effectués.
• Présentation résumant le travail et les conclusions du groupe.