# Algoritmi/Gli algoritmi di visita dei grafi

Algoritmi
Copertina Tutti i moduli · Sviluppo
    CopertinaAlgoritmi/Copertina
* Gli algoritmiAlgoritmi/Gli algoritmi
* L'analisi di complessità degli algoritmiAlgoritmi/L'analisi di complessità degli algoritmi
* Gli algoritmi di ordinamentoAlgoritmi/Gli algoritmi di ordinamento
* Grafi e alberiAlgoritmi/Grafi e alberi
* La ricorsioneAlgoritmi/La ricorsione
* Il paradigma "divide et impera"Algoritmi/Il paradigma "divide et impera"
* Gli heapAlgoritmi/Gli heap
* Le tabelle di simboliAlgoritmi/Le tabelle di simboli
* Alberi binari di ricerca (BST)Algoritmi/Alberi binari di ricerca (BST)
* Tipologie di problemiAlgoritmi/Tipologie di problemi
* Le tabelle di hashAlgoritmi/Le tabelle di hash
* L'ADT grafo non orientatoAlgoritmi/L'ADT grafo non orientato
* Gli algoritmi di visita dei grafiAlgoritmi/Gli algoritmi di visita dei grafi
* Le applicazioni degli algoritmi di visita dei grafiAlgoritmi/Le applicazioni degli algoritmi di visita dei grafi
* Gli alberi ricoprenti minimiAlgoritmi/Gli alberi ricoprenti minimi
* I cammini minimiAlgoritmi/I cammini minimi
Modifica il sommario
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

* si parte da un vertice, e si verifica se esistono vertici adiacenti (ovvero se è connesso ad altri vertici da archi);
* i vertici adiacenti possono essere o ancora da scoprire, o già scoperti, o già terminati come elaborazione;
* secondo un criterio fisso, si sceglie il nodo su cui scendere (ad esempio: nodo più a sinistra, ordine lessicografico) tra quelli non ancora scoperti;
* 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.
* In primo luogo, si assume per ogni nodo la condizione "non esiste cammino" → si associa la massima distanza concepibile $+\infty$.
* Si scende sui vertici adiacenti v e w, si riesegue la stima della distanza, quindi li si inserisce in una coda FIFO.
* 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)$