Soluzione: Ricerca in Profondità (Depth-First Search)
Complessità: $\Theta(V + E)$
Si prenda come esempio il grafo nell'immagine sotto a sinistra, con la sua rappresentazione in memoria illustrata sulla destra (si veda [2] per ulteriori info sulla rappresentazione dei grafi).
La ricerca in profondità è chiamata così perché "percorre" il grafo esaminando ricorsivamente varie liste di adiacenza in cerca di quei vertici che hanno lista di adiacenza vuota (nessun vertice collegato) per poi risalire la ricorsione e "svuotare" le liste di adiacenza esaminate fino a quel momento, arrivando così ad una nuova lista di adiacenza vuota che segnala che un altro vertice (quello associato alla nuova lista "vuota") è stato trovato.
Prendendo come esempio il grafo rappresentato nell'immagine sopra e seguendo i passaggi indicati dalle immagini sotto, partendo dal vertice $1$ (in modo del tutto arbitrario) la lista di adiacenza associata dice che il primo vertice collegato ad $1$ è $2$. Si va quindi a controllare la lista di adiacenza del vertice $2$, il cui primo elemento è il vertice $5$. Si va nella lista di adiacenza del vertice $5$ ed il primo elemento è il vertice $3$. Il primo elemento della lista di adiacenza del vertice $3$ è il vertice $4$. Si va nella lista di adiacenza del vertice $4$ e si scopre che è vuota. Si può segnare il vertice $4$ come scoperto (immagine A sotto; Nota: i vertici grigi e le frecce in grassetto indicano il genitore del vertice segnato o, se si preferisce, il vertice relativo alla lista di adiacenza che si stava esaminando in precedenza e che ci ha portato al vertice corrente con lista vuota. Inoltre, i vertici segnati vengono inseriti in uno stack in modo che i primi ad essere segnati stiano alla fine della pila, proprio come prevede l'ordinamento topologico).
Il vertice $4$, dunque, non ha vertici collegati ad esso ed è stato segnato, quindi ora anche la lista di adiacenza del vertice $3$ si può considerare vuota (il vertice $4$ è stato ormai processato). Prima di arrivare alla lista di adiacenza del vertice $4$ eravamo nella lista di adiacenza del vertice $3$ che, a questo punto, può essere segnato anch'esso (immagine B sotto).
Prima di arrivare alla lista di adiacenza del vertice $3$ eravamo nella lista di adiacenza del vertice $5$ che, pur avendo adesso un vertice in meno (il vertice $3$), ha ancora il vertice $6$ come elemento della lista. Si va nella lista di adiacenza del vertice $6$ e si scopre che è vuota. Si può segnare il vertice $6$ come scoperto (immagine C sotto).
Prima di arrivare alla lista di adiacenza del vertice $6$ eravamo nella lista di adiacenza del vertice $5$ che, a questo punto, non ha più elementi e può essere segnato anch'esso (immagine D sotto).
Prima di arrivare alla lista di adiacenza del vertice $5$ eravamo nella lista di adiacenza del vertice $2$ che, a questo punto, non ha più elementi e può essere segnato anch'esso (immagine E sotto).
Prima di arrivare alla lista di adiacenza del vertice $2$ eravamo nella lista di adiacenza del vertice $1$ che, a questo punto, non ha più elementi e può essere segnato anch'esso (immagine F sotto).
In questo modo, alla fine della ricerca, si potrebbe pensare che quello che si ottiene è un albero ma non è così. Se il grafo non è collegato quello che si ottiene è una foresta (detta foresta DF) che conterrà tanti alberi quanti sono le parti non collegate del grafo.
L'uso più frequente delle ricerche in profondità è quella di ordinare degli eventi dipendenti o, comunque, di risolvere le dipendenze tra alcuni oggetti. L'ordinamento topologico, ritornato da una ricerca in profondità, prevede che se esiste un arco orientato $u \longrightarrow v$, che va dal vertice $u$ al vertice $v$, $u$ venga prima di $v$ o, se si preferisce, $u$ dipende da $v$. Ed infatti, seguendo l'algoritmo illustrato in precedenza, $v$ viene scoperto prima di $u$ ed inserito in uno stack in modo che si trovi dopo $u$ quando questo verrà segnato.
#include <iostream> #include <deque> struct Vertex { Vertex *parent; unsigned int index; bool traced; }; struct Edge { Vertex *head; Vertex *tail; Edge *next; }; void dfs(Edge**, size_t, std::deque<Vertex*>&); void dfs_visit(Edge**, size_t, std::deque<Vertex*>&); void print_vector(std::deque<Vertex*>&); int main(int argc, char* argv[], char* env[]) { Vertex v1{ nullptr, 1, false }; Vertex v2{ nullptr, 2, false }; Vertex v3{ nullptr, 3, false }; Vertex v4{ nullptr, 4, false }; Vertex v5{ nullptr, 5, false }; Vertex v6{ nullptr, 6, false }; Vertex *v[7] = { nullptr, &v1, &v2, &v3, &v4, &v5, &v6 }; Edge *graph[7] = { nullptr }; Edge e1_25{ v[1], v[5], nullptr }; Edge e1_12{ v[1], v[2], &e1_25 }; graph[1] = &e1_12; Edge e2_53{ v[2], v[3], nullptr }; Edge e2_25{ v[2], v[5], &e2_53 }; graph[2] = &e2_25; Edge e3_34{ v[3], v[4], nullptr }; graph[3] = &e3_34; Edge e4_4{ v[4], nullptr, nullptr }; graph[4] = &e4_4; Edge e5_36{ v[5], v[6], nullptr }; Edge e5_53{ v[5], v[3], &e5_36 }; graph[5] = &e5_53; Edge e6_6{ v[6], nullptr, nullptr }; graph[6] = &e6_6; size_t size = sizeof(graph) / sizeof(Vertex*); std::deque<Vertex*> v_vec; dfs(graph, size, v_vec); print_vector(v_vec); return 0; } void dfs(Edge **g, size_t size, std::deque<Vertex*>& dec) { for (size_t i = 1; i < size; ++i) { // condizione vera tante volte quanti sono i vertici scollegati del grafo if (!g[i]->head->traced) dfs_visit(g, i, dec); } } void dfs_visit(Edge **g, size_t i, std::deque<Vertex*>& dec) { Edge *e = g[i]; while (e != nullptr) { if (e->tail) // vera se vertice ha lista di adiacenza { if (e->tail->traced == false) { // imposta il padre per "ricordarsi" come risalire le liste di adiacenza. // in realtà è intrinseco nella ricorsione ricordarsi come risalire. // di fatto serve solo a tener traccia del cammino tra vertice corrente e sorgente qualora si volesse stamparlo e->tail->parent = e->head; dfs_visit(g, e->tail->index, dec); } } else // vertice non ha lista di adiacenza (vuota sin dall'inizio) { e->head->traced = true; dec.push_front(e->head); } // vertice ha lista di adiacenza vuota adesso e può essere segnato e inserito sullo stack if (e->tail && e->next == nullptr) { e->head->traced = true; dec.push_front(e->head); } e = e->next; } } void print_vector(std::deque< Vertex* > &d) { auto end = d.end(); for (auto i = d.begin(); i != end; ++i) std::cout << (*i)->index << ((end - i > 1) ? " --> " : ""); }
Riferimenti:
[1] Introduzione agli algoritmi e strutture dati - Cormen, Leiserson, Rivest, Stein
[2] Rappresentazione dei grafi attraverso strutture dati
Nessun commento:
Posta un commento