Algoritmi e programmazione/Gli algoritmi di visita dei grafi

Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 13. Gli algoritmi di visita dei grafi.

[[{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Gli algoritmi di visita dei grafi}}/L'ADT grafo non orientato{{#ifcategory:Traduzioni|/Gli algoritmi di visita dei grafi||/Gli algoritmi di visita dei grafi}}|12. L'ADT grafo non orientato]]	[[{{#ifcategory:Traduzioni|/Gli algoritmi di visita dei grafi|Algoritmi e programmazione|/Gli algoritmi di visita dei grafi}}|{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Gli algoritmi di visita dei grafi}}]]	[[{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Gli algoritmi di visita dei grafi}}/Le applicazioni degli algoritmi di visita dei grafi{{#ifcategory:Traduzioni|/Gli algoritmi di visita dei grafi||/Gli algoritmi di visita dei grafi}}|14. Le applicazioni degli algoritmi di visita dei grafi]]

2 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)

3 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. 4 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.

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

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

Classificazione degli archi

20 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);
• 21 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à

24 Lista delle adiacenze

<math>T \left( n \right) = \Theta \left( \left| V \right| + \left| E \right| \right)</math>

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

Matrice delle adiacenze

<math>T \left( n \right) = \Theta \left( {\left| V \right|}^2 \right)</math>

Visita in ampiezza (BFS)

27 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.

28 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

29 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 <math>+ \infty</math>.
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à

41 Lista delle adiacenze

<math>T \left( n \right) = \Theta \left( \left| V \right| + \left| E \right| \right)</math>

Matrice delle adiacenze

<math>T \left( n \right) = \Theta \left( {\left| V \right|}^2 \right)</math>

Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 13. Gli algoritmi di visita dei grafi.

[[{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Gli algoritmi di visita dei grafi}}/L'ADT grafo non orientato{{#ifcategory:Traduzioni|/Gli algoritmi di visita dei grafi||/Gli algoritmi di visita dei grafi}}|12. L'ADT grafo non orientato]]	[[{{#ifcategory:Traduzioni|/Gli algoritmi di visita dei grafi|Algoritmi e programmazione|/Gli algoritmi di visita dei grafi}}|{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Gli algoritmi di visita dei grafi}}]]	[[{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Gli algoritmi di visita dei grafi}}/Le applicazioni degli algoritmi di visita dei grafi{{#ifcategory:Traduzioni|/Gli algoritmi di visita dei grafi||/Gli algoritmi di visita dei grafi}}|14. Le applicazioni degli algoritmi di visita dei grafi]]