Lab 9

Implémentation d'une liste d'adjacence d'un graphe et le DFS

Télécharger l'archive Lab9.zip et extraire l'application SimpleGraph. L'application lit une liste d'arêtes (edge-list) à partir d'un fichier et construit un Graphe. Le graphe est stocké comme AdjacencyListGraph. L'application imprime tous les sommets suivis par tous les arêtes. L’archive contient également deux fichiers des graphes que vous pouvez utiliser comme entrée pour l'application:

· graph.txt

· graph2.txt

Nouvel Graphe

Définir un nouveau graphe dans un fichier texte et l'imprimer en utilisant cette application.

Étude de l'implémentation de Goodrich et al.

Étudier l'implémentation de l'ADT Graphe de AdjacencyListGraph par Goodrich et al. en gardant à l’esprit de la structure discutée en classe. Notez que les listes d'adjacence sont implémentées dans la classe interne MyVertex et les références sur les arêtes dans la classe interne MyEdge. L'ADT graphe ne définit aucune méthode de traversée. Le parcours de graphes est implémenté dans des de classes distinctes DFS. Ces classes font partie du paquetage net.datastructures qui est contenu dans l'archive de ce laboratoire.

Impression avec DFS génériques

Le programme SimpleGraph a une méthode printDFS (String vert) qui ne fait actuellement rien. Implementer cette méthode en dérivant DFS (i.e. créer une sous-classe de DFS). Une classe interne anonyme serait appropriée. La méthode doit imprimer les sommets visités par le parcours: une fois quand ils sont d'abord visité et une seconde fois quand un sommet est terminé.