Algoritmi/Gli algoritmi di visita dei grafi

Indice del libro

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

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

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

Lista delle adiacenze
 
  • inizializzazione: legata al numero dei vertici ( )
  • visita ricorsiva: legata al numero di archi ( )
Matrice delle adiacenze
 

Visita in ampiezza (BFS) modifica

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 modifica

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

Lista delle adiacenze
 
Matrice delle adiacenze