Cos'è visited?

Visited

L'informazione "visited" si riferisce, in informatica, a un meccanismo per tracciare quali nodi (o elementi, o stati) di una struttura dati, come un grafo, un albero o una griglia, sono già stati esplorati durante un algoritmo di ricerca o di traversal.

Scopo Principale:

L'utilizzo di "visited" previene la revisita di nodi già esplorati, evitando così:

• Cicli infiniti: In particolare nei grafi, la presenza di cicli può portare l'algoritmo a ripetere continuamente la stessa sequenza di nodi.
• Ridondanza computazionale: Esplorare più volte lo stesso nodo spreca risorse di calcolo.
• Risultati errati: In alcuni algoritmi, la revisita di un nodo può alterare il risultato finale.

Implementazione:

L'informazione "visited" viene generalmente implementata utilizzando una struttura dati ausiliaria, come:

• Array booleano: Il metodo più semplice, dove l'indice dell'array corrisponde all'identificativo del nodo e il valore booleano indica se il nodo è stato visitato o meno. Adatto se i nodi hanno identificativi (indici) che possono essere usati direttamente.
• Set (Insieme): Un set permette di memorizzare gli identificativi dei nodi visitati. La verifica dell'appartenenza (se un nodo è già presente nel set) è generalmente efficiente (spesso O(1) medio). Utile quando gli identificativi dei nodi sono complessi o non sequenziali.
• Hash Table (Tabella Hash): Simile al set, ma può anche memorizzare informazioni aggiuntive associate a ciascun nodo visitato.

Esempio di Utilizzo:

In un algoritmo di Breadth-First Search (BFS) o Depth-First Search (DFS), si controlla la struttura "visited" prima di aggiungere un nodo alla coda (BFS) o alla pila (DFS). Se il nodo è già "visited", viene ignorato; altrimenti, viene aggiunto alla coda/pila e contrassegnato come "visited".

Considerazioni:

• L'efficienza dell'implementazione di "visited" (sia in termini di memoria che di tempo di accesso) ha un impatto diretto sulle prestazioni complessive dell'algoritmo di ricerca o traversal.
• La scelta della struttura dati per implementare "visited" dipende dalle caratteristiche specifiche del problema e della struttura dati sottostante.
• In alcuni casi, anziché una struttura "visited" separata, l'informazione sulla visita può essere memorizzata direttamente all'interno della struttura dati che rappresenta il grafo o l'albero, modificando ad esempio un attributo del nodo stesso.