96 lines
3.7 KiB
Markdown
96 lines
3.7 KiB
Markdown
|
TP Graphes 3 : Parcours et Coloration
|
|||
|
|
============
|
|||
|
|
|
|||
|
|
Le TP est prévu pour être fait en utilisant le codage des graphes à l'aide de matrices d'adjacence.
|
|||
|
|
Pour plus de clarté, vous pouvez utiliser un nouveau fichier, en copiant les structures et fonctions nécessaires depuis les TPs précédants.
|
|||
|
|
|
|||
|
|
- - - - -
|
|||
|
|
Exercice 1 : Parcours en largeur
|
|||
|
|
----------
|
|||
|
|
|
|||
|
|
Pour cet exercice, vous aurez besoin de file FIFO (First In, First Out).
|
|||
|
|
Vous pouvez par exemple utiliser la classe [`LinkedList`](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/LinkedList.html), instanciée pour les entiers avec `LinkedList<Integer>`.
|
|||
|
|
Pour utiliser une LinkedList en tant que file FIFO, vous pouvez utiliser les méthodes :
|
|||
|
|
```
|
|||
|
|
public boolean isEmpty() : Returns true if this collection contains no elements.
|
|||
|
|
Integer remove() : Retrieves and removes the head (first element) of this list.
|
|||
|
|
boolean offer(E e) : Adds the specified element as the tail (last element) of this list.
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**Question :**
|
|||
|
|
|
|||
|
|
Ecrire une fonction qui, étant donnés un graphe g et un sommet v de ce graphe, renvoie sous forme de file FIFO l'ensemble des voisins de v dans g :
|
|||
|
|
```
|
|||
|
|
public LinkedList<Integer> getVoisins(int i);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
**Question :**
|
|||
|
|
|
|||
|
|
Ecrire une fonction effectuant le parcours en largeur d'un graphe g à partir d'un sommet v.
|
|||
|
|
On pourra se contenter d'afficher sur la sortie standard la numérotation ainsi que les distances obtenues, plutôt que de les renvoyer :
|
|||
|
|
```
|
|||
|
|
public void parcoursLargeur(int v)
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**Question :**
|
|||
|
|
|
|||
|
|
Tester sur un graphe (au hasard celui des frontières). Cela correspond-t-il à une exécution manuelle de l'algorithme ?
|
|||
|
|
|
|||
|
|
|
|||
|
|
- - - - -
|
|||
|
|
Exercice 2 : Parcours en profondeur
|
|||
|
|
----------
|
|||
|
|
|
|||
|
|
Pour implémenter le parcours en profondeur d'un graphe, nous aurons besoin d'une pile.
|
|||
|
|
La classe `LinkedList` permet également de simuler des piles, avec les méthodes :
|
|||
|
|
```
|
|||
|
|
public boolean isEmpty() : Returns true if this collection contains no elements.
|
|||
|
|
Integer pop() : Pops an element from the stack represented by this list.
|
|||
|
|
void push(int i) : Pushes an element onto the stack represented by this list.
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
|
|||
|
|
**Question :**
|
|||
|
|
|
|||
|
|
Ecrire une fonction effectuant le parcours en profondeur d'un graphe g à partir d'un sommet v.
|
|||
|
|
On pourra se contenter d'afficher sur la sortie standard la numérotation de premier passage plutôt que de les renvoyer :
|
|||
|
|
```
|
|||
|
|
public void parcoursProfondeur(int i);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
**Question :**
|
|||
|
|
|
|||
|
|
Tester sur un graphe (au hasard celui des frontières). Cela correspond-t-il à une exécution manuelle de l'algorithme ?
|
|||
|
|
|
|||
|
|
**Question :**
|
|||
|
|
|
|||
|
|
Adaptez votre code pour également calculer, puis afficher, la numérotation de dernier passage.
|
|||
|
|
|
|||
|
|
- - - - -
|
|||
|
|
Exercice 3 : Algorithme de Welsh-Powell
|
|||
|
|
----------
|
|||
|
|
|
|||
|
|
On va implémenter l'algorithme de Welsh-Powell de coloriage glouton des graphes.
|
|||
|
|
Les premières questions visent à donner des fonctions aidant à l'implémentation de l'algorithme. A vous de les suivre ou non.
|
|||
|
|
|
|||
|
|
**Question : Liste des sommets selon leur degré**
|
|||
|
|
|
|||
|
|
-Créer une fonction `private int[] tableauDegre();` renvoyant un tableau où la case i contient le degré du sommet i.
|
|||
|
|
|
|||
|
|
-Créer une fonction `private int indiceMax(int[] tab);` renvoyant l'indice de la plus grande valeur du tableau tab.
|
|||
|
|
|
|||
|
|
-En utilisant les deux premières fonctions, créer une fonction `private LinkedList<Integer> listeDegre()` renvoyant une liste des sommets classés selon leur degré.
|
|||
|
|
|
|||
|
|
**Question**
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
**Question**
|
|||
|
|
|
|||
|
|
Enfin, implémentez l'algorithme de Welsh-Powell.
|
|||
|
|
|
|||
|
|
Indice : Vous aurez besoin de la liste des sommets triés selon leur degré. On peut retirer un élément i donné de la liste l avec `l.remove((Integer) i)`.
|