• Non ci sono risultati.

Istituto di Istruzione Superiore Angioy Informatica GRAFI E ALBERI. Prof. Gianfranco Ciaschetti

N/A
N/A
Protected

Academic year: 2022

Condividi "Istituto di Istruzione Superiore Angioy Informatica GRAFI E ALBERI. Prof. Gianfranco Ciaschetti"

Copied!
10
0
0

Testo completo

(1)

Istituto di Istruzione Superiore “Angioy”

Informatica

GRAFI E ALBERI

Prof. Gianfranco Ciaschetti

1. NOTAZIONE

Nel corso di questa dispensa, saranno riportati - in grassetto le definizioni

- in blu gli esempi

2. INTRODUZIONE

Se possiamo pensare a una lista collegata (linked list) come a una struttura dati (dinamica) lineare, nel senso che possiamo immaginare i suoi elementi collegati uno all’altro lungo una linea,

un grafo è la sua generalizzazione, e permette di collegare un qualsiasi nodo (elemento) a qualsiasi altro. Nella figura che segue, alcuni esempi di grafi:

Matematicamente parlando, un grafo G = (V, E) è definito da un insieme di vertici o nodi V che corrispondono agli elementi che compongono la struttura, e un insieme di archi o spigoli E che collegano coppie di nodi tra loro.

Il nome grafo deriva dal fatto che è possibile disegnare graficamente la sua struttura, tracciando un cerchio per ogni nodo di V e un segmento per ogni arco che unisce due nodi.

Un grafo non è altro che la rappresentazione grafica della relazione che esiste tra gli elementi di un insieme. Ad esempio, se consideriamo la relazione “essere amico di” tra gli elementi dell’insieme

“ragazzi del quartiere”, potremmo ottenere il seguente grafo (è solo un esempio):

Il grafo della figura è definito da G = (V, E) dove V = {Mario, Peppe, Lucy, Franca} mentre E = {(Mario,Peppe), (Mario, Franca), (Mario, Lucy), (Peppe, Franca)}

Dal grafo, possiamo leggere che Mario è amico di Peppe, perché esiste un arco che li collega tra

(2)

Un grafo è non orientato se la relazione rappresentata è simmetrica, ossia le coppie di E non sono ordinate, come nell’esempio precedente. La relazione “essere amico” è una relazione simmetrica, perché ad esempio, se Mario è amico di Lucy allora anche Lucy è amica di Mario.

Se la relazione invece non è simmetrica il grafo è orientato, e gli archi tra i nodi sono rappresentati con delle frecce, come nell’esempio seguente:

Ad esempio, la relazione “ha prestato dei soldi a” è una relazione non simmetrica, e viene

rappresentata in un grafo orientato. La freccia tra Mario e Peppe indica che Mario ha prestato dei soldi a Peppe, ma non è vero il contrario.

In un grafo orientato, l’insieme degli archi viene solitamente indicato con A (arcs) anziché con E (edges).

Ricapitolando, facciamo un esempio di grafo non orientato e uno di grafo orientato:

ESEMPIO 1: grafo non orientato

G = (V, E) con V = {A, B, C, D} ed E = {(A,B), (B,C), (B,D), (C,D)}

ESEMPIO 2: grafo orientato

G = (V, A) con V = {A, B, C, D} e A = {(A,B), (A,C), (B,C), (C,D)}

3. TERMINOLOGIA DEI GRAFI

A. Se (x,y) è un arco di un grafo orientato, si dice che l’arco esce da x ed entra in y Nell’esempio 2, l’arco (A, B) esce da A ed entra in B

B. In un grafo, orientato o no, se (A, B) è un arco, i nodi A e B si dicono adiacenti, e l’arco

(3)

C. In un grafo non orientato, il numero di archi che incidono su un nodo v è detto grado del nodo v ed è indicato con (v).

Nell’esempio 1, il grado di D è (D) = 2.

D. In un grafo orientato, il numero di archi che entrano in un nodo v è detto grado entrante del nodo v ed è indicato con - (v), mentre il numero di archi che escono da un nodo v è detto grado uscente del nodo v ed è indicato con + (v).

Nell’esempio 2, il grado entrante di C è - (C) = 2 mentre il suo grado uscente è + (C) = 1 E. In un grafo, orientato o no, un cammino è una sequenza di vertici a due a due adiacenti tra

loro. La lunghezza di un cammino è data dal numero di nodi che ne fanno parte.

Ovviamente, se un grafo non è orientato, dato un cammino “andata” esiste anche il cammino

