Visita di un grafo

Table of Contents

Visita in ampiezza

La visita in ampiezza si basa sull'assegnazione a ogni vertice di un colore tra bianco, grigio e nero: il bianco indica che il vertice non è ancora stato visitato, il grigio indica che è stato visitato, ma non sono stati visitati tutti i suoi vertici adiacenti, il nero indica che è stato visitato il vertice e tutti i vertici adiacenti.

La visita in ampiezza sfrutta alcune strutture dati di appoggio:

il colore di un vertice è memorizzato in una lista in cui la chiave è il vertice e il valore è il colore: color[v]
il predecessore di un vertice è memorizzato in una lista in cui la chiave è il vertice e il valore è il predecessore: π[v]
la distanza dal vertice sorgente è memorizzata in una lista in cui la chiave è il vertice e il valore è un numero naturale: d[v]
l'elenco di vertici grigi è una coda FIFO: Q

L'algoritmo opera così:

for each v in G inizializzazione dei vertici (tranne il sorgente)
1. color[v] = white; imposto il colore bianco
2. π[v] = NIL; il predecessore del vertice è vuoto
3. d[v] = ∞; la distanza dalla sorgente è infinita
inizializzazione del vertice sorgente
1. color[s] = grey; imposto il colore grigio
2. π[s] = NIL; il predecessore della sorgente è NIL (resterà così)
3. d[s] = 0; la distanza dalla sorgente è zero (resterà così)
Q ↞ s; aggiungo alla FIFO l'elemento sorgente
while Q ≠ ∅, Q ↠ v; finché la coda Q non è vuota estraggo l'elemento in coda
1. 1. for each u = adj(v); per ogni vertice u adiacente a v
    1. if color[u] == white; se il colore di u è bianco
      1. color[u] = grey; imposta il colore grigio a u
      2. d[u] = d[v] + 1; la distanza di u è uno più di v
      3. π[u]= v; il predecessore di u è v
      4. Q ↞ u; accoda u all'elenco di vertici grigi
  2. color[v] = black; imposta il colore di v a nero

Il tempo di esecuzione di questo algoritmo è O(V+E), poiché ogni vertice e "toccato" una sola volta e ogni arco è "toccato" al massimo una volta.

Siccome se un nodo è già stato visitato non si visitano più i suoi archi, la visita in ampiezza crea, di fatto, un albero.

Visita in profondità

La visita in profondità inizia dal nodo sorgente e lo marca in grigio, poi non lo marca in nero finché non sono neri tutti i suoi successori, e così via ricorsivamente.

L'algoritmo ricorda il modo per uscire sempre da un labirinto (senza isole), che consiste nel procedere con una mano sempre appoggiata al lato (es. mano destra tocca sempre la parete destra).

L'algoritmo è composto da una parte di inizializzazione e lancio della parte ricorsiva e una seconda parte che richiama se stessa nei suoi sotto-vertici:

function DFS

for each v in G inizializzazione dei vertici (tranne il sorgente)
1. color[v] = white; imposto il colore bianco
2. π[v] = NIL; il predecessore del vertice è vuoto
3. time = 0; informazione sull'ordine di esecuzione
for each v in adj(s) richiama la visita su ogni nodo adiacente
1. if color[v] == white, DFG-visit(v)

function DFS-visit(v)

color[v] = grey;
time = time + 1;
d[v] = time;
for each u in adj(v)
1. if color[u] == white
  1. π[u] = v;
  2. DFS-visit(u)
color[v] = black;
time = time + 1
f[v] = time

Il tempo di esecuzione di questa funzione è Θ(V+E).

Una proprietà importante di questa visita è che l'ordine dei vertici visitati potrebbe ricalcare uno schema "a parentesi", cioè se apriamo una parentesi ogni volta che visitiamo un vertice e la chiudiamo ogni volta che finsice la visita, otteniamo una struttura a parentesi "ben formato".

Un'altra proprietà è che a seconda del colore che troviamo possiamo classificare gli archi:

se l'arco è collegato a un vertice white, abbiamo un arco dell'albero
se l'arco è collegato a un vertice grey, abbiamo un arco all'indietro
se l'arco(u, v) è collegato a un vertice black, abbiamo un arco in avanti (se d[u] < d[v]) o di attraversamento (se d[u] > d[v])

Topological sort

Utilizzando la DFS è possibile ordinare i vertici di un grafo in base all'ordine in cui sono disposti.

Grafici aciclici

Se una visita in profondità non incontra mai vertici grey, il grafo è aciclico.