Grafi: Visite e Ordinamento Topologico

Un algoritmo per esplorare un grafo, elaborando i nodi in un determinato ordine. Inizia da un nodo radice e visita i suoi nodi adiacenti, quindi i nodi adiacenti a questi e così via, finché tutti i nodi raggiungibili dalla radice sono esplorati.

L'insieme di nodi che sono stati visitati ma non ancora completamente esplorati in un BFS. I nodi grigi sono quelli che hanno almeno un nodo adiacente non ancora visitato.

Un nodo in un BFS che ha già visitato tutti i suoi nodi adiacenti. I nodi neri sono considerati completamente esplorati.

Un nodo in un BFS che è stato identificato ma non ancora visitato. I nodi bianchi sono quelli che non sono ancora stati esplorati dall'algoritmo.

L'arco utilizzato per spostarsi da un nodo grigio a un nodo bianco durante un BFS. Rappresenta la connessione tra i nodi.

Il cambio di stato da bianco a grigio in un BFS indica che il nodo è stato raggiunto dall'algoritmo e verrà esplorato in un prossimo passo.

Il cambio di stato da grigio a nero in un BFS indica che il nodo è stato completamente esplorato e tutti i suoi nodi adiacenti sono stati visitati.

Il criterio per convertire un nodo grigio in nero in un BFS. Se non ha più nodi adiacenti bianchi, significa che tutti i suoi vicini sono stati già esplorati.

Un algoritmo che visita tutti i nodi di un grafo a partire da un nodo sorgente, esplorando i nodi vicini prima di esplorare i nodi più lontani.

La visita in ampiezza utilizza una coda per gestire l'insieme dei nodi grigi. I nodi grigi sono i nodi che sono stati scoperti ma non ancora esplorati.

La visita in ampiezza visita tutti gli adiacenti di un nodo prima di passare al prossimo nodo. In questo modo, tutti i nodi ad una certa distanza dal nodo sorgente vengono visitati prima di passare ai nodi ad una distanza maggiore.

Un nodo bianco non è stato ancora scoperto. Un nodo grigio è stato scoperto ma non ancora completamente esplorato. Un nodo nero è stato scoperto e completamente esplorato.

La BFS viene utilizzata per trovare il percorso più corto da un nodo sorgente a tutti gli altri nodi in un grafo non orientato. Questo è il caso perché la BFS visita tutti i nodi ad una certa distanza dal nodo sorgente prima di passare ai nodi ad una distanza maggiore.

Nella BFS, per ogni nodo viene marcato il suo predecessore (π) e la distanza (d) dal nodo sorgente. Questo permette di ricostruire il cammino più breve dal nodo sorgente a qualsiasi altro nodo.

Durante la BFS, un nodo non può ridiventare bianco. Questo implica che ogni arco del grafo viene attraversato solo una volta.

La complessità temporale della BFS è O(|V| + |E|), dove |V| è il numero di nodi e |E| è il numero di archi nel grafo.

All'inizio della visita di un grafo, i nodi sono bianchi. Un nodo diventa grigio quando viene visitato per la prima volta. Un nodo diventa nero quando viene totalmente esplorato.

Le invarianti sono proprietà che rimangono vere durante l'esecuzione di un algoritmo. Nel contesto della visita di un grafo, ci sono tre invarianti che garantiscono la correttezza dell'algoritmo.

L'invariante I1 afferma che tutti i nodi adiacenti a un nodo nero devono essere grigi o neri. Ciò significa che tutti i vicini di un nodo completamente esplorato sono stati visitati.

L'invariante I2 afferma che tutti i nodi grigi o neri sono raggiungibili dal nodo di partenza della visita. Questa invariante garantisce che la visita raggiunga effettivamente tutti i nodi che possono essere raggiunti dal nodo di partenza.

L'invariante I3 afferma che qualsiasi cammino dal nodo di partenza a un nodo bianco deve contenere almeno un nodo grigio. Questo significa che per raggiungere un nodo non ancora visitato, bisogna passare necessariamente da un nodo visitato.

L'algoritmo Visita(G, s) visita un grafo G partendo da un nodo s. L'obiettivo è esplorare tutti i nodi raggiungibili da s e colorarli di nero.

L'algoritmo Visita-Tutti-Vertici(G) esegue una visita completa del grafo G, assicurandosi di visitare ed esplorare tutti i nodi del grafo.