“ritorno”. Non è vero, in generale, per un grafo orientato.

Nell’esempio 2, possiamo distinguere tra gli altri il cammino <A, C, D> perché possiamo andare da A a D percorrendo in sequenza gli archi (A, C) e (C, D). Il cammino <A, C, D> ha lunghezza 3 perché coinvolte 3 nodi, il nodo A, il nodo C e il nodo D.

F. La distanza tra due nodi x e y è la lunghezza del cammino più breve tra x e y.

Nell’esempio 2, la distanza tra A e D è il minimo tra la lunghezza del cammino <A, C, D> e quella del cammino <A, B, C, D>, cioè il minimo tra 3 e 4. Quindi, la distanza tra A e D è 3.

G. Un percorso è un cammino che ha tutti archi distinti (ogni arco è attraversato una sola volta).

Nell’esempio 1, esiste il cammino <A, B, C, B, D> mentre esistono solo i percorsi <A, B, D> e <A, B, C, D> per andare da A a D.

H. Un circuito è un cammino che torna al nodo di partenza. Un circuito euleriano è un circuito che attraversa ogni arco una sola volta (ma può toccare più volte lo stesso nodo, e non necessariamente coinvolge tutti gli archi).

Nella figura seguente <A, B, D, C, B, E, A> è un circuito.

I. Un cammino hamiltoniano è un cammino che attraversa tutti i nodi del grafo. Un circuito hamiltoniano è un circuito che attraversa tutti i nodi del grafo.

Nella figura seguente <A, B, D, C, B, E, A> è sia un cammino hamiltoniano che un circuito hamiltoniano.

J. Un ciclo è un circuito che non passa due volte per lo stesso nodo. Un ciclo hamiltoniano è un ciclo che tocca una volta sola tutti i nodi del grafo.

Nella figura seguente, < B, D, C > e <A, B, E> sono cicli, e non ci sono cicli hamiltoniani.

K. Un grafo si dice pesato se ad ogni suo arco viene associata un’informazione, come ad esempio un numero che rappresenta la distanza tra due nodi.

(4)

L. Un grafo non orientato si dice connesso se esiste un cammino da un qualunque nodo verso un altro qualunque nodo del grafo.

Il grafo dell’esempio 1 è connesso

M. Si chiama il grafo di supporto il grafo non orientato che si ottiene da un grafo orientato trasformando ogni freccia (arc) in segmento (edge), cioè considerando la relazione simmetrica.

N. Un grafo orientato è connesso se il suo grafo di supporto è connesso.

Il grafo dell’esempio 2 è connesso

O. Un grafo si dice aciclico se non contiene cicli.

4. ALBERI

Un albero è un grafo connesso aciclico. Un albero è la struttura di base per rappresentare:

• alberi genealogici (nonno, padre, figlio, ecc.)

• alberi di classificazione (genere, specie, sottospecie, ecc.)

• organigrammi (reparto, direttore, capoufficio, impiegato, ecc.)

• alberi di decisione (se faccio questo si apre questo scenario, ecc.) ESEMPIO di albero genealogico:

ESEMPIO di albero di classificazione:

(5)

ESEMPIO di organigramma:

ESEMPIO di albero decisionale:

5. TERMINOLOGIA DEGLI ALBERI

In un albero gli archi sono chiamati rami. Gli alberi possono essere orientati oppure no, ma solitamente si intendono orientati.

Un albero può essere radicato o libero. Nel primo caso, c’è un nodo (o vertice) chiamato radice che ha solo archi uscenti, e ci sono altri nodi chiamati foglie che hanno solo archi entranti; tutti gli altri nodi sono chiamati interni. Nel secondo caso, l’albero si intende non orientato e ogni nodo dell’albero può avere il ruolo di radice (si pensi di “appendere” l’albero tirando verso l’alto il nodo scelto)

Seguendo la terminologia di un albero genealogico, in un albero si possono distinguere:

• padre (o genitore) e figlio: i nodi x e y di un arco orientato (x, y)

• fratello: sono fratelli due figli dello stesso padre

• antenato e discendente: un nodo dal quale è possibile trovare un cammino verso un altro nodo

Nell’albero del seguente esempio

(6)

• i nodi 2 (quello in basso), 5 (quello in basso), 11, 4 sono le foglie, perché non hanno archi entranti

• i nodi 7, 6, 5 (quello in alto), 9 sono interni

• il nodo 7 è il padre del nodo 6, che è il figlio di 7

• il nodo 7 è un antenato del nodo 11; il nodo 4 è un discendente del nodo 2 (quello in alto)

