:: Enseignements :: ESIPE :: E4INFO :: 2009-2010 :: Algorithmique ::

Implantation de graphes

Le but de ce tp est d'implanter une structure de graphe, ainsi que les différents algorithmes sur les graphes vus en cours. Vous disposez de plusieurs séances pour faire tous les exercices.

Exercice 1 - Représentation par liste d'ajdacence

Vous devez implanter une classe représentant un graphe codé par liste d'adjance. Vous devrez être vigilant dans vos choix d'implantation :
- Pensez au fait qu'un graphe peut être orienté ou non.
- Pensez au fait que les arêtes peuvent être pondérées.
- Pensez au fait qu'il peut être utile de maintenir des informations dans les nœuds pour implanter les algorithmes demandés (par la suite).
Vous devez redéfinir la méthode toString pour qu'elle produise une sortie au format dot. Voici un exemple tout simple de fichier dot :
```
	digraph G {
	  1 -> 2;
	  2 -> 3;
	  2 -> 4;
	  3 -> 1;
	  4 -> 2;
	};
	
```
Vous pouvez maintenant générer une représentation au format png (par exemple) de votre graphe :
```
	java -cp bin ir1.algo.tp.GraphTest | dot -Tpng -ograph.png
	
```
ou directement à l'écran :
```
	java -cp bin ir1.algo.tp.GraphTest | dot -Tx11
	
```

Exercice 2 - Calcul des composantes fortement connexes

Implantez une méthode effectuant un parcours en profondeur du graphe.
Utilisez cette méthode pour implanter une méthode de calcul des composantes fortement connexes. Cette dernière devra retourner le graphe acyclique des composantes.
Vous pouvez utiliser une liste pour stocker les sommets une fois leur traitement terminé, cela vous évitera de devoir les trier par date de fin de traitement décroissante.

Exercice 3 - Dijkstra

Implantez l'algorithme de Dijkstra sous la forme d'une méthode prenant deux sommets en argument et renvoyant la plus courte distance entre ces deux sommets.
Vous pouvez utiliser une file de priorité plutôt qu'un tableau pour améliorer la complexité de votre implantation. Pensez aux structures fournies par l'API de Java.

Exercice 4 - Kruskal

Implantez la méthode d'Union & Find vue en cours.
Utilisez là pour implanter l'algorithme de Kruskal.