Visita in Profondità (DFS)

1. Cos'è la Visita in Profondità (Depth-First Search)?

La DFS (Depth-First Search) è un algoritmo di attraversamento dei grafi che procede esplorando il più in fondo possibile lungo ciascun ramo prima di effettuare il retrostepping (tornare indietro). Partendo da un nodo sorgente, l'algoritmo seleziona un vicino non visitato e ripete il procedimento finché non incontra un vicolo cieco, momento in cui risale al nodo precedente per esplorare altre ramificazioni.

Concettualmente, la DFS sfrutta una struttura dati di tipo Pila (Stack), basata sulla politica LIFO (Last In, First Out). Questa logica è gestita naturalmente in modo elegante attraverso le chiamate di funzione ricorsive (sfruttando lo stack di sistema dei programmi).

2. Proprietà e Complessità

Applicazioni principali: Rilevamento di cicli nel grafo, ordinamento topologico, calcolo delle componenti fortemente connesse e risoluzione di labirinti/puzzle.
Complessità Temporale $\mathcal{O}(V + E)$: Ciascun vertice e ciascun arco del grafo vengono esaminati esattamente una volta (supponendo di utilizzare una lista di adiacenza).
Complessità Spaziale $\mathcal{O}(V)$: Lo spazio è occupato dal vettore booleano di marcatura dei nodi visitati e dalla pila di ricorsione (o esplicita), la cui profondità massima nel caso peggiore (grafo lineare) coincide con il numero di vertici $V$.

                // Implementazione ricorsiva DFS in C++ con std::vector
                #include <vector>
                #include <iostream>

                void dfsUtil(int curr, const std::vector<std::vector<int>>& adjList, std::vector<bool>& visited) {
                visited[curr] = true;
                std::cout << curr << " ";

                for (int neighbor :
                adjList[curr]) {
                if (!visited[neighbor]) {
                dfsUtil(neighbor, adjList, visited);
                }
                }
                }

                void dfs(int startNode, const std::vector<std::vector<int>>& adjList) {
                int n = adjList.size();
                std::vector<bool> visited(n, false);
                dfsUtil(startNode, adjList, visited);
                }
            

3. Simulatore Interattivo: Configurazione Esplorazione DFS

Configura i parametri di esecuzione della visita ricorsiva in profondità impostando i nodi e la sorgente di avvio.

dfs-engine@nexus-core:~# Depth-First Simulation

Nodi Totali ($V$):

Nodo Sorgente ($s$):

> Inserisci i parametri e avvia la simulazione dello stack di chiamata ricorsivo LIFO.

Visita in Profondità (DFS)

1. Cos'è la Visita in Profondità (Depth-First Search)?

2. Proprietà e Complessità

3. Simulatore Interattivo: Configurazione Esplorazione DFS

Gestione della Privacy e dei Cookie