Grafi Algoritmi e Strutture Dati. Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Algoritmi e...

Grafi

Algoritmi e Strutture Dati

Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano

2

Algoritmi e strutture dati 2/ed

Copyright © 2008 - The McGraw - Hill Companies, srl

Definizione

Un grafo G=(V,E) consiste in:

- un insieme V di vertici o nodi, (vertex)

- un insieme E di coppie di vertici, detti archi o spigoli (edge): ogni arco connette due vertici

Esempio 1: V={persone che vivono in Italia}, E={coppie di persone che si sono strette la mano}

Esempio 2: V={persone che vivono in Italia}, E={(x,y) tale che x ha inviato una mail a y}


3



Terminologia (1/10)Se esiste una relazione simmetrica grafo non orientato

Accade quando la relazione tra una coppia di vertici è simmetrica; vedi esempio 1.


4



Terminologia (2/10)Se esiste una relazione “orientata” grafo orientato o diretto

Accade quando la relazione tra una coppia di vertici è orientata; vedi esempio 2.


5



Terminologia (3/10)• Un grafo verrà denotato con G=(V,E), dove E VxV

• n = numero di vertici (nodi)

• m = numero di spigoli (archi)

• Se x e y sono due vertici di G, allora (x, y) indicherà l’arco

• (x, y) si dice incidente a x e a y

• Se il Grafo è Orientato, si dice che (x, y) esce da x e entra nel vertice y

• Se il Grafo NON è Orientato, si dice che x ed y sono adiacenti


6



Terminologia (4/10)• Grado di un vertice v in un Grafo NON orientato è dato dal numero di archi incidenti su v.• Si indica con (v)• Esempio: H ha grado 4: (H)=4• La somma di tutti i gradi dei vertici è data da:

∑ (v)=2mvG


7



Terminologia (5/10)• Grado di un vertice v in un Grafo Orientato• Si ha il grado in uscita di v e il grado in entrata di v

• Si indicano con in(v) e out(v)

• Il Grado di v è in(v) + out(v)

• Esempio: E ha in(E)=3 e out(E)=4, (E)=7

∑ (v)=2mvG

• Si ha che ∑ in(v)=vG

∑ out(v)=mvG


8



Terminologia (6/10)

• Si dice che il cammino è semplice se tutti i vertici sono distinti• Esempio: il cammino tra A e L esiste, contiene (A, B, E, I, L), e

gli archi (A,B)-(B,E)-(E,I)-(I,L), ha lunghezza 4, ed è semplice

• Un Cammino in G dal vertice x al vertice y è una sequenza di vertici (v0, v1, v2, ……, vk) con v0=x e vk=y, tale che: (vi-1, vi) appartiene a G per qualunque 1≤i≤k

• Il cammino ha lunghezza k (numero di vertex – 1)• Esempio:< L , I , E, C, B, A > è un cammino di lunghezza 5


9



Terminologia (7/10)

• Esempio: il cammino tra A e L esiste, contiene (A, B, C, E, F, H, E, I, L), e gli archi (A,B)-(B,C)-(C,E)-(E,F)-(F,H)-(H,E)-(E,I)-(I,L), ha lunghezza 8, e NON è semplice (passa due volte da E)


10



Terminologia (8/10)• Se esiste un cammino da un vertice x ad un vertice y, si dice che y è raggiungibile da x, ossia che y è discendente di x e che x è un antenato di y

• Un cammino (v0, v1, v2, ……, vk) tale che v0=vk e k≥1 si dice un ciclo

• Un ciclo è semplice se i vertici sono distinti• Un Grafo Diretto Aciclico è un grafo orientato che non contiene cicli


11



Terminologia (9/10)

(B,C,E,D,B) è un ciclo semplice

(E,F,H,E,I,G,E) non è semplice


12



Terminologia (10/10)• Un Grafo NON orientato G=(V,E) si dice connesso se esiste un cammino tra ogni coppia di vertici in G

• Per essere connesso un Grafo deve avere almeno (n-1) archi

• Un Grafo Orientato si dice fortemente connesso se esiste un cammino tra ogni coppia di vertici


13



Operazioni sui Grafi


14



Alcune Operazioni• unsigned int grado(vertex v);

– numero di archi incidenti su v

• edge[] archiIncidenti(vertex v);– lista/vettore di archi incidenti su v

• boolean sonoAdiacenti(vertex u, vertex v);– TRUE se esiste l’arco (u,v)

• void aggiungiVertice(vertex v);– inserisce un nuovo vertice v

• void aggiungiArco(vertex u, vertex v);– inserisce un nuovo arco tra i vertici u e v

• void rimuoviVertice(vertex v);• void rimuoviArco(edge e);


15



Strutture dati

per rappresentare grafi


16



Lista di ArchiPiù struttura dati per memorizzare vertex


17



Liste di Adiacenza


18



Liste di Incidenza


19



Matrice di Adiacenza


20



Matrice di Incidenza


21



Implementazione in C

di un Grafo con Liste di Adiacenza


22



v next

nv

vect

vpresent

adjv

presentadjv

presentadjv

presentadjv

presentadj

v next v next

v next v next

v next

v next v next

graph

1 2 3

0

1

2

3