• i nodi 2 (quello in basso) e 6 sono fratelli, perché sono entrambi figli di 7

Il livello di un nodo è la lunghezza del percorso tra la radice e quel nodo.

Nell’esempio di sopra,

• la radice è a livello 0

• i nodi 7 e 5 (quello in alto) sono a livello 1

• i nodi 2 (quello in basso), 6 e 9 sono a livello 2

• i nodi 5 (quello in basso), 11 e 4 sono a livello 3.

Il livello di un nodo è anche definito ricorsivamente come il livello del padre + 1.

La profondità di un nodo x è la lunghezza del cammino dalla radice a x. Nell’esempio di sopra, la profondità del nodo 9 è 3, in virtù del cammino <2, 5, 9>. Quindi il nodo 9 è a livello 2 e ha profondità 3.

Un sottoalbero con radice x è l’albero formato da tutti i discendenti del nodo x. Nell’esempio di sopra, questo è il sottoalbero con radice 7

Considerando il nodo 7, sempre nello stesso esempio, questi sono il suo sottoalbero sinistro e il suo sottoalbero destro, disegnati rispettivamente in rosso e in blu

Si dice che un albero è n-ario se ogni nodo ha al più n figli. Ad esempio, un albero binario è un albero in cui ogni nodo ha al massimo due figli, in un albero ternario ogni nodo ha al massimo tre figli, ecc.

Un albero è completo se ogni nodo ha il massimo dei suoi figli. Nell’esempio che segue, un albero binario completo (a sinistra) e un albero binario incompleto (a destra).

(7)

6. MEMORIZZAZIONE DI UN GRAFO

Ci sono diversi modi possibili per memorizzare un grafo. I più usati sono:

Matrice di adiacenza

Matrice di incidenza

Lista di adiacenza

6.1 Matrice di adiacenza

Dato un grafo non orientato G = (V, E), dove V ha n nodi e E ha m archi, la matrice di adiacenza di G è la matrice di dimensioni n x n il cui elemento di riga i e colonna j ha il valore:

• 1 se esiste l’arco (i, j)

• 0 se non esiste l’arco (i ,j)

ESEMPIO: La matrice di adiacenza del grafo

è la matrice

La matrice di adiacenza di un grafo non orientato è sempre simmetrica (speculare rispetto alla diagonale principale), essendo simmetrica la relazione tra gli elementi. Nella matrice, risultano esserci 2m elementi pari a 1 (due per ogni arco), e a ogni elemento 1 in posizione (i, j) corrisponde, per simmetria, un elemento 1 in posizione (j, i).

Se il grafo è orientato, invece, la matrice di adiacenza non è simmetrica ed esiste un 1 in posizione (i, j) solo se c’è un arco orientato dal nodo i al nodo j (ma non viceversa).

ESEMPIO: La matrice di adiacenza del grafo

è la matrice

Nel caso di un grafo orientato con n nodi e m archi, il numeri di elementi della matrice pari a 1 è m.

6.1 Matrice di incidenza

Dato un grafo non orientato G = (V, E), dove V ha n nodi e E ha m archi, la matrice di incidenza di G è la matrice di dimensioni n x m in cui ogni colonna ha due soli elementi pari a 1, gli estremi dell’arco, e tutti gli altri pari a 0.

ESEMPIO: La matrice di incidenza del grafo

è la matrice

Se il grafo è orientato, come prima, ogni colonna ha due valori non nulli, ma stavolta abbiamo:

• 1 se l’arco esce dal nodo

• -1 se l’arco entra nel nodo

(8)

ESEMPIO: La matrice di incidenza del grafo

è la matrice

6.3 Lista di adiacenza

Una lista di adiacenza è una struttura dinamica che fa uso dell’ADT Lista Collegata (linked list) per memorizzare le adiacenze tra i nodi. I diversi puntatori per i diversi nodi sono solitamente memorizzati in un vettore di puntatori.

ESEMPIO: Dato il grafo

la sua lista di adiacenza è

Sebbene questo tipo di memorizzazione risulti estremamente più complessa da gestire rispetto alle matrici, il suo vantaggio è evidente allorché si vogliano memorizzare grafi di grandi dimensioni. In questo modo si evita di occupare inutilmente memoria con un’allocazione statica.

Per alcuni particolari problemi di ottimizzazione, come vedremo, esistono strutture dati più efficienti che possono migliorare la complessità computazionale dell’algoritmo risolutivo.

7. MEMORIZZAZIONE DI UN ALBERO

