Algoritmi/Gli algoritmi di visita dei grafi

La visita di un grafo consiste nell'elencare tutti i vertici del grafo a partire da un vertice dato secondo una determinata strategia, elencando le informazioni memorizzate nel grafo.

Visita in profondità (DFS)

Si segue un cammino finché esso non si interrompe per qualche ragione, e si ritorna sulle scelte fatte. Tutti i vertici vengono visitati indipendentemente dal fatto che siano tutti raggiungibili o meno dal vertice di partenza. Si esplora una foresta di alberi estratta dal grafo di partenza: ogni nodo del grafo appartiene a uno e un solo albero della foresta; solo gli archi di tipo Tree appartengono alla foresta, mentre gli altri archi si dicono Backward o, nel caso del grafo orientato, Forward e Cross.

Tempo

Si usa una linea del tempo discreta: a intervalli regolari esistono istanti in corrispondenza biunivoca con numeri naturali, e il tempo esiste soltanto in quegli istanti discretizzati. Sotto certe condizioni, il tempo passa discretamente dall'istante t all'istante t + 1. Ogni vertice si etichetta con un tempo di scoperta (il vertice è stato incontrato per la prima volta) e un tempo di fine elaborazione (il nodo non ha più informazioni da fornire).

Passi

1. si parte da un vertice, e si verifica se esistono vertici adiacenti (ovvero se è connesso ad altri vertici da archi);
2. i vertici adiacenti possono essere o ancora da scoprire, o già scoperti, o già terminati come elaborazione;
3. secondo un criterio fisso, si sceglie il nodo su cui scendere (ad esempio: nodo più a sinistra, ordine lessicografico) tra quelli non ancora scoperti;
4. si opera ricorsivamente sui nodi figlio, fino a quando non esistono più vertici adiacenti → sono stati visitati tutti i nodi.

Per un nodo la fine elaborazione corrisponde all'uscita del nodo dalla ricorsione.

Convenzione colori: non ancora scoperto = bianco | scoperto ma non completato = grigio | scoperto e completato = nero

Classificazione degli archi

Dopo aver individuato gli archi di tipo Tree e riorganizzato il grafo di partenza come foresta di alberi di visita in profondità, vi si aggiungono gli archi rimanenti e li si classifica confrontando i tempi di scoperta e di fine elaborazione dei nodi su cui ciascun arco insiste:

• Backward: connette un nodo u a un suo antenato v (tempo di scoperta v < u e tempo di fine elaborazione v > u);
• Forward (solo nei grafi orientati): connette un nodo a un suo discendente (tempo di scoperta v > u e tempo di fine elaborazione v < u);
• Cross: archi rimanenti (solo nei grafi orientati).

Analisi di complessità

Lista delle adiacenze

$T\left(n\right)=\Theta \left(\left|V\right|+\left|E\right|\right)$

• inizializzazione: legata al numero dei vertici ($\Theta \left(\left|V\right|\right)$)
• visita ricorsiva: legata al numero di archi ($\Theta \left(\left|E\right|\right)$)

Matrice delle adiacenze

$T\left(n\right)=\Theta \left({\left|V\right|}^{2}\right)$

Visita in ampiezza (BFS)

La visita in ampiezza opera in parallelo su tutti i nodi correnti. Non necessariamente vengono visitati tutti i vertici del grafo, ma solo i vertici raggiungibili dal vertice di partenza; non c'è più una foresta di alberi, ma c'è un unico albero. Si applica a un grafo non pesato, che è equivalente a un grafo pesato in cui ogni arco ha egual peso.

A ciascun vertice corrente si associa la distanza minima dal vertice di partenza, ma i pesi sono tutti uguali → è un caso particolare della ricerca dei cammini minimi.

Passi

Bisogna ricondurre il lavoro in parallelo in un modello seriale. A ogni passo, la stima della distanza minima viene ricalcolata.

1. In primo luogo, si assume per ogni nodo la condizione "non esiste cammino" → si associa la massima distanza concepibile $+\infty$.
2. Si scende sui vertici adiacenti v e w, si riesegue la stima della distanza, quindi li si inserisce in una coda FIFO.
3. Si riesegue il passo 2. per i vertici adiacenti del nodo v, che nella coda verranno inseriti dopo w, e per quelli di w, inseriti alla fine → verranno processati prima i nodi adiacenti di w, poi i nodi adiacenti di v, quindi w e infine v, come se l'albero risultante venisse esplorato da destra verso sinistra livello per livello.

Analisi di complessità

Lista delle adiacenze

$T\left(n\right)=\Theta \left(\left|V\right|+\left|E\right|\right)$

Matrice delle adiacenze

$T\left(n\right)=\Theta \left({\left|V\right|}^{2}\right)$