In una precedente discussione abbiamo trattato la ricerca in ampiezza in un grafo ( Guida - Algoritmo BFS per grafi ); oggi, come avevo già preannunciato in quel thread, andremo a parlare della ricerca in profondità (DFS).
È un algoritmo abbastanza interessante dato che, al contrario del BFS, è progettato per essere implementato in modo ricorsivo. In realtà, possiamo implementare una versione iterativa utilizzando come struttura ausiliaria la pila (struttura LIFO).
Implementazione
Partendo da un nodo X, andremo ad esaminare tutti i prossimi nodi u di esso. Se viene trovato un nuovo nodo, ci si sposta in esso. Se vi si trovano vertici già scoperti, si torna indietro. Questo procedimento va ripetuto finché tutti i nodi non vengono esaminati.
Per vedere se un nodo è stato visitato o meno si possono usare due strade diverse:
La ricerca in profondità utilizza due marcatempi che permettono di individuare quali passi compie la ricerca: d (nodo GRIGIO) e f (nodo NERO).
La complessità di suddetto algoritmo è O(|V|+|E|) ove V è il numero dei vertici e E il numero degli archi.
Pseudo codice
Questa è la pseudo codifica ricorsiva dell'algoritmo e inoltre non identifica un nodo di partenza della ricerca (parte dal primo per default).
Codifica
Ricorsiva
Iterativa
Un esempio di caricamento della lista potrebbe essere:
Un esempio di esecuzione del programma potrebbe essere questa:
L'esempio che abbiano eseguito è quello della gif postata sopra. Come potete veder, l'output non è ordinato, ma dai marcatempi vi si può vedere l'ordine della ricerca (primo, secondo).
La compilazione del programma deve avvenire con il flag -std=c++11.
La guida è finita, spero di esservi stato d'aiuto
È un algoritmo abbastanza interessante dato che, al contrario del BFS, è progettato per essere implementato in modo ricorsivo. In realtà, possiamo implementare una versione iterativa utilizzando come struttura ausiliaria la pila (struttura LIFO).
Implementazione
Partendo da un nodo X, andremo ad esaminare tutti i prossimi nodi u di esso. Se viene trovato un nuovo nodo, ci si sposta in esso. Se vi si trovano vertici già scoperti, si torna indietro. Questo procedimento va ripetuto finché tutti i nodi non vengono esaminati.
Per vedere se un nodo è stato visitato o meno si possono usare due strade diverse:
- array di valori booleani (true se è stato visitato in precedenza; false se ancora no);
- array di valori interi con tre stati: BIANCO => non visitato; GRIGIO => in visita; NERO => già visitato).
La ricerca in profondità utilizza due marcatempi che permettono di individuare quali passi compie la ricerca: d (nodo GRIGIO) e f (nodo NERO).
La complessità di suddetto algoritmo è O(|V|+|E|) ove V è il numero dei vertici e E il numero degli archi.
Pseudo codice
Questa è la pseudo codifica ricorsiva dell'algoritmo e inoltre non identifica un nodo di partenza della ricerca (parte dal primo per default).
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Codifica
Ricorsiva
C++:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Iterativa
C++:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Un esempio di caricamento della lista potrebbe essere:
C++:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Un esempio di esecuzione del programma potrebbe essere questa:
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
La compilazione del programma deve avvenire con il flag -std=c++11.
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
La guida è finita, spero di esservi stato d'aiuto
Ultima modifica: