Intelligence Artificielle
TP 2 : Graphe - Parcours en Largeur
Esmia 2022
Rakotoarimalala Tsinjo
L’objectif de ce TP est l’implantation du parcours en largeur d’un graphe en utilisant la classe
Graphe et Sommet du TP1.
1 Préliminaires
1. Créer les attributs couleurs de type ArrayList<String> dans la classe Graphe
2. Créer les attributs predecesseurs de type ArrayList<Sommet> dans la classe Graphe
3. Créer les attributs distances de type ArrayList<Integer> dans la classe Graphe
4. Définir la méthode public int getIndice(Sommet j) qui permet de savoir à quelle position
dans l’ArrayList sommets de la classe Graphe se trouve le sommet j. Elle retourne −1 si j
n’est pas présent dans sommets
2 La Méthode pl
1. Créer la méthode public void pl(Sommet s) qui sera la méthode de implantant le parcours
en largeur du graphe courant en partant du sommet s. (On écrira le corps de cette méthode pas
à pas).
2. Écrire les premières lignes de la méthode pl qui consistera à instancier les attributs : couleurs,predecesseur
On comprendra ces attributs comme suit :
(a) La couleur du sommet à l’indice i de sommets sera stockée dans couleurs indice i (couleurs.get(i)),
(b) le prédécesseur du sommet à l’indice i de sommets sera stocké dans predecesseurs indice
i (predecesseurs.get(i)),
(c) la distance du sommet à l’indice i de sommets sera stockée dans distances indice i
(distances.get(i)).
3. Écrire la suite du corps de pl qui consiste à ajouter les couleurs, les prédécesseurs et les distances
qui seront initialisés comme suit :
• Les couleurs de tous les sommets seront en BLANC
• les prédécesseurs seront tous null
• les distances seront tous à −1
4. Écrire la suite de pl qui consiste à trouver l’indice du sommet s dans l’arraylist sommets (utiliser
la fonction getIndice).
5. Dnas la ligne suivante, mettez la couleur de s en GRIS
1
6. On va utiliser un ArrayList<Sommet> pour simuler une file. Créer cet arrayList, nommer le
file et y ajouter s.
7. La partie finale consiste à faire la boucle principale du parcours en largeur selon l’algorithme vu en
cours. La condition d’arrêt est quand file ne contiendra plus aucun élément: while(!file.isEmpty()).
Implanter la boucle principale.
Indication :
• Pour prendre la tête de la file : Sommet u= file.get(0);
• Pour supprimer la tête de la file : file.remove(0);
• Utiliser la méthode getIndice pour trouver l’emplacement des sommets à traiter.
3 Chemin d’un sommet vers un autre en utilisant pl
1. Créer la méthode public ArrayList<Sommet> cheminDeSVersU(Sommet s,Sommet u). Elle
renverra un arrayList qui stockera les sommets à visiter en partant de s pour arriver à u. (On
écrira cette méthode petit à petit)
2. Écrire les premières lignes de cheminDeSVersU qui consiste à créer un arraylist res qui stockera
le résultat. Puis lance un parcours en largeur en partant de s.
3. La ligne suivante sera la recherche de l’indice de u dans sommets (utiliser la méthode getIndice).
4. Les lignes suivantes consistent à ajouter
• u dans res
• Puis le prédécesseur de u dans res à la première position
• Puis le prédécesseur du prédécesseur de u dans res à la première position
• Ainsi de suite
• Jusqu’à s (qui a un prédécesseur null).
4 Test
1. Créer un graphe pour tester les méthodes (le graphe du TP1 sera idéal)
