Grafi: Ricerca in Ampiezza (Breadth-First Search)

Problema: Dato un grafo $G = (V, E)$ (con $|V|$ vertici ed $|E|$ archi) non pesato e non orientato e dato uno dei suoi vertici $v$ (detto vertice sorgente), trovare tutti cammini minimi che partono da $v$ ed arrivano ad ognuno dei vertici raggiungibili da $v$.

Soluzione: Ricerca in Ampiezza (Breadth-First Search)
Complessità: $O(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 ampiezza è chiamata così perché "scopre" prima tutti i vertici che si trovano ad una stessa distanza dal vertice sorgente prima di passare a vertici che hanno distanza maggiore. Ad esempio, partendo dal vertice sorgente, che ha distanza pari a $0$ da se stesso, l'algoritmo calcola prima tutti i vertici a distanza $1$ prima di passare a calcolare quelli a distanza $2$, e così via. A questo scopo viene usata una coda che tiene traccia dei vertici collegati al vertice corrente in modo che vengano scoperti tutti prima di passare a vertici a distanze maggiori.

L'algoritmo è relativamente semplice. Si parte inizializzando gli attributi dei vertici di $G$ prima o all'inizio dell'algoritmo. In particolare, le distanze dal vertice sorgente vengono impostate ad un valore che non ha significato o ad un valore molto grande (come $-1$ assegnato ad una variabile unsigned). Inoltre ogni genitore viene impostato a null e la sentinella che indica la "scoperta" del vertice da parte dell'algoritmo viene impostata a false.
Prima di entrare nel ciclo che processa i vertici di $G$ si imposta sentinella e distanza del vertice sorgente (il vertice $1$ nell'immagine A sotto) a true e $0$ (rispettivamente) e accodando il vertice alla coda. Si entra ora in un ciclo che si conclude solo quando la coda si svuota. Alla prima iterazione del ciclo (immagine B) viene estratto un vertice dalla coda (il vertice $1$ in questo caso) e vengono scoperti i vertici $2$ e $5$ che sono gli unici collegati al vertice $1$. Per entrambi i vertici scoperti si imposta la sentinella a true, il genitore a $1$ e la distanza a $1.d + 1$ (con $1.d$ distanza del vertice $1$). Alla fine dell'iterazione i due vertici vengono accodati alla coda e saranno gli unici a distanza $1$ dal vertice $1$.
Alla seconda iterazione del ciclo (immagine C) il vertice $2$ viene estratto dalla coda ma dei vertici collegati ad esso solo il vertice $3$ non è stato scoperto quindi solo per questo si imposta la sentinella (true), il genitore ($2$) e la distanza ($2.d + 1$). E così via.
Nell'ultima iterazione (immagine E) la coda conterrà solo il vertice $6$ ma l'unico vertice collegato ad esso ($5$) era già stato scoperto quindi si estrae il vertice $6$ dalla coda e si esce dal ciclo principale dato che ora la coda è vuota.

Oltre a contenere la propria distanza dal vertice sorgente quindi, ogni vertice mantiene anche il genitore attraverso il quale si è potuto calcolare la distanza per il vertice corrente. In questo modo, alla fine della ricerca, quello che si ottiene è un albero (detto albero BF) attraverso il quale è possibile tracciare il cammino da un vertice sorgente a qualsiasi altro vertice raggiungibile da esso.

#include <iostream>
#include <queue>
 
struct Vertex
{
 Vertex *parent;
 unsigned int distance;
 unsigned int index;
 bool traced;
};
 
struct Edge
{
 Vertex *v;
 Edge *next;
};
 
void bfs(Edge**, Vertex*);
void print_path(Edge**, Vertex*, Vertex*, size_t);
 
int main(int argc, char* argv[], char* env[])
{
 Vertex v1{ nullptr, (unsigned int)-1, 1, false };
 Vertex v2{ nullptr, (unsigned int)-1, 2, false };
 Vertex v3{ nullptr, (unsigned int)-1, 3, false };
 Vertex v4{ nullptr, (unsigned int)-1, 4, false };
 Vertex v5{ nullptr, (unsigned int)-1, 5, false };
 Vertex v6{ nullptr, (unsigned int)-1, 6, false };
 
 Vertex *v[7] = { nullptr, &v1, &v2, &v3, &v4, &v5, &v6 };
 Edge *graph[7];
 
 Edge e1_25{ v[5], nullptr };
 Edge e1_12{ v[2], &e1_25 };
 graph[1] = &e1_12;
 
 Edge e2_53{ v[3], nullptr };
 Edge e2_15{ v[5], &e2_53 };
 Edge e2_21{ v[1], &e2_15 };
 graph[2] = &e2_21;
 
 Edge e3_24{ v[4], nullptr };
 Edge e3_32{ v[2], &e3_24 };
 graph[3] = &e3_32;
 
 Edge e4_43{ v[3], nullptr };
 graph[4] = &e4_43;
 
 Edge e5_26{ v[6], nullptr };
 Edge e5_12{ v[2], &e5_26 };
 Edge e5_51{ v[1], &e5_12 };
 graph[5] = &e5_51;
 
 Edge e6_65{ v[5], nullptr };
 graph[6] = &e6_65; 
 
 bfs(graph, v[1]);
 
 print_path(graph, v[1], v[4], v[4]->index);
 
 return 0;
}
 
void bfs(Edge **g, Vertex *v)
{
 v->distance = 0;
 v->traced = true;
 
 std::queue<Vertex*> v_queue;
 v_queue.push(v);
 
 while (!v_queue.empty())
 {
  Vertex *p = v_queue.front();
  v_queue.pop();
  Edge *e = g[p->index];
 
  while (e != nullptr)
  {
   if (e->v->traced == false)
   {
    e->v->traced = true;
    e->v->distance = p->distance + 1;
    e->v->parent = p;
    v_queue.push(e->v);
   }
   e = e->next;
  }
 }
}
 
void print_path(Edge **g, Vertex *s, Vertex *t, size_t index)
{
 if (t == s)
  std::cout << s->index << " --> ";
 else if (t->parent == nullptr)
  std::cout << "No path between vertices.";
 else
 {
  print_path(g, s, t->parent, index);
  std::cout << t->index << ((t->index != index) ? " --> " : "");
 }
}

Riferimenti:
[1] Introduzione agli algoritmi e strutture dati - Cormen, Leiserson, Rivest, Stein
[2] Rappresentazione dei grafi attraverso strutture dati