Grafi: Rappresentazioni e Visite -...

Grafi: Rappresentazioni e Visite

Laboratorio di Algoritmi e Strutture Dati

Massimo Benerecetti

Ci sono due tipi di rappresentazione standard

per grafi in un computer:

• Rappresentazione a matrice di adiacenza

• Rappresentazione a liste di adiacenza

Rappresentazone di grafi

A

BC

F

DE

A B C D E F

A

B

C

D

E

F

0 1 0 1 0 0

0 0 1 0 0 0

0 0 0 0 1 0

1 0 1 0 0 0

0 0 0 1 0 0

0 0 0 0 0 0

Rappresentazone di grafi orientati

Rappresentazione a matrice di adiacenza questa

volta per rapresentare un grafo orientato.

Spazio: |V|2

A

BC

F

DE

A

B

C

D

E

F

B D

A

D

E

C


Rappresentazione a liste di adiacenza questa volta

per rapresentare un grafo orientato.

C

Rappresentazione a liste di adiacenza questa volta

per rapresentare un grafo orientato.

A

BC

F

DE

A

B

C

D

E

F

B D

D

E

C

Spazio: a |V| + b |E|

a b


A C

Rappresentazone di grafi

• Matrice di adiacenza

• Spazio richiesto O(|V|2)

• Verificare se i vertici u e v sono adiacenti richiede tempo O(1).

• Molti 0 nel caso di grafi sparsi

• Liste di adiacenza

• Spazio richiesto O(|E|+|V|)

• Verificare se i vertici u e v sono adiacenti richiede tempo O(|V|).

Visita in ampiezza BFS

• Tecnica di visita di un grafo

• È una variazione della visita in ampiezza per alberi binari

• Viene mantenuta una coda di vertici da visitare, inizialmentecontenete solo la sorgente della visita;

• La visita di s procede come segue:

1. Ad ogni iterazione viene prelevato un vertice s dalla coda;

2. Si accodano tutti i vertici adiacenti (scoperti) ad s;

3. Si termina la visita del vertice s e si ritorna al passo 1 per procedere con l’iterazione successiva.

• La visita termina quando la coda è vuota.

• Bisogna evitare di rivisitare vertici già visitati

• Attenzione alla presenza di cicli.

Algoritmo BFS

• Per distinguere tra i vertici non visitati, quelli sciperti, equelli visitati coloriamo:• ogni vertice scoperto di grigio

• ogni vertice non scoperto di bianco

• ogni vertice visitato di nero

• Vengono accodati solo i vertici che non sono ancora statiscoperti (cioè bianchi)

• I vertici in coda saranno i vertici scoperti e non ancoravisitati (cioè grigi)

• I vertici già scoperti o visitati non vengono più riconsiderati.

Algoritmo BFSBSF(G:grafo, s:vertice)for each vertice u V(G) - {s}

do colore[u] = Bianco

pred[u] = Nil

colore[s] = Grigio

pred[s] = Nil

Coda = {s}

while Coda

do u = Testa[Coda]

for each v Adiac(u)

do if colore[v] = Bianco

then colore[v] = Grigio

pred[v] = u

Accoda(Coda,v)

Decoda(Coda)

colore[u] = Nero

Inizializzazione

Accodamento dei soli

nodi non visitati

Algoritmo BFS: complessitàBSF(G:grafo, s:vertice)for each vertice u V(G) - {s}


pred[u] = Nil

colore[s] = Grigio

pred[s] = Nil

Coda = {s}

while Coda

do u = Testa[Coda]

for each v Adiac(u)



pred[v] = u

Accoda(Coda,v)

Decoda(Coda)

colore[u] = Nero

O(|V|)

O(|Eu|)Eu = lunghezza della

lista di adiacenza

di u

BSF(G:grafo, s:vertice)for each vertice u V(G) - {s}


pred[u] = Nil

colore[s] = Grigio

pred[s] = Nil

Coda = {s}

while Coda

do u = Testa[Coda]

for each v Adiac(u)



pred[v] = u

Accoda(Coda,v)

Decoda(Coda)

colore[u] = Nero

O(|V|)

O(|E|)E = dimensione

delle liste di

adiacenza.

Numero di archi

Algoritmo BFS: complessità

Algoritmo BFS: complessità

L’algoritmo di visita in Breadth-First impiega tempoproporzionale alla somma del numero di vertici e delnumero di archi (dimensione delle liste di adiacenza).

