DFS (visita in profondità)
Ultimo aggiornamento
La visita in profondità esplora un grafo scendendo il più in profondità possibile lungo ogni ramo prima di tornare indietro. Partendo da un nodo sorgente, visita un vicino, poi il vicino di quel vicino e così via, finché non arriva a un vicolo cieco (un nodo senza vicini non visitati); a quel punto torna indietro e prova il ramo successivo. Premi play qui sopra per vederla scendere lungo un percorso, toccare il fondo e risalire.
La DFS si esprime in modo naturale con una pila: una pila esplicita (come nell'animazione) oppure lo stack delle chiamate tramite la ricorsione. Visita ogni nodo e ogni arco una volta, quindi richiede tempo O(V + E) per un grafo con V vertici ed E archi.
Complessità temporale e spaziale
| Misura | Complessità | Note |
|---|---|---|
| Tempo | O(V + E) | Ogni vertice e ogni arco visitati una volta |
| Spazio | O(V) | Pila + insieme dei visitati, nel caso peggiore tutti i nodi |
| Visita | Prima in profondità | Segue un ramo fino in fondo prima degli altri |
| Struttura dati | Pila (o ricorsione) | L'ordine LIFO determina il comportamento in profondità |
Passo dopo passo
| Passo | Cosa succede |
|---|---|
| 1 | Inserisci il nodo sorgente nella pila. |
| 2 | Estrai un nodo; se è già stato visitato, saltalo. |
| 3 | Segnalo come visitato e registra l'arco che l'ha raggiunto. |
| 4 | Inserisci nella pila tutti i suoi vicini non visitati. |
| 5 | Ripeti finché la pila non è vuota. |
Esempio svolto
DFS iterativa da A sul grafo A → [B, C], B → [D], C → [E], inserendo i vicini nell'ordine elencato (la pila LIFO estrae per primo l'ultimo inserito):
| Passo | Pila (cima a destra) | Visitati | Azione |
|---|---|---|---|
| 1 | [A] | {} | Inserisci la sorgente A. |
| 2 | [B, C] | {A} | Estrai A, segnalo come visitato, inserisci i vicini B e poi C. |
| 3 | [B, E] | {A, C} | Estrai C, segnalo come visitato, inserisci il vicino E. |
| 4 | [B] | {A, C, E} | Estrai E, segnalo come visitato, nessun vicino. |
| 5 | [D] | {A, C, E, B} | Estrai B, segnalo come visitato, inserisci il vicino D. |
| 6 | [] | {A, C, E, B, D} | Estrai D, segnalo come visitato, pila vuota: fatto. |
Quando usare la DFS
| Usala quando | Evitala quando |
|---|---|
| Ti serve rilevare cicli, fare un ordinamento topologico o trovare le componenti connesse. | Ti serve il cammino minimo in un grafo non pesato: lo fa la BFS, non la DFS. |
| Il grafo è largo e poco profondo, quindi una pila usa molta meno memoria di una coda con tanti nodi di frontiera. | Il grafo è molto profondo e usi la ricorsione: lo stack delle chiamate può andare in overflow. |
| Vuoi esplorare tutti i percorsi in modo esaustivo, come nella risoluzione di labirinti o nella ricerca con backtracking. | Ti servono i nodi scoperti in ordine di distanza dalla sorgente. |
| Stai verificando la raggiungibilità o se esiste un percorso tra due nodi. | Devi garantire il numero minimo di archi nel percorso trovato. |
Codice Depth-First Search
Un'implementazione di Depth-First Search pulita ed eseguibile in Python, JavaScript, Java, C++, C. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice Depth-First Search in Python
Python
1def dfs(graph, node, visited):2 visited.add(node)3 order = [node]4 for neighbor in graph[node]:5 if neighbor not in visited:6 order.extend(dfs(graph, neighbor, visited))7 return order8
9
10graph = {11 "A": ["B", "C"],12 "B": ["D", "E"],13 "C": ["F"],14 "D": [],15 "E": ["F"],16 "F": [],17}18
19order = dfs(graph, "A", set())20print("DFS order:", " -> ".join(order))Codice Depth-First Search in JavaScript
JavaScript
1const graph = {2 A: ["B", "C"],3 B: ["D", "E"],4 C: ["F"],5 D: [],6 E: ["F"],7 F: [],8};9
10function dfs(node, visited = new Set(), order = []) {11 if (visited.has(node)) return order;12 visited.add(node);13 order.push(node);14 for (const next of graph[node]) {15 dfs(next, visited, order);16 }17 return order;18}19
20console.log("DFS from A:", dfs("A").join(" -> "));Codice Depth-First Search in Java
Java
1import java.util.List;2
3public class Main {4 static List<List<Integer>> adj = List.of(5 List.of(1, 2), // neighbors of 06 List.of(0, 3, 4), // neighbors of 17 List.of(0, 5), // neighbors of 28 List.of(1),9 List.of(1, 5),10 List.of(2, 4)11 );12 static boolean[] visited = new boolean[6];13
14 static void dfs(int node) {15 visited[node] = true;16 System.out.print(" " + node);17 for (int next : adj.get(node)) {18 if (!visited[next]) dfs(next);19 }20 }21
22 public static void main(String[] args) {23 System.out.print("DFS from 0:");24 dfs(0);25 System.out.println();26 }27}Codice Depth-First Search in C++
C++
1#include <iostream>2#include <vector>3
4void dfs(int node, const std::vector<std::vector<int>>& adj,5 std::vector<bool>& visited) {6 visited[node] = true;7 std::cout << node << " ";8 // Recurse into every unvisited neighbor9 for (int next : adj[node]) {10 if (!visited[next]) dfs(next, adj, visited);11 }12}13
14int main() {15 // 6-node undirected graph as an adjacency list16 std::vector<std::vector<int>> adj = {17 {1, 2}, // 018 {0, 3, 4}, // 119 {0, 5}, // 220 {1}, // 321 {1, 5}, // 422 {2, 4}, // 523 };24 std::vector<bool> visited(adj.size(), false);25 std::cout << "DFS from node 0: ";26 dfs(0, adj, visited);27 std::cout << "\n";28 return 0;29}Codice Depth-First Search in C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 65
6// 6-node undirected graph as an adjacency matrix7int adj[N][N] = {8 {0, 1, 1, 0, 0, 0},9 {1, 0, 0, 1, 1, 0},10 {1, 0, 0, 0, 0, 1},11 {0, 1, 0, 0, 0, 0},12 {0, 1, 0, 0, 0, 1},13 {0, 0, 1, 0, 1, 0},14};15bool visited[N];16
17void dfs(int node) {18 visited[node] = true;19 printf("%d ", node);20 // Recurse into every unvisited neighbor21 for (int next = 0; next < N; next++) {22 if (adj[node][next] && !visited[next]) dfs(next);23 }24}25
26int main(void) {27 printf("DFS from node 0: ");28 dfs(0);29 printf("\n");30 return 0;31}Domande frequenti sulla DFS
Qual è la complessità temporale della DFS?
La DFS richiede tempo
O(V + E), dove V è il numero di vertici ed E il numero di archi, perché visita ogni vertice una volta ed esamina ogni arco una volta. Usa spazio O(V) per la pila e l'insieme dei visitati.Qual è la differenza tra DFS e BFS?
La DFS usa una pila e scende in profondità lungo un ramo prima di tornare indietro, mentre la BFS usa una coda ed esplora livello per livello, prima i nodi più vicini. La BFS trova il cammino minimo in un grafo non pesato; la DFS no, ma usa meno memoria sui grafi larghi ed è naturale per compiti come il rilevamento di cicli e l'ordinamento topologico.
La DFS è ricorsiva o iterativa?
Funzionano entrambe. La versione ricorsiva usa implicitamente lo stack delle chiamate del programma ed è molto concisa; la versione iterativa usa una pila esplicita (come l'animazione qui) ed evita gli stack overflow da ricorsione profonda sui grafi grandi.
Quando conviene usare la DFS invece della BFS?
Usa la DFS quando devi esplorare percorsi interi: rilevamento di cicli, ordinamento topologico, componenti connesse o ricerca con backtracking come la risoluzione di un labirinto. Usa anche meno memoria sui grafi larghi, perché la pila contiene solo la frontiera di un ramo alla volta. Scegli invece la BFS quando ti serve il cammino minimo in un grafo non pesato o i nodi in ordine di distanza dalla sorgente.
La DFS può trovare il cammino minimo?
Non in modo affidabile. La DFS restituisce il primo percorso che trova, che spesso non è quello con meno archi, perché punta a scendere in profondità invece di espandersi in modo uniforme. Per i cammini minimi in un grafo non pesato usa la BFS, e per i grafi pesati usa l'algoritmo di Dijkstra.
Perché la DFS ha bisogno di un insieme dei visitati?
Senza un insieme dei visitati, la DFS rivisita i nodi raggiungibili da più percorsi e, in un grafo con cicli, gira all'infinito. Segnare un nodo come visitato quando lo estrai (e saltare le estrazioni di nodi già visitati) garantisce che ogni nodo venga elaborato una volta e mantiene il tempo a
O(V + E). Un errore comune è segnare i nodi come visitati solo all'estrazione continuando a inserire duplicati: è corretto, ma può lasciare nella pila voci vecchie da saltare.Risorse correlate
Altre visualizzazioni