Un albero, essendo un caso particolare di grafo, può essere memorizzato usando uno qualsiasi tra i possibili modi di memorizzare un grafo. Però possiamo sfruttare la sua semplicità (è connesso e non ha cicli) rispetto a un qualsiasi grafo generico per trovare modi più efficienti di memorizzarlo.

In genere, per gli alberi, le strutture statiche come le matrici sono troppo rigide per permettere una gestione snella e veloce per le operazioni di inserimento, ricerca, modifica, cancellazione, ecc.

Si preferisce allora memorizzare l’albero utilizzando strutture dinamiche con puntatori, come:

• Liste di figli

• Puntatori ai figli (albero collegato in modo gerarchico)

• Puntatori a figli e al prossimo fratello (albero collegato in modo gerarchico e per livelli)

• Puntatori a figli e al padre (albero doppiamente collegato)

• Vettore heap (alberi binari)

NOTA: in grassetto la struttura dati che abbiamo utilizzato per l’ADT Albero Binario.

7.1 Liste di figli

(9)

È evidente che per alberi semplici, come gli alberi binari (con al massimo due figli per nodo) questo non è il modo più efficiente, mentre risulta di facile utilizzo per alberi n-ari.

7.1 Puntatori ai figli

Ogni nodo contiene, oltre alla sua informazione, i puntatori ai propri figli. Questo tipo di memorizzazione è estremamente utile per gli alberi binari, in quanto basta memorizzare solo i puntatori al figlio sinistro e al figlio destro per ogni nodo.

struct nodo { char info;

nodo *left;

nodo *right;

};

Nella prossima dispensa tratteremo più in dettaglio gli alberi binari e questo tipo di rappresentazione, che è la più usata in quanto rappresenta un ottimo compromesso tra efficienza e semplicità.

7.1 Puntatori ai figli e al prossimo fratello

Ogni nodo contiene, oltre alla sua informazione, i puntatori ai propri figli e al fratello immediatamente a destra. Questa rappresentazione permette una scansione veloce dell’albero “per livelli”, potendo esplorare rapidamente uno stesso livello seguendo i link orizzontali, senza dover salire e scendere continuamente.

7.1 Puntatori ai figli e al padre

Come nelle liste doppiamente collegate, un puntatore che permette di risalire l’albero dal figlio al padre, oltre che solo poter scendere dal padre al figlio, consente di esplorare più rapidamente la struttura dati, a scapito però di un aumento di complessità nella gestione delle informazioni degli indirizzi, cioè i puntatori.

(10)

7.1 Vettore heap

Si possono memorizzare le informazioni di un albero binario in un vettore nel seguente modo:

• in posizione 0 la radice dell’albero

• in posizione 1 il figlio sinistro dell’elemento in posizione 0

• in posizione 2 il figlio destro dell’elemento in posizione 0

• in posizione 3 il figlio sinistro dell’elemento in posizione 1

• in posizione 4 il figlio destro dell’elemento in posizione 1

• ecc.

In generale, troviamo i figli dell’elemento in posizione i nelle posizioni 2i + 1 e 2i + 2.

ESEMPIO: l’albero della seguente figura può essere rappresentato come

Questa rappresentazione funziona molto bene con gli alberi completi, ma spreca troppo spazio di memoria nel caso di alberi incompleti, come è evidente dall’esempio di sopra.

Riferimenti

Documenti correlati

Soluzione : dalle matrici di adiacenza si vede che il vertice corrispondente alla settima colonna (o riga) in G’ ha grado 4, mentre G non ha vertici di grado 4. Ciò implica che G e

 Se un thread, che possiede alcune risorse, richiede un’altra risorsa, che non gli può essere allocata immediatamente, allora rilascia tutte le risorse possedute.  Le

Grafo particolare è quello &#34;euleriano&#34;, dal matematico Eulero, che nel 1736 lo utilizzò per risolvere il problema dei ponti di Königsberg: un cammino o percorso è detto di

Se valesse anche nel senso opposto esisterebbe un algoritmo estremamente semplice (e polinomiale) per colorare in modo minimo un grafo (si colora arbitrariamente e si vede se il

Per ogni x `e qundi definita una clique e per ogni clique esiste un x che la definisce.. Quindi tale colore

• La visita in ampiezza fa uso di una coda per memorizzare tutti i nodi adiacenti al nodo v visitato, che portano ad un nodo non marcato come scoperto. • I nodi raggiungibili

‰ eventi causalmente legati nello spazio e/o nel tempo (inizio/fine di un’operazione, un trasporto, una giacenza in magazzino)... Corso di Ricerca

[r]