T(V,E) = O(|V|+|E|)

Stampa del percorso minimo

Percorso-minimo(G:grafo,s,v:vertice)

BFS(G,s,pred[])

Stampa-percorso(G,s,v,pred)

Stampa-percorso(G:grafo,s,v:vertice,pred[]:array)

if v = s

then stampa s

else if pred[v] = NIL

then stampa “non esiste alcun cammino tra

s e v”

else

Stampa-percorso(G,s,pred[v],pred)

print v

Visita in Profondità (DFS)• Tecnica di visita di un grafo

• È una variazione della visita in profondità per alberi binari

• La visita di s procede come segue:• Si visitano ricorsivamente tutti i vertici adiacenti ad s;

• Si termina la visita del vertice s e si ritorna.

• Bisogna evitare di rivisitare vertici già visitati• Bisogna anche qui evitare i cicli

• Nuovamente, quando un vertice è stato scoperto e (poi)visitato viene marcato opportunamente (colorandolo)

Algoritmo DFS

Manterremo traccia del momento (tempo) in cui

ogni vertice v viene scoperto e del momento in

cui viene visitato (o terminato).

Useremo inoltre due array d[v] e f[v] che

registrano il momento in cui v verrà scoperto e

quello in cui verrà visitato.

La variabile globale tempo serve a registrare il

passaggio del tempo.

Il tempo viene usato per studiare le proprietà di DFS

DFS: intuizioniI passi dell’algoritmo DFS

si parte da un vertice non visitato s e lo si visita

si sceglie un vertice non scoperto adiacente ad s.

da s si attraversa quindi un percorso di vertici adiacenti(visitandoli) finché possibile (DFS-Visita):

• cioè finché non si incontra un vertice già scoperto/visitsto

appena si resta “bloccati” (tutti gli archi da un verticesono stati scoperti), si torna indietro (backtracking) di unpasso (vertice) nel percorso attraversato (aggiornando ilvertice s al vertice corrente dopo il passo all’indietro).

si ripete il processo ripartendo dal passo.

DFS: DFS-Visita

DFS-Visita: algoritmo principale della DFS

sia dato un vertice u di colore bianco in ingresso

visitare il vertice u: colorare u di grigio e assegnare il

tempo di inizio visita d[u]

visitare in DFS ricorsivamente ogni vertice bianco

adiacente ad u con DFS-Visita

colorare di nero u e assegnare il tempo di fine visita

f[u].Chiamata ricorsiva

ba

c

e f

d

b

ac

e

f

d

b acef d

ba

c

e f

d

Albero di copertura Depth-first

Archi dell’alberoArchi di ritorno

Algoritmo DFSDSF(G:grafo)

for each vertice u V


pred[u] = NIL

tempo = 0

DSF-Visita(G:grafo,u:vertice)

colore[u] = Grigio

d[u] = tempo = tempo + 1

for each vertice v Adiac[u]


then pred[v] = u

DFS-Visit(G,v)

colore[u] = Nero

f[u] = tempo = tempo + 1

Abbreviazione per:tempo=tempo+1

d[u]=tempo

Abbreviazione per:tempo=tempo+1

f[u]=tempo

Inizializzazione del grafo e della variabiletempo


do if colore[u] = Bianco

then DFS-Visita(G,u)

DFS: simulazone

ba

c

e f

d

DSF(G:grafo)



pred[u] = NIL

tempo = 0





colore[u] = Grigio




then pred[v] = u

DFS-Visit(G,v)

colore[u] = Nero


Alberi di copertura multipli

ab

c de

f

g

DSF(G:grafo)



pred[u] = NIL

tempo = 0





colore[u] = Grigio




then pred[v] = u

DFS-Visit(G,v)

colore[u] = Nero


a

cd

ef

b

g


colore[u] = Grigio




then pred[v] = u

DFS-Visit(G,v)

colore[u] = Nero


Tempo di esecuzione di DFSDSF(G:grafo)



pred[u] = NIL

tempo = 0




(|V|)

(|V|)

Chiamata solo per vertici non ancora visitati

|V|volte

( |Eu| )

Tempo di esecuzione di DFSDSF(G:grafo)



pred[u] = NIL

tempo = 0




(|V|+ |E| )

Libreria per gestione grafi

Le operazioni da implementare sono: • Creazione di grafo casuale con n nodi (arco tra ogni coppia di vertici con

probabilità p[0,1], con p numero razionale);• Conversione tre le due le rappresentazioni di grafo (liste ↔ matrice) • Inserimento di un nuovo vertice; • Inserimento di un nuovo arco; • Cancellazione di un arco o di un vertice; • Calcolo del grafo trasposto; • Visita in ampiezza di un grafo; • Visita in profondità di un grafo; • Stampa di un percorso tra due vertici (minimo o non); • Verifica della aciclicità di un grafo;• Lettura/scrittura di un grafo da file.

BNF - Backus-Naur Form

Backus-Naur Form (BNF) : notazione standard utilizzata per ladefinizione di grammatiche di linguaggi formali.

Specifica le regole di produzione delle frasi del linguaggio.

Distingue tre insiemi di simboli:• simboli non terminali (<nome>, <cognome>, …)• simboli terminali (a, marco, …) [oppure ‘a’, ‘marco’, …]• simboli speciali ( |, ::= )

Esempio:

<number> ::= <digit> | <digit> <number>

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

BNF - EsempiAlcuni esempi:

<number> ::= <digit> | <digit> <number>

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<real_number> ::= <number> '.' <number>

<log_expr> ::= <log_expr> <bin_op> <log_expr> |

'' <log_expr> | <simple_exp>

<bin_op> ::= '' | ''

<simple_exp> ::= 'A' | 'B' | 'C' | . . .

EBNF - Extended Backus-Naur Form

Extended Backus-Naur Form (EBNF) : estende la notazioneBackus-Naur Form (BNF) con simboli aggiuntivi per la definizionidi parti opzionali o ricorrenti:

• parentesi tonde [raggruppamento]• parentesi quadre [componenti opzionali]• parentesi graffe [ripetizioni]

La sintassi dei linguaggi di programmazione (C, C++, Pascal, …)viene tipicamente espressa tramite grammatiche EBNF.

Facilita la definizione di algoritmi di “parsing” per il linguaggi.

EBNF - parentesi tonde [raggruppamento]

Parentesi tonde ( ) : indicano una singola occorrenza, tipicamentesi usano per alternative annidate.

Esempio:

<N>::= (a | b) c produce stringhe della forma ac o bc

Equivale alla grammatica

<N> ::= <M> c<M> ::= a | b

EBNF - parentesi quadre [opzione]

Parentesi quadre [ ] : indicano una componente opzionale, 0 o 1occorrenze.

Esempio:

<N> ::= [a] c produce stringhe della forma c oppure ac

– equivale alla grammatica: <N> ::= <M> c<M> ::= ε | a [ε indica la stringa vuota]

Possono contenere alternative annidate

<N> ::= [a | b] c produce stringhe della forma c o ac o bc

– equivale alla grammatica: <N> ::= <M> c<M>::= ε | a | b

EBNF - parentesi graffe [ripetizione]

Parentesi graffe { } : indicano una ripetizione di 0 o 1 o più occorrenze.

Esempio:

<N> ::= {a} c produce stringhe della forma c, ac, aac, …, aaaaac, …

– equivale alla grammatica: <N> ::= <M> c<M> ::= ε | a <M>

Possono contenere alternative annidate

<N> ::= {a | b} c produce stringhe della forma c, ac, bc, abc, bac, …

– equivale alla grammatica: <N> ::= <M> c

<M>::= ε | a <M> | b <M>

Parser Ricorsivo

Analizzatore sintattico di tipo top-down, tipicamente di tipo LL(1).

Relativamente semplice da realizzare, data una grammatica in formaEBNF opportuna (i.e., senza ambiguità).

Segue la struttura ricorsiva della grammatica:

• una funzione per ogni simbolo non-terminale• una o più funzioni per il riconoscimento dei simboli terminali

La funzione per un non-terminale <X> richiama le funzioni per isimboli terminali e non-terminali, seguendo la regola grammaticaledel non-terminal <X> stesso.

Parser Ricorsivo: Esempio

Data la regola EBNF <X> ::= '(' <T> ',' <T> ') ‘ lo schema dellafunzione per <X> è

void parse_X(…)

{ // fn. per il non-terminale <X>

match(‘(’); // lettura del terminale ‘)’

parse_T(…); // chiamata alla fn. per <T>

match(‘,’);

parse_T(…);

match(‘)’);

}

EBNF per file di specifica grafiIl file che contiene la descrizione di un grafo deve essere conforme alla seguentegrammatica in formato Extended-BNF (EBNF):

I simboli tra virgolette identificano i simboli terminali della grammatica. Ad es. “(”indica il simbolo terminale di aperta parentesi (nel file le virgolette non compaiono).• I simboli tra parentesi angolari (ad es., <nodo>) identificano i simboli non

terminali della grammatica.• Le parentesi graffe indicano zero o più ripetizioni del simbolo tra esse contenuto.

<grafo> ::= '(' <numero_nodi> ')' <adiacenze> '.'

<adiacenze> ::= { <adiacenza_nodo> }

<adiacenza_nodo> ::= <nodo> ['->' <lista_archi> ] ';'

<lista_archi> ::= <arco> { ',' <arco> }

<arco> ::= ['(' <peso> ')' ] <nodo>

<nodo> ::= identificativo

<peso> ::= numero_reale_con_segno

<numero_nodi> ::= numero_intero_senza_segno

Libreria per gestione grafi

Definire in linguaggio C una libreria per la gestione di grafi. • Implementazione di grafi con le due rappresentazioni

standard: • Rappresentazione tramite matrice di adiacenza; • Rappresentazione tramite liste di adiacenza.

• Prevedere la possibilità di associare pesi (numeri reali) agli archi.

Variabile di tipo puntatorea (descrittore di) file.

Funzioni standard gestione file#include <stdio.h>

FILE *stream fopen(const char *name, char *mode); int fclose(FILE *stream);

#include <stdio.h>

int main(void) {FILE *fd = fopen("myfile.txt","r");char y[5] = "abcd";

if (fd) {fprintf(fd,"%s\n", y); /* inserisce nel file la stringa contenuta in y */fclose(fd);

}}

Funzioni di apertura e chiusura di file.

Funzioni standard gestione file#include <stdio.h>

FILE *stream fopen(const char *name, char *mode); int fclose(FILE *stream);

#include <stdio.h>



}}

Modalità di apertura file

I possibili valori per il mode in fopen("myfile.txt", mode) sono:

r Apre il file per la lettura (read-only).

w Apre il file per la scrittura (write-only). Il file viene creato se non esiste.

r+ Apre il file per lettura e scrittura. Il file deve già esistere.

w+ Apre il file per scrittura e lettura. Il file viene creato se non esiste.

a Apre il file per aggiornamento (append). È come aprire il file per la scrittura, ma ci siposiziona alla fine del file per aggiungere dati alla fine. Il file viene creato se non esiste.

a+ O Apre il file per lettura e aggiornamento. Il file viene creato se non esiste.

Funzioni standard di output su file#include <stdio.h>

int fputc(char c, FILE *stream);int fprintf(FILE *stream, const char *format, ...);

#include <stdio.h>



}}

Funzioni di scritture su file.

Funzioni standard di output su file#include <stdio.h>

int fputc(char c, FILE *stream);int fprintf(FILE *stream, const char *format, ...);

#include <stdio.h>


if (fd) {for (int i=0; i<4; i++)

fputc(y[i], fd); /* inserisce nel file la stringa contenuta in y */fclose(fd);

}}


Funzioni standard di input da file

#include <stdio.h>

int fgetc(FILE *stream);

#include <stdio.h>

int main(void) {char x[10];

FILE *fd = fopen("myfile.txt","r");if (fd) {for(i = 0; i < 10; i++)

x[i] = fgetc(); /* Legge 10 caratteri che vengono inseriti nell’array x */ fclose(fd);}

}


Funzioni standard di spostamento in file#include <stdio.h>

int fseek(FILE *stream, long offset, int whence);

long ftell(FILE *stream);

void rewind(FILE *stream);

int fgetpos(FILE *stream, fpos_t *pos);

int fsetpos(FILE *stream, fpos_t *pos);

• fseek: sposta l’indicatore di posizione nel file alla posizione whence + offset

whence può valere SEEK_SET, SEEK_CUR o SEEK_END per specificare il riferimento all'inizio, alla posizione corrente o alla fine file.

• ftell: ritorna il valore corrente dell'indicatore di posizione del file stream.

• rewind: imposta l'indicatore di posizione del file stream all'inizio file.

• fgetpos: scrive in *pos il valore corrente della posizione del file.

• fsetpos: riposiziona il file associato a stream nella posizione indicata in *pos.

Grafi: Rappresentazioni e Visite -...

Documents

Transcript of Grafi: Rappresentazioni e Visite -...