Il tipo di dato astratto Grafo¶

Un tipo di dato astratto o ADT (Abstract Data Type) è un tipo di dato le cui istanze possono essere manipolate con modalità che dipendono esclusivamente dalla semantica del dato e non dalla sua realizzazione.

L’interfaccia di un grafo che permette l’interazione e la modifica del tipo di dato Grafo è la seguente:

• Graph() crea un nuovo grafo vuoto.
• addVertex(vert) aggiunge una istanza di Vertex al grafo.
• addEdge(fromVert, toVert) aggiunge un nuovo arco diretto al grafo, connettendo i due vertici specificati in input.
• addEdge(fromVert, toVert, weight) aggiunge un nuovo arco diretto e pesato che connette i due vertici specificati in input.
• getVertex(vertKey) trova in un grafo un vertice chiamato vertKey.
• getVertices() ritorna la lista di tutti i vertici nel grafo.
• in ritorna True per una richiesta del tipo vertex in graph, se il dato vertice è nel grafo, False altrimenti.

Ci sono molti modi che possiamo usare per implementare l’ADT grafo in Python. Vedremo che ci sono compromessi nell’usare le diverse rappresentazioni. Due modi classici sono la matrice di adiacenza e la lista di adiacenza.