Scribd
Importer
12 vues2 pages

TP 1

Ce document présente un TP sur l'implantation de graphes en utilisant à la fois une matrice d'adjacence et une liste d'adjacence. Il décrit les classes à créer, leurs attributs et méthodes, ainsi que les étapes pour construire un graphe et manipuler ses sommets. Les méthodes incluent l'ajout d'arêtes, la vérification de voisinage, et la recherche de sommets par étiquette.

Transféré par

gabinrkt
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
12 vues2 pages

TP 1

Ce document présente un TP sur l'implantation de graphes en utilisant à la fois une matrice d'adjacence et une liste d'adjacence. Il décrit les classes à créer, leurs attributs et méthodes, ainsi que les étapes pour construire un graphe et manipuler ses sommets. Les méthodes incluent l'ajout d'arêtes, la vérification de voisinage, et la recherche de sommets par étiquette.

Transféré par

gabinrkt
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

Intelligence Artificielle

TP 1 : Graphe
Esmia 2022
Rakotoarimalala Tsinjo

L’objectif de ce TP est l’implantation de graphe sous la forme matrice d’adjacence et par liste
d’adjacence.
Si besoin vous pouvez ajouter des attributs ou des méthodes pour répondre aux questions.

1 Graphe non orienté par matrice d’adjacence


1. Créer une classe GrapheMatrice ayant les attributs suivants:

• un tableau d’entier à deux dimensions appelés matrice


• un entier stockant le nombre de sommet du graphe appelé taille

2. Créer un constructeur de la classe GrapheMatrice prenant en paramètre un entier qui sera la


taille du graphe. Ce constructeur allouera aussi le tableau matrice

3. Créer la méthode ajouterArete (int i, int j) qui ajoutera une arête entre les sommets i et
j.

4. Dans main, créer le graphe suivant c’est-à-dire un objet de type GrapheMatrice, ajouter les
noeuds et les sommets

5. Créer la méthode sontVoisins(int i, int j) qui retourne true si le sommet i et j sont voisins,
false sinon.

6. Créer la méthode voisins(int i) qui affiche la liste des voisins du sommet i.

7. Créer la méthode degre(int i) qui retourne le degré du sommet i.

1
2 Graphe par liste d’adjacence
1. Créer une classe Sommet ayant les attributs suivants:

• une chaîne de caractère appelé label (étiquette/nom du sommet)


• une liste (ArrayList) d’objet de type Sommet appelé voisins

2. Créer la méthode ajouterArete(Sommet j) de la classe Sommet qui ajoute le sommet j à la liste


de voisins du sommet courant.

3. Créer la méthode voisins() qui affiche la liste des voisins du sommet courant.

4. Créer la méthode degre() qui retourne le degré du sommet courant.

5. Créer la méthode estVoisin(Sommet j) qui retourne true si le sommet courant et le sommet j


sont voisins, false sinon.

6. Créer une classe Graphe ayant un attribut (appelé sommet) une liste d’objet de type Sommet.

7. Dans main, créer le graphe suivant (créer un objet de type Graphe et les sommets):

8. Créer la méthode rechercherSommetParLabel(String lab) de la classe Graphe, qui recherche


s’il y a un sommet avec un label lab dans la liste de sommet du graphe et retourne ce sommet
si trouvé sinon elle retourne null.

Vous aimerez peut-être aussi