algorithm
Larghezza prima ricerca
Ricerca…
Trovare il percorso più breve dalla sorgente ad altri nodi
La breadth-first-search (BFS) è un algoritmo per attraversare o perquisire strutture dati di alberi o grafici. Inizia dalla radice dell'albero (o da qualche nodo arbitrario di un grafico, a volte indicato come "chiave di ricerca") ed esplora prima i nodi vicini, prima di passare ai vicini di livello successivo. BFS fu inventato alla fine degli anni '50 da Edward Forrest Moore , che lo utilizzò per trovare il percorso più breve da un labirinto e scoperto in modo indipendente da CY Lee come un algoritmo di routing del filo nel 1961.
I processi dell'algoritmo BFS funzionano secondo questi presupposti:
- Non attraverseremo alcun nodo più di una volta.
- Il nodo di origine o il nodo da cui stiamo iniziando si trova nel livello 0.
- I nodi che possiamo raggiungere direttamente dal nodo sorgente sono i nodi di livello 1, i nodi che possiamo raggiungere direttamente dai nodi di livello 1 sono i nodi di livello 2 e così via.
- Il livello indica la distanza del percorso più breve dalla sorgente.
Vediamo un esempio: 
Supponiamo che questo grafico rappresenti la connessione tra più città, in cui ciascun nodo denota una città e un margine tra due nodi denota che esiste una strada che li collega. Vogliamo andare dal nodo 1 al nodo 10 . Quindi il nodo 1 è la nostra fonte , che è il livello 0 . Contrassegniamo il nodo 1 come visitato. Possiamo andare al nodo 2 , al nodo 3 e al nodo 4 da qui. Quindi saranno livello (0 + 1) = livello 1 nodi. Ora li contrassegneremo come visitati e lavoreremo con loro.
I nodi colorati sono visitati. I nodi con cui stiamo lavorando verranno contrassegnati in rosa. Non visiteremo lo stesso nodo due volte. Dal nodo 2 , nodo 3 e nodo 4 , possiamo andare al nodo 6, al nodo 7 e al nodo 8 . Marciamoli come visitati. Il livello di questi nodi sarà livello (1 + 1) = livello 2 . 
Se non l'hai notato, il livello dei nodi indica semplicemente la distanza del percorso più breve dalla sorgente . Ad esempio: abbiamo trovato il nodo 8 al livello 2 . Quindi la distanza dalla sorgente al nodo 8 è 2 .
Non abbiamo ancora raggiunto il nostro nodo di destinazione, ovvero il nodo 10 . Quindi visitiamo i prossimi nodi. possiamo andare direttamente dal nodo 6 , dal nodo 7 e dal nodo 8 . 
Possiamo vedere che abbiamo trovato il nodo 10 al livello 3 . Così il percorso più breve dalla sorgente al nodo 10 è 3. Abbiamo cercato il livello grafico per livello e abbiamo trovato il percorso più breve. Ora cancelliamo i bordi che non abbiamo usato: 
Dopo aver rimosso i bordi che non abbiamo usato, otteniamo un albero chiamato albero BFS. Questo albero mostra il percorso più breve dalla sorgente a tutti gli altri nodi.
Quindi il nostro compito sarà, passare dai nodi sorgente a quelli di livello 1 . Quindi dai nodi di livello 1 a livello 2 e così via fino a raggiungere la nostra destinazione. Possiamo usare la coda per memorizzare i nodi che elaboreremo. Cioè, per ogni nodo con cui lavoreremo, spingeremo tutti gli altri nodi che possono essere attraversati direttamente e non ancora attraversati nella coda.
La simulazione del nostro esempio:
Per prima cosa inseriamo il codice sorgente nella coda. La nostra coda sarà simile a:
front
+-----+
| 1 |
+-----+
Il livello del nodo 1 sarà 0. livello [1] = 0 . Ora iniziamo il nostro BFS. All'inizio, facciamo scoppiare un nodo dalla nostra coda. Otteniamo il nodo 1 . Possiamo andare al nodo 4 , al nodo 3 e al nodo 2 da questo. Abbiamo raggiunto questi nodi dal nodo 1 . Quindi livello [4] = livello [3] = livello [2] = livello [1] + 1 = 1 . Ora li contrassegniamo come visitati e li mettiamo in coda.
front
+-----+ +-----+ +-----+
| 2 | | 3 | | 4 |
+-----+ +-----+ +-----+
Ora inseriamo il nodo 4 e lavoriamo con esso. Possiamo andare al nodo 7 dal nodo 4 . livello [7] = livello [4] + 1 = 2 . Contrassegniamo il nodo 7 come visitato e lo inseriamo nella coda.
front
+-----+ +-----+ +-----+
| 7 | | 2 | | 3 |
+-----+ +-----+ +-----+
Dal nodo 3 , possiamo andare al nodo 7 e al nodo 8 . Poiché abbiamo già contrassegnato il nodo 7 come visitato, contrassegniamo il nodo 8 come visitato, cambiamo il livello [8] = livello [3] + 1 = 2 . Spingiamo il nodo 8 nella coda.
front
+-----+ +-----+ +-----+
| 6 | | 7 | | 2 |
+-----+ +-----+ +-----+
Questo processo continuerà finché non raggiungiamo la nostra destinazione o la coda diventa vuota. L'array di livelli ci fornirà la distanza del percorso più breve dalla fonte . Possiamo inizializzare l'array di livelli con valore infinito , che segnerà che i nodi non sono ancora stati visitati. Il nostro pseudo-codice sarà:
Procedure BFS(Graph, source):
Q = queue();
level[] = infinity
level[source] := 0
Q.push(source)
while Q is not empty
u -> Q.pop()
for all edges from u to v in Adjacency list
if level[v] == infinity
level[v] := level[u] + 1
Q.push(v)
end if
end for
end while
Return level
Attraverso l'iterazione attraverso l'array di livelli , possiamo scoprire la distanza di ogni nodo dalla sorgente. Ad esempio: la distanza del nodo 10 dalla sorgente verrà memorizzata nel livello [10] .
A volte potremmo aver bisogno di stampare non solo la distanza più breve, ma anche il percorso attraverso il quale possiamo andare al nostro nodo destinato dalla sorgente . Per questo abbiamo bisogno di mantenere un array di genitori . genitore [fonte] sarà NULL. Per ogni aggiornamento nell'array di livelli , aggiungeremo semplicemente parent[v] := u nel nostro pseudo codice all'interno del ciclo for. Dopo aver terminato BFS, per trovare il percorso, attraverseremo l'array genitore fino a raggiungere la fonte che sarà indicata dal valore NULL. Lo pseudo-codice sarà:
Procedure PrintPath(u): //recursive | Procedure PrintPath(u): //iterative
if parent[u] is not equal to null | S = Stack()
PrintPath(parent[u]) | while parent[u] is not equal to null
end if | S.push(u)
print -> u | u := parent[u]
| end while
| while S is not empty
| print -> S.pop
| end while
Complessità:
Abbiamo visitato ogni nodo una sola volta per volta. Quindi la complessità sarà O (V + E) dove V è il numero di nodi ed E è il numero di spigoli.
Trovare il percorso più breve dalla sorgente in un grafico 2D
La maggior parte delle volte, dovremo trovare il percorso più breve da una singola fonte a tutti gli altri nodi o un nodo specifico in un grafico 2D. Per esempio: vogliamo scoprire quanti movimenti sono necessari per un cavaliere per raggiungere un certo quadrato in una scacchiera, o abbiamo un array dove alcune celle sono bloccate, dobbiamo trovare il percorso più breve da una cella all'altra . Possiamo muoverci solo orizzontalmente e verticalmente. Anche le mosse diagonali possono essere possibili. In questi casi, possiamo convertire i quadrati o le celle nei nodi e risolvere facilmente questi problemi usando BFS. Ora il nostro visitato , genitore e livello saranno array 2D. Per ogni nodo, prenderemo in considerazione tutte le mosse possibili. Per trovare la distanza da un nodo specifico, controlleremo anche se abbiamo raggiunto la nostra destinazione.
Ci sarà una cosa aggiuntiva chiamata array di direzione. Questo semplicemente memorizzerà tutte le possibili combinazioni di direzioni che possiamo raggiungere. Diciamo che, per le mosse orizzontali e verticali, i nostri array di direzione saranno:
+----+-----+-----+-----+-----+
| dx | 1 | -1 | 0 | 0 |
+----+-----+-----+-----+-----+
| dy | 0 | 0 | 1 | -1 |
+----+-----+-----+-----+-----+
Qui dx rappresenta lo spostamento nell'asse xe dy rappresenta lo spostamento nell'asse y. Di nuovo questa parte è facoltativa. Puoi anche scrivere separatamente tutte le possibili combinazioni. Ma è più facile da gestire usando l'array di direzione. Possono esserci più combinazioni, anche diverse, per mosse diagonali o mosse di cavalieri.
La parte aggiuntiva che dobbiamo tenere a mente è:
- Se una qualsiasi delle celle è bloccata, per ogni possibile mossa, controlleremo se la cella è bloccata o meno.
- Controlleremo anche se siamo andati fuori limite, cioè abbiamo superato i confini dell'array.
- Sarà dato il numero di righe e colonne.
Il nostro pseudo-codice sarà:
Procedure BFS2D(Graph, blocksign, row, column):
for i from 1 to row
for j from 1 to column
visited[i][j] := false
end for
end for
visited[source.x][source.y] := true
level[source.x][source.y] := 0
Q = queue()
Q.push(source)
m := dx.size
while Q is not empty
top := Q.pop
for i from 1 to m
temp.x := top.x + dx[i]
temp.y := top.y + dy[i]
if temp is inside the row and column and top doesn't equal to blocksign
visited[temp.x][temp.y] := true
level[temp.x][temp.y] := level[top.x][top.y] + 1
Q.push(temp)
end if
end for
end while
Return level
Come abbiamo discusso in precedenza, BFS funziona solo per i grafici non pesati. Per i grafici ponderati, avremo bisogno dell'algoritmo di Dijkstra . Per i cicli negativi di bordo, abbiamo bisogno dell'algoritmo di Bellman-Ford . Anche in questo caso, questo algoritmo è l'algoritmo del percorso più breve della singola origine. Se abbiamo bisogno di scoprire la distanza da ciascun nodo a tutti gli altri nodi, avremo bisogno dell'algoritmo di Floyd-Warshall .
Connected Components Of Undirected Graph utilizzando BFS.
BFS può essere utilizzato per trovare i componenti collegati di un grafico non orientato . Possiamo anche scoprire se il dato grafico è collegato o meno. La nostra discussione successiva presuppone che abbiamo a che fare con grafici non orientati. La definizione di un grafico connesso è:
Un grafico è connesso se c'è un percorso tra ogni coppia di vertici.
Di seguito è riportato un grafico collegato .
Il seguente grafico non è connesso e ha 2 componenti collegati:
- Connected Component 1: {a, b, c, d, e}
- Connected Component 2: {f}
BFS è un algoritmo di attraversamento grafico. Quindi, partendo da un nodo di origine casuale, se alla fine dell'algoritmo vengono visitati tutti i nodi, allora il grafico è connesso, altrimenti non è connesso.
PseudoCode per l'algoritmo.
boolean isConnected(Graph g)
{
BFS(v)//v is a random source node.
if(allVisited(g))
{
return true;
}
else return false;
}
Implementazione C per scoprire se un grafo non orientato è connesso o meno:
#include<stdio.h>
#include<stdlib.h>
#define MAXVERTICES 100
void enqueue(int);
int deque();
int isConnected(char **graph,int noOfVertices);
void BFS(char **graph,int vertex,int noOfVertices);
int count = 0;
//Queue node depicts a single Queue element
//It is NOT a graph node.
struct node
{
int v;
struct node *next;
};
typedef struct node Node;
typedef struct node *Nodeptr;
Nodeptr Qfront = NULL;
Nodeptr Qrear = NULL;
char *visited;//array that keeps track of visited vertices.
int main()
{
int n,e;//n is number of vertices, e is number of edges.
int i,j;
char **graph;//adjacency matrix
printf("Enter number of vertices:");
scanf("%d",&n);
if(n < 0 || n > MAXVERTICES)
{
fprintf(stderr, "Please enter a valid positive integer from 1 to %d",MAXVERTICES);
return -1;
}
graph = malloc(n * sizeof(char *));
visited = malloc(n*sizeof(char));
for(i = 0;i < n;++i)
{
graph[i] = malloc(n*sizeof(int));
visited[i] = 'N';//initially all vertices are not visited.
for(j = 0;j < n;++j)
graph[i][j] = 0;
}
printf("enter number of edges and then enter them in pairs:");
scanf("%d",&e);
for(i = 0;i < e;++i)
{
int u,v;
scanf("%d%d",&u,&v);
graph[u-1][v-1] = 1;
graph[v-1][u-1] = 1;
}
if(isConnected(graph,n))
printf("The graph is connected");
else printf("The graph is NOT connected\n");
}
void enqueue(int vertex)
{
if(Qfront == NULL)
{
Qfront = malloc(sizeof(Node));
Qfront->v = vertex;
Qfront->next = NULL;
Qrear = Qfront;
}
else
{
Nodeptr newNode = malloc(sizeof(Node));
newNode->v = vertex;
newNode->next = NULL;
Qrear->next = newNode;
Qrear = newNode;
}
}
int deque()
{
if(Qfront == NULL)
{
printf("Q is empty , returning -1\n");
return -1;
}
else
{
int v = Qfront->v;
Nodeptr temp= Qfront;
if(Qfront == Qrear)
{
Qfront = Qfront->next;
Qrear = NULL;
}
else
Qfront = Qfront->next;
free(temp);
return v;
}
}
int isConnected(char **graph,int noOfVertices)
{
int i;
//let random source vertex be vertex 0;
BFS(graph,0,noOfVertices);
for(i = 0;i < noOfVertices;++i)
if(visited[i] == 'N')
return 0;//0 implies false;
return 1;//1 implies true;
}
void BFS(char **graph,int v,int noOfVertices)
{
int i,vertex;
visited[v] = 'Y';
enqueue(v);
while((vertex = deque()) != -1)
{
for(i = 0;i < noOfVertices;++i)
if(graph[vertex][i] == 1 && visited[i] == 'N')
{
enqueue(i);
visited[i] = 'Y';
}
}
}
Per trovare tutti i componenti Connected di un grafo non orientato, abbiamo solo bisogno di aggiungere 2 linee di codice alla funzione BFS. L'idea è di chiamare la funzione BFS fino a quando tutti i vertici sono visitati.
Le linee da aggiungere sono:
printf("\nConnected component %d\n",++count);
//count is a global variable initialized to 0
//add this as first line to BFS function
E
printf("%d ",vertex+1);
add this as first line of while loop in BFS
e definiamo la seguente funzione:
void listConnectedComponents(char **graph,int noOfVertices)
{
int i;
for(i = 0;i < noOfVertices;++i)
{
if(visited[i] == 'N')
BFS(graph,i,noOfVertices);
}
}
