18. Lezione del 1/12/03 (turno 1) e del 3/12/03 (turno 2) - LAB. UNIX

di: Algoritmi & Laboratorio ( Modulo 2 )

"Riassunto" della lezione:

• Approfondimento degli argomenti affrontati la lezione precedente.
• L'ADT grafo non orientato.
• L'ADT grafo orientato.

Esercizi assegnati (FACOLTATIVI):

1. (F29)
   Considerate l'intefaccia

   interface WeightedGraph
   {
      public void addVertex(Object info);
   
      public void setInfo(int vertex, Object info);
   
      public Object getInfo(int vertex);
   
      public void addArc(int vertex1, int vertex2, double weight);
   
      public void removeVertex (int vertex);
   
      public void removeArc(int vertex1, int vertex2);
   
      public int numberOfVertices();
       
      public Set connectedComponents();
   
      public Iterator depthFirstVisit(int vertex);
   
      public Iterator breadthFirstVisit(int vertex);
   
      public int[] primMST(int vertex);
   }
   

   che rappresenta il tipo di dato astratto "grafo non orientato e pesato con vertici numerati da 0 a n-1 contenenti un'informazione".
   Produrre la documentazione Javadoc (in italiano) per l'interfaccia WeightedGraph. ATTENZIONE: per lo stile dei commenti ispiratevi agli esempi nel libro e alla documentazione on-line della libreria Java.
2. (F30)
   Realizzate una classe AdjListWeightedGraph che implementi l'interfaccia WeightedGraph basandosi su di una rappresentazione a "lista di adiacenza".
   ATTENZIONE: PRIMA DI SCRIVERE IL BODY DEI METODI: PRODUCETE LA DOCUMENTAZIONE Javadoc E SCRIVETE GLI INVARIANTI DELLA STRUTTURA DATI.
3. (F31)
   Scrivere una classe di test con interfaccia a menu', TestWeightedGraph, per la classe AdjListWeightedGraph. La parola AdjListWeightedGraph dovra' occorrere ESATTAMENTE UNA VOLTA nel codice della classe di test. Tutti i riferimenti agli oggetti AdjListWeightedGraph dovranno essere gestiti attraverso l'interfaccia WeightedGraph.
4. (F32)
   Realizzate una classe AdjMatrixWeightedGraph che implementi l'interfaccia WeightedGraph basandosi su di una rappresentazione a "matrice di adiacenza".
   ATTENZIONE: PRIMA DI SCRIVERE IL BODY DEI METODI: PRODUCETE LA DOCUMENTAZIONE Javadoc E SCRIVETE GLI INVARIANTI DELLA STRUTTURA DATI.
5. (F33)
   Modificare la classe TestWeightedGraph dell'esercizio F31 in modo che diventi una classe di test per la classe AdjMatrixWeightedGraph dell'esercizio F32 (NOTA: e' sufficiente cambiare una parola sola del codice).