Laboratorio di Algoritmi e Strutture Dati Ingegneria e Scienze

Strutture dati per grafi
Visita di un grafo
Laboratorio di Algoritmi e Strutture Dati
Ingegneria e Scienze Informatiche - Cesena
A.A. 2013-2014
Pietro Di Lena
[email protected], [email protected]
Pietro Di Lena
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Lista di adiacenza
Matrice di adiacenza
Lista di adiacenza
Struttura dati per la rappresentazione in memoria di grafi (diretti e pesati)
Occupazione in spazio: O(|V | + |E |) (|V | = numero di vertici, |E | = numero di archi)
Verifica dell’esistenza di un arco tra due vertici v 1, v 2: O(outdegree(v 1))
Visita dei vertici adiacenti ad un vertice v : O(outdegree(v ))
b
0
1
d
a
a,0
b
d,1
c
e,4
d
e,1
e
b,5
b,1
1
5
a
2
1
3
c
4
e
Pietro Di Lena
d,2
Laboratorio di Algoritmi e Strutture Dati
c,3
Strutture dati per grafi
Visita di un grafo
Lista di adiacenza
Matrice di adiacenza
Nota: formato di un grafo in file di testo
Possibile formato di testo per un grafo:
Prima riga: numero di vertici nel grafo.
Righe successive alla seconda:
<id vertice1> <id vertice2> <peso dell’arco diretto tra vertice1 e vertice2>
Per semplicit`
a utilizziamo valori interi tra 0 e n − 1 per le label dei vertici.
5
0
0
0
1
2
3
4
4
2
1
0
3
4
4
3
1
3
1
0
1
4
2
2
5
Pietro Di Lena
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Lista di adiacenza
Matrice di adiacenza
Nota: lettura di un grafo da file in lista di adiacenza 1/2
Definizione della struttura vertice per una lista di adiacenza.
typedef struct VERTEX {
int id ;
int dist ;
struct VERTEX * next ;
} VERTEX ;
VERTEX * VertexAlloc ( int id , int dist ) {
VERTEX * v = ( VERTEX *) malloc ( sizeof ( VERTEX ) ) ;
v - > id
= id ;
v - > dist = dist ;
v - > next = NULL ;
return v ;
}
Pietro Di Lena
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Lista di adiacenza
Matrice di adiacenza
Nota: lettura di un grafo da file in lista di adiacenza 2/2
Lettura di un grafo da file in lista di adiacenza.
VERTEX ** AdjListRead ( char * file , int * n ) {
FILE * in = fopen ( file ," r ") ;
VERTEX ** AdjList ;
int i ,j , dist ;
if ( in == NULL )
return NULL ;
if ( fscanf ( in ,"% d " , n ) == EOF ) return NULL ;
AdjList = ( VERTEX **) calloc (* n , sizeof ( VERTEX *) ) ;
while ( fscanf ( in ,"% d % d % d \ n " ,&i ,& j ,& dist ) != EOF )
if (i >=0 && i <* n && j >=0 && j <* n ) {
VERTEX * tmp = VertexAlloc (j , dist ) ;
tmp - > next = AdjList [ i ];
AdjList [ i ] = tmp ;
}
fclose ( in ) ;
return AdjList ;
}
Pietro Di Lena
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Lista di adiacenza
Matrice di adiacenza
Matrice di adiacenza
Struttura dati per la rappresentazione in memoria di grafi (diretti e pesati)
Occupazione in spazio: O(|V |2 ) (|V | = numero di vertici)
Verifica dell’esistenza di un arco tra due vertici v 1, v 2: O(1)
Visita dei vertici adiacenti ad un vertice v : O(|V |)
b
0
1
b
c
d
e
0
1
3
-
-
b
-
-
-
1
-
c
-
-
-
-
4
d
-
-
-
-
1
e
-
5
-
2
-
d
1
5
a
a
a
2
1
3
c
4
e
Pietro Di Lena
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Lista di adiacenza
Matrice di adiacenza
Nota: lettura di un grafo da file in matrice di adiacenza 1/2
Definizione della struttura dati matrice di adiacenza. Adottiamo, come possibile
scelta implementativa, il valore INT MIN per indicare un arco non esistente.
# include < limits .h >
# define NIL INT_MIN
int ** MatrixAlloc ( int n ) {
int i ,j ,** m =( int **) calloc (n , sizeof ( int *) ) ;
m [0]=( int *) calloc ( n *n , sizeof ( int ) ) ;
for ( i =0; i < n ; i ++)
m [ i ]=& m [0][ n * i ];
for ( i =0; i < n ; i ++)
for ( j =0; j < n ; j ++)
m [ i ][ j ]= NIL ;
return m ;
}
Pietro Di Lena
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Lista di adiacenza
Matrice di adiacenza
Nota: lettura di un grafo da file in matrice di adiacenza 2/2
Lettura di un grafo da file in matrice di adiacenza.
int ** AdjMatrixRead ( char * file , int * n ) {
FILE * in = fopen ( file ," r ") ;
int ** AdjMatrix ;
int i ,j , dist ;
if ( in == NULL )
return NULL ;
if ( fscanf ( in ,"% d " , n ) == EOF ) return NULL ;
AdjMatrix = MatrixAlloc (* n ) ;
while ( fscanf ( in ,"% d % d % d \ n " ,&i ,& j ,& dist ) != EOF )
if (i >=0 && i <* n && j >=0 && j <* n )
AdjMatrix [ i ][ j ]= dist ;
fclose ( in ) ;
return AdjMatrix ;
}
Pietro Di Lena
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Lista di adiacenza
Matrice di adiacenza
Nota: struttura dati generica per grafi
typedef struct GRAPH {
VERTEX ** AdjList ; // Lista di adiacenza
int ** AdjMatrix ; // Matrice di adiacenza
int n ; // Numero di vertici nel grafo
int * c ; // Colore
int * p ; // Predecessore ( DFS )
int * s ; // Inizio visita ( DFS )
int * t ; // Fine visita ( DFS )
int * d ; // Distanza ( BFS )
} GRAPH ;
GRAPH * GraphAlloc ( int n ) {
GRAPH * G = ( GRAPH *) malloc ( sizeof ( GRAPH ) ) ;
G->n
= n;
G - > AdjList
= NULL ;
G - > AdjMatrix = NULL ;
G->c
= ( int *) calloc (n , sizeof ( int ) ) ;
G->p
= ( int *) calloc (n , sizeof ( int ) ) ;
G->s
= ( int *) calloc (n , sizeof ( int ) ) ;
G->t
= ( int *) calloc (n , sizeof ( int ) ) ;
G->d
= ( int *) calloc (n , sizeof ( int ) ) ;
return G ;
}
Pietro Di Lena
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Lista di adiacenza
Matrice di adiacenza
Nota: lettura di un grafo da file
GRAPH * G ra p hR ea d By A d j L i s t ( char * file ) {
GRAPH * G ;
VERTEX ** AdjList ;
int n ;
if (( AdjList = AdjListRead ( file ,& n ) ) == NULL ) return NULL ;
G = GraphAlloc ( n ) ;
G - > AdjList = AdjList ;
return G ;
}
GRAPH * G r a p h R e a d B y A d j M a t r i x ( char * file ) {
GRAPH * G ;
int ** AdjMatrix ;
int n ;
if (( AdjMatrix = AdjMatrixRead ( file ,& n ) ) == NULL ) return NULL ;
G = GraphAlloc ( n ) ;
G - > AdjMatrix = AdjMatrix ;
return G ;
}
Pietro Di Lena
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Depth First Search: esempio
Depth First Search: pseudocodice
Depth First Search
La ricerca in profondit`
a (Depth First search) `e una procedura (ricorsiva) di
vista di un grafo.
Dato un vertice sorgente, produce un albero di copertura per la
componente connessa a cui appartiene il vertice sorgente.
Utilizzando dei marcatori di inizio e fine visita di un vertice, pu`
o essere
utilizzata per calcolare un ordinamento topologico nei grafi diretti e aciclici
(DAG).
Costo computazionale: O(|V | + |E |).
Informazioni aggiuntive utilizzate dalla DFS:
colore di un nodo (c[]): WHITE (non visitato), GREY (in visita), BLACK
(gi`
a visitato)
puntatore al padre (p[]): contiene le informazione per ricostruire l’albero di
copertura
inizio visita (s[]): marcatore temporale intero
fine visita (t[]): marcatore temporale intero
Pietro Di Lena
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Depth First Search: esempio
Depth First Search: pseudocodice
Depth First Search: esempio
p[b]=NIL
s[b]=NIL
t[b]=NIL
time=0
b
0
p[d]=NIL
s[d]=NIL
t[d]=NIL
1
d
1
p[a]=NIL
s[a]=NIL
t[a]=NIL
5
a
2
1
3
c
p[c]=NIL
s[c]=NIL
t[c]=NIL
Pietro Di Lena
4
e
p[e]=NIL
s[e]=NIL
t[e]=NIL
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Depth First Search: esempio
Depth First Search: pseudocodice
Depth First Search: esempio
p[b]=NIL
s[b]=NIL
t[b]=NIL
time=1
b
0
p[d]=NIL
s[d]=NIL
t[d]=NIL
1
d
1
p[a]=NIL
s[a]=1
t[a]=NIL
5
a
2
1
3
c
p[c]=NIL
s[c]=NIL
t[c]=NIL
Pietro Di Lena
4
e
p[e]=NIL
s[e]=NIL
t[e]=NIL
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Depth First Search: esempio
Depth First Search: pseudocodice
Depth First Search: esempio
p[b]=a
s[b]=2
t[b]=NIL
time=2
b
0
p[d]=NIL
s[d]=NIL
t[d]=NIL
1
d
1
p[a]=NIL
s[a]=1
t[a]=NIL
5
a
2
1
3
c
p[c]=NIL
s[c]=NIL
t[c]=NIL
Pietro Di Lena
4
e
p[e]=NIL
s[e]=NIL
t[e]=NIL
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Depth First Search: esempio
Depth First Search: pseudocodice
Depth First Search: esempio
p[b]=a
s[b]=2
t[b]=NIL
time=3
b
0
p[d]=b
s[d]=3
t[d]=NIL
1
d
1
p[a]=NIL
s[a]=1
t[a]=NIL
5
a
2
1
3
c
p[c]=NIL
s[c]=NIL
t[c]=NIL
Pietro Di Lena
4
e
p[e]=NIL
s[e]=NIL
t[e]=NIL
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Depth First Search: esempio
Depth First Search: pseudocodice
Depth First Search: esempio
p[b]=a
s[b]=2
t[b]=NIL
time=4
b
0
p[d]=b
s[d]=3
t[d]=NIL
1
d
1
p[a]=NIL
s[a]=1
t[a]=NIL
5
a
2
1
3
c
p[c]=NIL
s[c]=NIL
t[c]=NIL
Pietro Di Lena
4
e
p[e]=d
s[e]=4
t[e]=NIL
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Depth First Search: esempio
Depth First Search: pseudocodice
Depth First Search: esempio
p[b]=a
s[b]=2
t[b]=NIL
time=5
b
0
p[d]=b
s[d]=3
t[d]=NIL
1
d
1
p[a]=NIL
s[a]=1
t[a]=NIL
5
a
2
1
3
c
p[c]=NIL
s[c]=NIL
t[c]=NIL
Pietro Di Lena
4
e
p[e]=d
s[e]=4
t[e]=5
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Depth First Search: esempio
Depth First Search: pseudocodice
Depth First Search: esempio
p[b]=a
s[b]=2
t[b]=NIL
time=6
b
0
p[d]=b
s[d]=3
t[d]=6
1
d
1
p[a]=NIL
s[a]=1
t[a]=NIL
5
a
2
1
3
c
p[c]=NIL
s[c]=NIL
t[c]=NIL
Pietro Di Lena
4
e
p[e]=d
s[e]=4
t[e]=5
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Depth First Search: esempio
Depth First Search: pseudocodice
Depth First Search: esempio
p[b]=a
s[b]=2
t[b]=7
time=7
b
0
p[d]=b
s[d]=3
t[d]=6
1
d
1
p[a]=NIL
s[a]=1
t[a]=NIL
5
a
2
1
3
c
p[c]=NIL
s[c]=NIL
t[c]=NIL
Pietro Di Lena
4
e
p[e]=d
s[e]=4
t[e]=5
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Depth First Search: esempio
Depth First Search: pseudocodice
Depth First Search: esempio
p[b]=a
s[b]=2
t[b]=7
time=8
b
0
p[d]=b
s[d]=3
t[d]=6
1
d
1
p[a]=NIL
s[a]=1
t[a]=NIL
5
a
2
1
3
c
p[c]=a
s[c]=8
t[c]=NIL
Pietro Di Lena
4
e
p[e]=d
s[e]=4
t[e]=5
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Depth First Search: esempio
Depth First Search: pseudocodice
Depth First Search: esempio
p[b]=a
s[b]=2
t[b]=7
time=9
b
0
p[d]=b
s[d]=3
t[d]=6
1
d
1
p[a]=NIL
s[a]=1
t[a]=NIL
5
a
2
1
3
c
p[c]=a
s[c]=8
t[c]=9
Pietro Di Lena
4
e
p[e]=d
s[e]=4
t[e]=5
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Depth First Search: esempio
Depth First Search: pseudocodice
Depth First Search: esempio
p[b]=a
s[b]=2
t[b]=7
time=10
b
0
p[d]=b
s[d]=3
t[d]=6
1
d
1
p[a]=NIL
s[a]=1
t[a]=10
5
a
2
1
3
c
p[c]=a
s[c]=8
t[c]=9
Pietro Di Lena
4
e
p[e]=d
s[e]=4
t[e]=5
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Depth First Search: esempio
Depth First Search: pseudocodice
Depth First Search: esempio
Albero di copertura prodotto dalla DFS a partire dal vertice sorgente a.
a
[2,7]
b
[3,6]
d
[4,5]
e
Pietro Di Lena
[1,10]
c
[8,9]
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Depth First Search: esempio
Depth First Search: pseudocodice
Depth First Search: pseudocodice
1: procedure DFS(G , u)
2:
for each vertex v in G do
3:
c[v ] ← WHITE
4:
p[v ] ← s[v ] ← t[v ] ← NIL
5:
end for
6:
time ← 0
7:
DFS-Visit(G , u)
8: end procedure
1: procedure DFS-Visit(G , u)
2:
c[u] ← GREY
3:
s[u] ← time ← time + 1
4:
for each vertex v in G adj to u do
5:
if c[v]=WHITE then
6:
p[v ] ← u
7:
DFS-Visit(G , v )
8:
end if
9:
end for
10:
c[u] ← BLACK
11:
t[u] ← time ← time + 1
12: end procedure
Quale implementazione `
e maggiormente efficiente: con liste o matrici di adiacenza?
Pietro Di Lena
Laboratorio di Algoritmi e Strutture Dati
Strutture dati per grafi
Visita di un grafo
Depth First Search: esempio
Depth First Search: pseudocodice
Nota: come generare un grafo random
Genera un grafo random di n vertici. L’argomento prob, controlla la probabilit`
a che esista un arco
tra due nodi. L’argomento maxdist controlla la distanza massima tra due nodi connessi.
# include < stdio .h >
# include < stdlib .h >
# include < time .h >
int main ( int argc , char * argv []) {
int n , max ,i , j ;
double prob ;
if ( argc !=4) {
fprintf ( stderr ," Usage : randgraph <n > < prob edge > < maxdist >\ n ") ;
return 1;
}
n = atoi ( argv [1]) ;
prob = atof ( argv [2]) ;
max = atoi ( argv [3]) ;
srand ( time ( NULL ) ) ;
printf ("% d \ n " , n ) ;
for ( i =0; i < n ; i ++)
for ( j =0; j < n ; j ++)
if (1.0* rand () / RAND_MAX < prob )
printf ("% d % d % d \ n " ,i ,j , rand () %( max +1) ) ;
return 0;
}
Pietro Di Lena
Laboratorio di Algoritmi e Strutture Dati

Download Report