La ricerca in profondità (DFS) è un algoritmo per l'attraversamento o la ricerca di strutture di dati ad albero o graph. Si inizia dalla radice (selezionando qualche nodo arbitrario come radice per un grafo) ed esplorando il più lontano possibile lungo ogni ramo prima di backtracking.
Il graph seguente mostra l'ordine in cui i nodi vengono rilevati in DFS:
Ricerca in profondità negli alberi
Un albero è un grafo non orientato in cui due vertici qualsiasi sono collegati esattamente da un percorso. In altre parole, qualsiasi grafo connesso aciclico è un albero. Per un albero, abbiamo i seguenti metodi di attraversamento:
- Preordinare: visita ogni nodo prima dei suoi figli.
- Postordine: visita ogni nodo dopo i suoi figli.
- In ordine (for alberi binari solo): visita sottoalbero sinistro, nodo, sottoalbero destro.
Questi sono già trattati in dettaglio in post separati.
Ricerca in profondità nel graph
UN Ricerca in profondità (DFS) è un modo per attraversare i graficici strettamente correlati all'attraversamento del preordine di un albero. Di seguito è riportata l'implementazione ricorsivo dell'attraversamento del preordine:
procedure preorder(treeNode v)
{
visit(v);
for each child u of v
preorder(u);
}
{
visit(v);
for each child u of v
preorder(u);
}
Per trasformarlo in un algoritmo di attraversamento del graph, sostituisci "figlio" con "vicino". Ma per evitare loop infiniti, tieni traccia dei vertici che sono già stati scoperti e non rivisitarli.
procedure dfs(vertex v)
{
visit(v);
for each neighbor u of v
if u is undiscovered
call dfs(u);
}
{
visit(v);
for each neighbor u of v
if u is undiscovered
call dfs(u);
}
L'algoritmo ricorsivo può essere implementato come segue in C++, Java e Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include <iostream> #include <vector> using namespace std; // Struttura dei dati per memorizzare un bordo del graph struct Edge { int src, dest; }; // Una classe per rappresentare un oggetto graph class Graph { public: // un vector di vector per rappresentare una lista di adiacenze vector<vector<int>> adjList; // Costruttore di grafici Graph(vector<Edge> const &edges, int n) { // ridimensiona il vector per contenere `n` elementi di tipo `vector<int>` adjList.resize(n); // aggiunge bordi al graph non orientato for (auto &edge: edges) { adjList[edge.src].push_back(edge.dest); adjList[edge.dest].push_back(edge.src); } } }; // Funzione per eseguire l'attraversamento DFS sul graph su un graph void DFS(Graph const &graph, int v, vector<bool> &discovered) { // contrassegna il nodo corrente come rilevato discovered[v] = true; // stampa il nodo corrente cout << v << " "; // fare per ogni arco (v, u) for (int u: graph.adjList[v]) { // se `u` non è stato ancora scoperto if (!discovered[u]) { DFS(graph, u, discovered); } } } int main() { // vector degli spigoli del grafi come nel diagramma sopra vector<Edge> edges = { // Nota che il nodo 0 non è connesso {1, 2}, {1, 7}, {1, 8}, {2, 3}, {2, 6}, {3, 4}, {3, 5}, {8, 9}, {8, 12}, {9, 10}, {9, 11} }; // numero totale di nodi nel graph (etichettato da 0 a 12) int n = 13; // costruisci un graph dai bordi dati Graph graph(edges, n); // per tenere traccia del rilevamento o meno di un vertice vector<bool> discovered(n); // Esegui l'attraversamento DFS da tutti i nodi sconosciuti a // copre tutte le componenti connesse di un graph for (int i = 0; i < n; i++) { if (discovered[i] == false) { DFS(graph, i, discovered); } } return 0; } |
Risultato:
0 1 2 3 4 5 6 7 8 9 10 11 12
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
import java.util.ArrayList; import java.util.Arrays; import java.util.List; // Una classe per memorizzare un bordo del graph class Edge { int source, dest; public Edge(int source, int dest) { this.source = source; this.dest = dest; } } // Una classe per rappresentare un oggetto graph class Graph { // Un elenco di elenchi per rappresentare un elenco di adiacenze List<List<Integer>> adjList = null; // Costruttore Graph(List<Edge> edges, int n) { adjList = new ArrayList<>(); for (int i = 0; i < n; i++) { adjList.add(new ArrayList<>()); } // aggiunge bordi al graph non orientato for (Edge edge: edges) { int src = edge.source; int dest = edge.dest; adjList.get(src).add(dest); adjList.get(dest).add(src); } } } class Main { // Funzione per eseguire l'attraversamento DFS sul graph su un graph public static void DFS(Graph graph, int v, boolean[] discovered) { // contrassegna il nodo corrente come rilevato discovered[v] = true; // stampa il nodo corrente System.out.print(v + " "); // fare per ogni arco (v, u) for (int u: graph.adjList.get(v)) { // se `u` non è stato ancora scoperto if (!discovered[u]) { DFS(graph, u, discovered); } } } public static void main(String[] args) { // Elenco dei bordi del graph come nel diagramma sopra List<Edge> edges = Arrays.asList( // Nota che il nodo 0 non è connesso new Edge(1, 2), new Edge(1, 7), new Edge(1, 8), new Edge(2, 3), new Edge(2, 6), new Edge(3, 4), new Edge(3, 5), new Edge(8, 9), new Edge(8, 12), new Edge(9, 10), new Edge(9, 11) ); // numero totale di nodi nel graph (etichettato da 0 a 12) int n = 13; // costruisci un graph dai bordi dati Graph graph = new Graph(edges, n); // per tenere traccia del rilevamento o meno di un vertice boolean[] discovered = new boolean[n]; // Esegui l'attraversamento DFS da tutti i nodi sconosciuti a // copre tutte le componenti connesse di un graph for (int i = 0; i < n; i++) { if (!discovered[i]) { DFS(graph, i, discovered); } } } } |
Risultato:
0 1 2 3 4 5 6 7 8 9 10 11 12
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
# Una classe per rappresentare un oggetto graph class Graph: # Costruttore def __init__(self, edges, n): # Un elenco di elenchi per rappresentare un elenco di adiacenze self.adjList = [[] for _ in range(n)] # aggiunge archi al grafo non orientato for (src, dest) in edges: self.adjList[src].append(dest) self.adjList[dest].append(src) # Funzione per eseguire l'attraversamento DFS sul graph su un graph def DFS(graph, v, discovered): discovered[v] = True # contrassegna il nodo corrente come rilevato print(v, end=' ') # stampa il nodo corrente # fare per ogni arco (v, u) for u in graph.adjList[v]: if not discovered[u]: # se `u` non è stato ancora scoperto DFS(graph, u, discovered) if __name__ == '__main__': # Elenco dei bordi del graph come da diagramma sopra edges = [ # Si noti che il nodo 0 non è connesso (1, 2), (1, 7), (1, 8), (2, 3), (2, 6), (3, 4), (3, 5), (8, 9), (8, 12), (9, 10), (9, 11) ] # numero totale di nodi nel graph (etichettato da 0 a 12) n = 13 # costruisce un graph dagli archi dati graph = Graph(edges, n) # per tenere traccia del rilevamento o meno di un vertice discovered = [False] * n # Esegue l'attraversamento DFS da tutti i nodi non rilevati a # copre tutti i componenti collegati di un graph for i in range(n): if not discovered[i]: DFS(graph, i, discovered) |
Risultato:
0 1 2 3 4 5 6 7 8 9 10 11 12
La complessità temporale dell'attraversamento DFS è O(V + E), dove V e E sono rispettivamente il numero totale di vertici e archi nel graph. Si prega di notare che O(E) può variare tra O(1) e O(V2), a seconda della densità del graph.
Implementazione iterativa di DFS
L'implementazione non ricorsivo di DFS è simile a implementazione non ricorsivo di BFS ma differisce da esso in due modi:
Di seguito è riportato il programma C++, Java e Python che lo dimostra:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
#include <iostream> #include <stack> #include <vector> using namespace std; // Struttura dei dati per memorizzare un bordo del graph struct Edge { int src, dest; }; // Una classe per rappresentare un oggetto graph class Graph { public: // un vector di vector per rappresentare una lista di adiacenze vector<vector<int>> adjList; // Costruttore di grafici Graph(vector<Edge> const &edges, int n) { // ridimensiona il vector per contenere `n` elementi di tipo `vector<int>` adjList.resize(n); // aggiunge bordi al graph non orientato for (auto &edge: edges) { adjList[edge.src].push_back(edge.dest); adjList[edge.dest].push_back(edge.src); } } }; // Esegue DFS iterativo sul graph a partire dal vertice `v` void iterativeDFS(Graph const &graph, int v, vector<bool> &discovered) { // crea uno stack utilizzato per eseguire DFS iterativi stack<int> stack; // inserisce il nodo di origine nello stack stack.push(v); // ciclo finché lo stack non è vuoto while (!stack.empty()) { // Estrarre un vertice dalla stack v = stack.top(); stack.pop(); // se il vertice è già stato scoperto, // ignoralo if (discovered[v]) { continue; } // arriveremo qui se il vertice spuntato `v` non è stato ancora scoperto; // stampa `v` ed elabora i suoi nodi adiacenti non scoperti nello stack discovered[v] = true; cout << v << " "; // fare per ogni arco (v, u) // stiamo usando l'iteratore inverso (perché?) for (auto it = graph.adjList[v].rbegin(); it != graph.adjList[v].rend(); it++) { int u = *it; if (!discovered[u]) { stack.push(u); } } } } int main() { // vector degli spigoli del grafi come nel diagramma sopra vector<Edge> edges = { // Nota che il nodo 0 non è connesso {1, 2}, {1, 7}, {1, 8}, {2, 3}, {2, 6}, {3, 4}, {3, 5}, {8, 9}, {8, 12}, {9, 10}, {9, 11} // {6, 9} introduces a cycle }; // numero totale di nodi nel graph (etichettato da 0 a 12) int n = 13; // costruisci un graph dai bordi dati Graph graph(edges, n); // per tenere traccia del rilevamento o meno di un vertice vector<bool> discovered(n); // Esegui un attraversamento DFS iterativo da tutti i nodi sconosciuti a // copre tutte le componenti connesse di un graph for (int i = 0; i < n; i++) { if (discovered[i] == false) { iterativeDFS(graph, i, discovered); } } return 0; } |
Risultato:
0 1 2 3 4 5 6 7 8 9 10 11 12
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Stack; // Una classe per memorizzare un bordo del graph class Edge { int source, dest; public Edge(int source, int dest) { this.source = source; this.dest = dest; } } // Una classe per rappresentare un oggetto graph class Graph { // Un elenco di elenchi per rappresentare un elenco di adiacenze List<List<Integer>> adjList = null; // Costruttore Graph(List<Edge> edges, int n) { adjList = new ArrayList<>(); for (int i = 0; i < n; i++) { adjList.add(new ArrayList<>()); } // aggiunge bordi al graph non orientato for (Edge edge: edges) { int src = edge.source; int dest = edge.dest; adjList.get(src).add(dest); adjList.get(dest).add(src); } } } class Main { // Esegue DFS iterativo sul graph a partire dal vertice `v` public static void iterativeDFS(Graph graph, int v, boolean[] discovered) { // crea uno stack utilizzato per eseguire DFS iterativi Stack<Integer> stack = new Stack<>(); // inserisce il nodo di origine nello stack stack.push(v); // ciclo finché lo stack non è vuoto while (!stack.empty()) { // Estrarre un vertice dalla stack v = stack.pop(); // se il vertice è già stato scoperto, ignoralo if (discovered[v]) { continue; } // arriveremo qui se il vertice spuntato `v` non è stato ancora scoperto; // stampa `v` ed elabora i suoi nodi adiacenti non scoperti nello stack discovered[v] = true; System.out.print(v + " "); // fare per ogni arco (v, u) List<Integer> adjList = graph.adjList.get(v); for (int i = adjList.size() - 1; i >= 0; i--) { int u = adjList.get(i); if (!discovered[u]) { stack.push(u); } } } } public static void main(String[] args) { // Elenco dei bordi del graph come nel diagramma sopra List<Edge> edges = Arrays.asList( // Nota che il nodo 0 non è connesso new Edge(1, 2), new Edge(1, 7), new Edge(1, 8), new Edge(2, 3), new Edge(2, 6), new Edge(3, 4), new Edge(3, 5), new Edge(8, 9), new Edge(8, 12), new Edge(9, 10), new Edge(9, 11) // (6, 9) introduce un ciclo ); // numero totale di nodi nel graph (etichettato da 0 a 12) int n = 13; // costruisci un graph dai bordi dati Graph graph = new Graph(edges, n); // per tenere traccia del rilevamento o meno di un vertice boolean[] discovered = new boolean[n]; // Esegui un attraversamento DFS iterativo da tutti i nodi sconosciuti a // copre tutte le componenti connesse di un graph for (int i = 0; i < n; i++) { if (!discovered[i]) { iterativeDFS(graph, i, discovered); } } } } |
Risultato:
0 1 2 3 4 5 6 7 8 9 10 11 12
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
from collections import deque # Una classe per rappresentare un oggetto graph class Graph: # Costruttore def __init__(self, edges, n): # Un elenco di elenchi per rappresentare un elenco di adiacenze self.adjList = [[] for _ in range(n)] # aggiunge archi al grafo non orientato for (src, dest) in edges: self.adjList[src].append(dest) self.adjList[dest].append(src) # Esegue DFS iterativo sul graph a partire dal vertice `v` def iterativeDFS(graph, v, discovered): # crea uno stack utilizzato per eseguire DFS iterativi stack = deque() # inserisce il nodo di origine nello stack stack.append(v) # loop fino a quando lo stack è vuoto while stack: # Estrarre un vertice dallo stack v = stack.pop() # se il vertice è già stato scoperto, ignoralo if discovered[v]: continue # raggiungeremo qui se il vertice spuntato `v` non è stato ancora scoperto; # stampa `v` ed elabora i suoi nodi adiacenti non scoperti nello stack discovered[v] = True print(v, end=' ') # fare per ogni arco (v, u) adjList = graph.adjList[v] for i in reversed(range(len(adjList))): u = adjList[i] if not discovered[u]: stack.append(u) if __name__ == '__main__': # Elenco dei bordi del graph come da diagramma sopra edges = [ # Si noti che il nodo 0 non è connesso (1, 2), (1, 7), (1, 8), (2, 3), (2, 6), (3, 4), (3, 5), (8, 9), (8, 12), (9, 10), (9, 11) # (6, 9) introduce un ciclo ] # numero totale di nodi nel graph (etichettato da 0 a 12) n = 13 # costruisce un graph dagli archi dati graph = Graph(edges, n) # per tenere traccia del rilevamento o meno di un vertice discovered = [False] * n # Esegue l'attraversamento DFS iterativo da tutti i nodi non rilevati a # copre tutti i componenti collegati di un graph for i in range(n): if not discovered[i]: iterativeDFS(graph, i, discovered) |
Risultato:
0 1 2 3 4 5 6 7 8 9 10 11 12
Applicazioni di DFS
- Trovare componenti collegati in un graph.
- Cernita topologico in un DAG (graph aciclico diretto).
- Trovare componenti collegati a 2/3 (bordo o vertice).
- Trovare il ponti di un graph.
- Trovare componenti fortemente connessi.
- Risolvere enigmi con una sola soluzione, come i labirinti.
- Trovare la biconnettività nei graficici e molti altri…
Vedi anche:
Deep First Search (DFS) – Domande del colloquio e problemi pratici
Riferimenti: https://www.ics.uci.edu/~eppstein/161/960215.html