Appunti dell'intera parte di teoria del corso di Algoritmi e strutture dati

ADT GRAFO

Perché la Teoria dei Grafi?

  

Moltissime applicazioni pratiche Centinaia di algoritmi Astrazione interessante e utilizzabile in molti



domini diversi Ricerca attiva in Informatica e Matematica discreta.

Complessità dei problemi

  

problemi facili: determinare se un grafo è connesso determinare la presenza di un ciclo individuare

 

le componenti fortemente connesse individuare gli alberi minimi ricoprenti calcolare i cammini minimi

   

determinare se un grafo è bipartito trovare un cammino di Eulero problemi trattabili: planarità di



un grafo matching  

problemi intrattabili: cammini a lunghezza massima color abilità (Dato un grafo non orientato G =(V,E),

quale è il minimo numero di colori k necessario affinché nessun vertice abbia lo stesso colore di un vertice

ad esso adiacente? Si dice «planare» un grafo che, se disegnato su di un piano, non ha archi che si

 

intersecano. Le mappe geografiche sono modellate come grafi planari. ) clique massimale ciclo di

Hamilton (Dato un grafo non orientato G =(V,E), esiste un ciclo semplice che visita ogni vertice una e una

 

sola volta?) problema del commesso viaggiatore problemi di complessità ignota: isomorfismo di due



grafi F e G: isomorfismo fra G e H: applicazione biiettiva f dai vertici di Gai vertici di H tale che vi sia un



arco dal vertice u al vertice v in G se e solo se c'è un arco dal vertice f(u) al vertice f(v) in H non esiste un

algoritmo polinomiale, ma non è stato provato che il problema è NP-completo.

L’ADT Grafo

Il modello più generale è il grafo orientato e pesato. Per efficienza si implementano ADT specifici per le 4

  

tipologie Dopo l’inizializzazione: Grafi statici: non si aggiungono né si cancellano né vertici né archi



Grafi semi-statici: non si aggiungono né si cancellano vertici, si possono aggiungere o cancellare archi



Grafi dinamici: si possono aggiungere e cancellare sia vertici, sia archi Nel Corso si considerano solo grafi

semi-statici, in cui i vertici vengono cancellati «logicamente», aggiungendo un campo per marcare se è

cancellato o meno.  

Vertici: informazioni rilevanti: interi per identificarli ai fini dell’algoritmo stringhe per identificarli ai fini

 

dell’utente memorizzate in tabelle di simboli: esterne al grafo interne al grafo cui si accede mediante 2

chiavi (intero e stringa) 

possibili implementazioni: tabella di simboli estesa: vettore non ordinato di stringhe: l’indice del vettore

coincide con l’indice del vertice che non è memorizzato esplicitamente. Ricerca inversa con scansione



lineare BST o tabella di hash: l’indice del vertice è memorizzato esplicitamente. STsearchByIndex con



scansione lineare di un vettore di corrispondenza indice-chiave negli esempi: tabella di simboli estesa

interna all’ADT grafo realizzata come vettore non ordinato con indice del vertice coincidente con quello del



vettore nei laboratori: tutte le tipologie. 

Il numero di vertici |V| che serve per inizializzare grafo e tabella di simboli può essere: noto per lettura o



perché compare come intero sulla prima riga del file da cui si legge ignoto, ma sovrastimabile: se il grafo



è dato come elenco di archi con una prima lettura si determina il numero di archi e |V| si sovrastima



come 2 volte il numero di archi, ipotizzando che ogni arco connetta vertici distinti con una seconda

lettura si inseriscono i vertici su cui insistono gli archi nella tabella di simboli, ottenendo il numero di vertici

distinti |V| esatto e la corrispondenza nome del vertice – indice.

 

Formato del file di input: numero V di vertici sulla prima riga V righe con ciascuna il nome di un vertice

 numero indefinito di righe con coppie vertice-vertice per gli archi (con peso se grafo pesato).



Il grafo è un ADT di I classe Gli archi sono definiti con typedef in Graph.h e sono quindi visibili anche al

 

client La tabella di simboli è un ADT di I classe Altre eventuali collezioni di dati sono ADT di I classe

(code, code a priorità, etc.)

Lettura/scrittura di un grafo da/su file

Se il file contiene la lista degli archi in formato «standard» ha senso offrire GRAPHload/ GRAPHstore. In

 

alternativa il client implementa la sua funzione di lettura/scrittura è già noto il numero di vertici |V|

 

lettura dei vertici e inserzione nella tabella di simboli lettura degli archi e inserzione nel grafo Scrittura:



si scandiscono gli archi: con GRAPHedges si accumulano gli archi in un vettore per ciascuno dei vertici

su cui l’arco insiste, tramite la tabella di simboli, dato l’indice si ricava il nome.



Matrice di adiacenza Dato G = (V, E), la matrice di adiacenza è: matrice adj di |V| x |V| elementi 1 se (i, j)

 E  

E adj[i,j] = 0 se (i, j) grafi non orientati: adj simmetrica grafi pesati: adj[i,j]=peso dell’arco (i,j) se

esiste, 0 non è unpeso ammesso

Multigrafo: archi multipli che connettono la stessa coppia di vertici. Si può generare se in fase di inserzione

degli archi non si scartano quelli già esistenti.

Vantaggi/svantaggi (|V|2  

Complessità spaziale S(n) = ) vantaggiosa SOLO per grafi densi No costi aggiuntivi per i pesi di



un grafo pesato Accesso efficiente (O(1)) alla topologia del grafo (adiacenza di 2 vertici).

Lista di adiacenza 

Dato G = (V, E), la lista di adiacenza è: un vettore A di |V| elementi. Il vettore è vantaggioso per via



dell’accesso diretto A[i] contiene il puntatore alla lista dei vertici adiacenti a i.

   

Vantaggi: Grafi non orientati: elementi complessivi nelle liste = 2|E| Grafi orientati: elementi

  vantaggioso

complessivi nelle liste = |E| Complessità spaziale S(n) = O(max(|V|, |E|)) = O(|V+E|)



per grafi sparsiSvantaggi: verifica dell’adiacenza di 2 vertici v e w mediante scansione della lista



diadiacenza di v uso di memoria per i pesi dei grafi pesati.

In generale i grafi sono modelli di situazioni reali e vengono formiti come dati di ingresso. In caso contrario,

si possono generare dei grafi senz alcuna relazione ad un problema specifico.

 

Tecnica 1: archi casuali Vertici come interi tra 0 e |V|-1 generazione di un grafo casuale a partire da E

 

coppie casuali di archi (interi tra 0 e |V|-1) possibili archi ripetuti (multigrafo) e cappi grafo con |V|

vertici e |E| archi (inclusi cappi e archi ripetuti)

 

Tecnica 2: archi con probabilità p si considerano tutti i possibili archi |V|*(|V|-1)/2 tra questi si



selezionano quelli con probabilità p p è calcolato in modo che sia |E| = p*(|V|*(|V|-1)/2) quindi p = 2 *

 

|E| / (|V| * (|V| – 1)) si ottiene un grafo con in media |E| archi non ci sono archi ripetuti.

Cammino semplice

Dato un grafo non orientato G =(V, E) e 2 suoi vertici v e w, esiste un cammino semplice che li connette?



Non è richiesto trovarli tutti. Se il grafo non orientato è connesso il cammino esiste per definizione,

basta trovarne uno qualsiasi senza altri vincoli se non essere semplice. Non serve backtrack. Se il grafo non

il

orientato non è connesso cammino esiste per definizione se i vertici sono nella stessa componente

connessa, altrimenti non esiste. Non serve backtrack.

 vertice t adiacente al vertice corrente v, determinare ricorsivamente se esiste un cammino semplice da t

 

a w array visited[maxV] per marcare i nodi già visitati cammino visualizzato in ordine inverso

complessità T(n) = O(|V+E|)

Il Cammino di Hamilton

Dato un grafo non orientato G =(V, E) e 2 suoi vertici v e w, se esiste uncammino semplice che li connette

visitando ogni vertice una e una solavolta, questo si dice cammino di Hamilton. Se v coincide con w, si parla

di ciclo di Hamilton.  

Cammino di Hamilton tra v e w: vertice t adiacente al vertice corrente v, determinare ricorsivamente

se esiste un cammino semplice da t a w ritorno con successo se e solo se la lunghezza del cammino è |V|-

 

1 set della cella dell’array visited per marcare i nodi già visitati reset della cella dell’array visited



quando ritorna con insuccesso (backtrack) complessità esponenziale!

Il Cammino di Eulero

Dato un grafo non orientato G =(V, E) e 2 suoi vertici v e w, si dicecammino di Eulero un cammino (anche

non semplice) che li connetteattraversando ogni arco una e una sola volta. Se v coincide con w, si parla di

ciclo di Eulero. 

Un grafo non orientato ha un ciclo di Eulero se e solo se è connesso etutti i suoi vertici sono di grado pari

Un grafo non orientato ha un cammino di Eulero se e solo se èconnesso e se esattamente due vertici hanno

grado dispari.

Algoritmi di visita dei grafi 

Visita di un grafo G=(V, E): a partire da un vertice dato, seguendo gli archi con una certastrategia,



elencare i vertici incontrati, eventualmenteaggiungendo altre informazioni. Algoritmi: in profondità



(depth-first search, DFS) in ampiezza (breadth-first search, BFS).

Visita in profondità 

Dato un grafo (connesso o non connesso), a partire da un vertices: visita tutti i vertici del grafo



(raggiungibili da s e non) etichetta ogni vertice v con tempo di scoperta/tempo di fineelaborazione

  

pre[v]/post[v] etichetta ogni arco: grafi orientati: T(tree), B(backward), F(forward), C(cross) grafi non



orientati: T(tree), B(backward) genera una foresta di alberi della visita in profondità, memorizzata in un

vettore st.

Principi base

Profondità: espande l’ultimo vertice scoperto che ha ancora vertici non ancora scoperti adiacenti. Scoperta

di un vertice: prima volta che si incontra nella visita(discesa ricorsiva, visita in pre-order). Completamento:

fine dell’elaborazione del vertice (uscita dallaricorsione, visita in post-order). Scoperta/Completamento:

tempo discreto che avanza mediantecontatore time.

 

I vertici si distinguono (concettualmente) in: bianchi: non ancora scoperti grigi: scoperti, ma non

 

completati neri: scoperti e completati. Per ogni vertice si memorizza: il tempo di scoperta pre[i] e il



tempo di fine elaborazione post[i] il padre nella visita in profondità st[i]

Classificazione degli archi

Grafo orientato:

 T: archi dell'albero della visita in profondità

 B: connettono un vertice j ad un suo antenato i nell’albero: tempo di fine elaborazione di i sarà > tempo

di fine elaborazione di j.

F: connettono un vertice i ad un suo discendente j nel