La complessità della visita completa dipende dalla gestione dell'insieme dei nodi grigi e dal controllo degli archi. La complessità associata ai nodi è O(|V|) e la complessità associata agli archi dipende da come viene effettuato il controllo degli archi.

Un algoritmo che visita tutti i nodi di un grafo, tenendo traccia dei nodi già visitati per evitare cicli e garantendo che tutti i nodi siano raggiunti.

Un attributo che indica lo stato di un nodo durante la visita di un grafo, con tre possibili valori: bianco (non ancora visitato), grigio (in corso di visita) e nero (visitato completamente).

I nodi adiacenti ad un nodo grigio che non sono ancora stati visitati.

Il processo di esplorazione dei nodi di un grafo partendo da un nodo di partenza, visitando sistematicamente i suoi nodi adiacenti.

Il processo di esplorazione dei nodi di un grafo partendo da un nodo di partenza, visitando sistematicamente i suoi nodi adiacenti in un ordine specifico.

Un algoritmo che determina se un grafo è aciclico (senza cicli), verificando se durante la visita in profondità si incontrano archi che puntano a nodi già visitati.

Un algoritmo che ordina i nodi di un grafo aciclico in modo tale che se esiste un arco da un nodo u a un nodo v, allora u precede v nell'ordinamento.

Un gruppo di nodi di un grafo tale che per ogni coppia di nodi (u, v) esiste un cammino da u a v e da v a u.

Nella visita in profondità, ogni nodo ha un attributo 'π' che identifica il suo predecessore nella foresta generata dalla visita. Il nodo radice è l'unico nodo senza predecessore, quindi 'π' è impostato a 'nil' per esso.

In una visita in profondità, il livello di un nodo è dato dall'attributo 'd'. Il livello indica la distanza del nodo dalla radice, in termini di numero di archi da attraversare per raggiungerlo. La radice ha livello 0.

La visita in profondità utilizza una pila per tenere traccia dei nodi non ancora esplorati. Questi nodi vengono chiamati 'grigio' perché non sono ancora stati completamente 'elaborati'.

Utilizzando un contatore chiamato 'time', la visita in profondità assegni due attributi a ogni nodo: 'time_start' e 'time_finish'. 'time_start' indica il momento in cui il nodo diventa 'grigio', mentre 'time_finish' indica il momento in cui il nodo diventa 'nero' (cioè, quando tutti i suoi vicini sono stati visitati).

La visita in profondità genera un albero che rappresenta il percorso seguito durante l'esplorazione del grafo. Questo albero si chiama 'foresta' perché può avere più radici, in caso di grafo con più componenti connesse.

L'algoritmo di Visita in Profondità (Depth First Search, DFS) è un algoritmo di ricerca in un grafo. Inizia da un nodo di partenza e esplora il grafo il più in profondità possibile lungo ogni ramo prima di tornare indietro. Ciò significa che visita tutti i vicini di un nodo prima di esplorare i vicini dei suoi vicini.

In un grafo, l'inizializzazione per la Visita in Profondità assegna a ogni nodo un colore (bianco inizialmente), un predecessore (nil inizialmente), un tempo di inizio (∞ inizialmente) e un tempo di fine (∞ inizialmente). Il tempo time è utilizzato per tenere traccia dell'ordine delle visite.

Durante la Visita in Profondità, un nodo viene considerato "bianco" se non è ancora stato visitato, "grigio" se è in corso di visita e "nero" se è stato completamente visitato, insieme a tutti i suoi vicini.

Quando un nodo u viene visitato per la prima volta, u.i viene impostato al tempo time corrente. Questo indica il momento in cui la visita di u è iniziata.

Quando la visita di un nodo u è completata, u.f viene impostato al tempo time corrente. Questo indica il momento in cui la visita di u è terminata.

Un arco di albero è un arco che è incluso nella foresta generata dalla Visita in Profondità. È l'arco che collega un nodo al suo predecessore, e quindi traccia il percorso di esplorazione.

Un arco all'indietro (Back edge) collega un nodo a un suo antenato nell'albero della foresta. Indica un ciclo nel grafo.

Un arco in avanti (Forward edge) collega un nodo a un suo discendente nell'albero della foresta. Indica un percorso non preso durante l'esplorazione iniziale.