Algoritmi e programmazione/Gli algoritmi di visita dei grafi

Da WikiAppunti.
Nota disambigua.svg Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 13. Gli algoritmi di visita dei grafi.
Gtk-go-back-ltr.svg  12. L'ADT grafo non orientato Gtk-home.svg  Algoritmi e programmazione 14. Le applicazioni degli algoritmi di visita dei grafi  Gtk-go-forward-ltr.svg

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)[modifica]

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[modifica]

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[modifica]

  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[modifica]

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à[modifica]

24 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)[modifica]

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[modifica]

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 + \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à[modifica]

41 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)
Nota disambigua.svg Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 13. Gli algoritmi di visita dei grafi.
Gtk-go-back-ltr.svg  12. L'ADT grafo non orientato Gtk-home.svg  Algoritmi e programmazione 14. Le applicazioni degli algoritmi di visita dei grafi  Gtk-go-forward-ltr.svg