4

0 3

0

1 0

0 1

3 2

4

Liste di Adiacenza


23



Liste di Adiacenza#define EMPTYGRAPH NULL

typedef int boolean;

typedef unsigned int vertex;

typedef vertex edge[2];

typedef struct node_edge{

vertex v;

struct node_edge *next;

} node_edge;

typedef struct node_vertex{

vertex v;

boolean present;

node_edge *adj; /* lista di adiacenze del vertex v*/

} node_vertex;

typedef struct node_graph {

unsigned int nv; /* numero massimo di vertici del grafo */

node_vertex *vect; /* vettore con le liste delle adiacenze */

} * graph ;


24



Liste di Adiacenzagraph MakeNULLGraph(unsigned int dim) {

graph G;

unsigned int i;

if (dim>0) {

G = (graph)malloc(sizeof(struct node_graph));

if (!G) printf("\nERRORE: impossibile allocare memoria per il grafo\n");

else {

G->vect=(node_vertex *)malloc(dim*sizeof(node_vertex));

if (!G->vect) {

printf("ERRORE: impossibile allocare memoria ");

printf("per il vettore di liste\n");

free(G);

G=NULL;

} else {

G->nv = dim;

for (i=0; i<dim; i++){

G->vect[i].v=i;

G->vect[i].present=0;

G->vect[i].adj=EMPTYGRAPH;

}

}

}

} else G=NULL;

return(G);

}


25



Liste di Adiacenzavoid AddEdgeGraph(graph G, vertex u, vertex v) {

node_edge *new;

if (G && u<G->nv && v<G->nv ) {

if (G->vect[u].present && G->vect[v].present) {

new = (node_edge*)malloc(sizeof(node_edge));

if (new==NULL) printf("\nERRORE: impossibile allocare memoria \n");

else {

new->v=v;

new->next=G->vect[u].adj;

G->vect[u].adj = new;

}

}

}

}


26



Liste di Adiacenzavoid RemoveEdgeGraph(graph G, edge e) {

node_edge *prev; /* l'arco precedente a quello da togliere nella lista */

node_edge *p; /* l'arco da togliere dalla lista */

vertex u=e[0], v=e[1];

if (G && u<G->nv && v<G->nv) {

if (G->vect[u].present && G->vect[v].present) {

/*eliminare l'arco da u a v*/

p=G->vect[u].adj;

if (p->v == v) {

G->vect[u].adj = p->next;

free(p);

} else {

prev=p;

while (prev->next->v != v && prev->next->next!=EMPTYGRAPH)

prev=prev->next;

if (prev->next->next!=EMPTYGRAPH) {

p=prev->next;

prev->next=p->next;

free(p);

}

}


27



Liste di Adiacenza /*eliminare l'arco da v a u*/

p=G->vect[v].adj;

if (p->v == u) {

G->vect[v].adj = p->next;

free(p);

} else {

prev=p;

while (prev->next->v != u && prev->next->next!=EMPTYGRAPH)

prev=prev->next;

if (prev->next->next!=EMPTYGRAPH) {

p=prev->next;

prev->next=p->next;

free(p);

}

}

}

}

}


28



Liste di Adiacenzavoid AddVertexGraph(graph G, vertex v) {

node_vertex *p;

unsigned int dim;

if (G!=NULL && !G->vect[v].present)

if(v<G->nv)

G->vect[v].present=1;

else

if (v==G->nv) {

dim=G->nv+1;

p=(node_vertex *)realloc(G->vect,dim*sizeof(node_vertex));

if (!p) printf("ERRORE: impossibile reallocare memoria \n");

else {

G->vect=p;

G->nv=dim;

G->vect[v].v=v;

G->vect[v].present=1;

G->vect[v].adj=EMPTYGRAPH;

}

}

}


29



Liste di Adiacenzavoid RemoveVertexGraph(graph G, vertex v) {

node_edge *prev; /* l'arco precedente a quello da togliere nella lista */

node_edge *p; /* l'arco da togliere dalla lista */

unsigned int i;

if (G && v<G->nv &&G->vect[v].present)

for (i=0; i<G->nv; i++) {

if (G->vect[i].v==v){

p=G->vect[i].adj;

while (p!=EMPTYGRAPH) {

prev=p;

p=p->next;

free(prev);

}

G->vect[i].adj=EMPTYGRAPH;

G->vect[i].present=0;

} else if (G->vect[i].present && G->vect[i].adj) {

p=G->vect[i].adj;

if (p->v == v) G->vect[i].adj = p->next;

else {

else {

prev=p;

while (prev->next->v != v &&

prev->next->next!=EMPTYGRAPH)

prev=prev->next;

if (prev->next->v==v) {

p=prev->next;

prev->next=p->next;

}

}

free(p);

}

}

}


30



Riepilogo

• Concetto di grafo e terminologia

• Diverse strutture dati per rappresentare grafi nella memoria di un calcolatore

• L’utilizzo di una particolare rappresentazione può avere un impatto notevole sui tempi di esecuzione di un algoritmo su grafi

Grafi Algoritmi e Strutture Dati. Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Algoritmi e...

Documents

Transcript of Grafi Algoritmi e Strutture Dati. Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Algoritmi e...