|
|
Figure 1 : (Gauche)
Exemple de
représentation d'un graphe à l'aide de listes d'adjacence.
(Droite) Exemple de représentation utilisant la matrice
d'adjacence.
Dans ce TD nous considérons des graphes qui sont censés etre planaires (et pour la plupart triangulés): néanmoins, l'implementation fournie par Jcg permet de représenter des graphes généraux, non orientés.
En ce qui concerne la représentation d'un graphe, il est
à remarquer qu'il en existe de nombreuses: nous allons
considérer ici juste une représentation, celle
basée sur une matrice
d'adjacence: c'est fait par la classe AdjacencyGraph.
En tant que structure de
données abstraite, Jcg fournit l'interface Graph qui met à
disposition un certain nombre de méthodes pour la manipulation
dàun graphe, ainsi que des primitives pour l'accès aux
incidences sommets/aretes.
On vous conseille de jeter un coup d'oeuil à la doc
de Jcg, mais en gros on a les méthodes suivantes:
public abstract class GraphDrawing<X extends Point_> {
...
}
