algorithm
Búsqueda de amplitud
Buscar..
Encontrar el camino más corto desde la fuente a otros nodos
La búsqueda en primer lugar (BFS) es un algoritmo para atravesar o buscar estructuras de datos de árboles o gráficos. Comienza en la raíz del árbol (o en algún nodo arbitrario de un gráfico, a veces denominado "clave de búsqueda") y explora los nodos vecinos primero, antes de pasar al siguiente nivel de vecinos. BFS fue inventado a fines de la década de 1950 por Edward Forrest Moore , quien lo usó para encontrar el camino más corto para salir de un laberinto y fue descubierto por CY Lee como un algoritmo de enrutamiento de cables en 1961.
Los procesos del algoritmo BFS funcionan bajo estas suposiciones:
- No atravesaremos ningún nodo más de una vez.
- El nodo de origen o el nodo desde el que comenzamos se encuentra en el nivel 0.
- Los nodos a los que podemos acceder directamente desde el nodo fuente son los nodos del nivel 1, los nodos a los que podemos acceder directamente desde los nodos del nivel 1 son los nodos del nivel 2 y así sucesivamente.
- El nivel denota la distancia del camino más corto desde la fuente.
Veamos un ejemplo: 
Supongamos que este gráfico representa la conexión entre varias ciudades, donde cada nodo denota una ciudad y un borde entre dos nodos indica que hay una carretera que los une. Queremos ir del nodo 1 al nodo 10 . Entonces el nodo 1 es nuestra fuente , que es el nivel 0 . Marcamos el nodo 1 como visitado. Podemos ir al nodo 2 , nodo 3 y nodo 4 desde aquí. Así que estarán a nivel (0 + 1) = nodos de nivel 1 . Ahora los marcaremos como visitados y trabajaremos con ellos.
Se visitan los nodos de colores. Los nodos con los que estamos trabajando actualmente se marcarán con rosa. No visitaremos el mismo nodo dos veces. Desde el nodo 2 , el nodo 3 y el nodo 4 , podemos ir al nodo 6, nodo 7 y nodo 8 . Vamos a marcarlos como visitados. El nivel de estos nodos será nivel (1 + 1) = nivel 2 . 
Si no lo ha notado, el nivel de los nodos simplemente denota la distancia de ruta más corta desde la fuente . Por ejemplo: hemos encontrado el nodo 8 en el nivel 2 . Entonces la distancia desde la fuente al nodo 8 es 2 .
Aún no llegamos a nuestro nodo objetivo, ese es el nodo 10 . Así que visitemos los próximos nodos. Podemos ir directamente desde el nodo 6 , nodo 7 y nodo 8 . 
Podemos ver que encontramos el nodo 10 en el nivel 3 . Así que la ruta más corta desde la fuente hasta el nodo 10 es 3. Buscamos el nivel del gráfico por nivel y encontramos la ruta más corta. Ahora vamos a borrar los bordes que no usamos: 
Después de eliminar los bordes que no usamos, obtenemos un árbol llamado árbol BFS. Este árbol muestra la ruta más corta desde la fuente a todos los demás nodos.
Así que nuestra tarea será, ir desde la fuente hasta los nodos del nivel 1 . Luego, desde los nodos del nivel 1 al nivel 2, etc., hasta que lleguemos a nuestro destino. Podemos usar la cola para almacenar los nodos que vamos a procesar. Es decir, para cada nodo con el que vamos a trabajar, empujaremos a todos los demás nodos que puedan atravesarse directamente y que aún no estén en la cola.
La simulación de nuestro ejemplo:
Primero empujamos la fuente en la cola. Nuestra cola se verá como:
front
+-----+
| 1 |
+-----+
El nivel del nodo 1 será 0. nivel [1] = 0 . Ahora empezamos nuestro BFS. Al principio, sacamos un nodo de nuestra cola. Conseguimos el nodo 1 . Podemos ir al nodo 4 , nodo 3 y nodo 2 desde este. Hemos llegado a estos nodos desde el nodo 1 . Entonces nivel [4] = nivel [3] = nivel [2] = nivel [1] + 1 = 1 . Ahora los marcamos como visitados y los empujamos en la cola.
front
+-----+ +-----+ +-----+
| 2 | | 3 | | 4 |
+-----+ +-----+ +-----+
Ahora abrimos el nodo 4 y trabajamos con él. Podemos ir al nodo 7 desde el nodo 4 . nivel [7] = nivel [4] + 1 = 2 . Marcamos el nodo 7 como visitado y lo colocamos en la cola.
front
+-----+ +-----+ +-----+
| 7 | | 2 | | 3 |
+-----+ +-----+ +-----+
Desde el nodo 3 , podemos ir al nodo 7 y al nodo 8 . Como ya hemos marcado el nodo 7 como visitado, marcamos el nodo 8 como visitado, cambiamos el nivel [8] = nivel [3] + 1 = 2 . Empujamos el nodo 8 en la cola.
front
+-----+ +-----+ +-----+
| 6 | | 7 | | 2 |
+-----+ +-----+ +-----+
Este proceso continuará hasta que lleguemos a nuestro destino o la cola se vacíe. La matriz de nivel nos proporcionará la distancia de la ruta más corta desde la fuente . Podemos inicializar la matriz de nivel con un valor infinito , lo que marcará que los nodos aún no se han visitado. Nuestro pseudo-código será:
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
Al iterar a través de la matriz de niveles , podemos averiguar la distancia de cada nodo desde la fuente. Por ejemplo: la distancia del nodo 10 a la fuente se almacenará en el nivel [10] .
A veces es posible que tengamos que imprimir no solo la distancia más corta, sino también la ruta a través de la cual podemos ir a nuestro nodo destinado desde la fuente . Para esto necesitamos mantener una matriz padre . padre [fuente] será NULL. Para cada actualización en la matriz de nivel , simplemente agregaremos parent[v] := u en nuestro pseudo código dentro del bucle for. Después de finalizar BFS, para encontrar la ruta, volveremos a recorrer la matriz principal hasta que lleguemos a la fuente, que se denotará con el valor NULL. El pseudocódigo será:
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
Complejidad:
Hemos visitado cada nodo una vez y todos los bordes una vez. Entonces, la complejidad será O (V + E) donde V es el número de nodos y E es el número de bordes.
Encontrar la ruta más corta desde la fuente en un gráfico 2D
La mayoría de las veces, necesitaremos encontrar la ruta más corta desde una sola fuente a todos los demás nodos o un nodo específico en un gráfico 2D. Por ejemplo, queremos saber cuántos movimientos se requieren para que un caballero alcance un cierto cuadrado en un tablero de ajedrez, o tenemos una matriz donde algunas celdas están bloqueadas, tenemos que encontrar el camino más corto de una celda a otra . Podemos movernos solo horizontal y verticalmente. Incluso los movimientos diagonales pueden ser posibles también. Para estos casos, podemos convertir los cuadrados o celdas en nodos y resolver estos problemas fácilmente usando BFS. Ahora nuestro visitado , padre y nivel serán matrices 2D. Para cada nodo, consideraremos todos los movimientos posibles. Para encontrar la distancia a un nodo específico, también verificaremos si hemos llegado a nuestro destino.
Habrá una cosa adicional llamada matriz de dirección. Esto simplemente almacenará todas las combinaciones posibles de direcciones a las que podemos ir. Digamos, para movimientos horizontales y verticales, nuestras matrices de dirección serán:
+----+-----+-----+-----+-----+
| dx | 1 | -1 | 0 | 0 |
+----+-----+-----+-----+-----+
| dy | 0 | 0 | 1 | -1 |
+----+-----+-----+-----+-----+
Aquí dx representa el movimiento en el eje x y dy representa el movimiento en el eje y. Nuevamente esta parte es opcional. También puedes escribir todas las combinaciones posibles por separado. Pero es más fácil manejarlo usando la matriz de dirección. Puede haber más e incluso diferentes combinaciones para movimientos diagonales o movimientos de caballero.
La parte adicional que debemos tener en cuenta es:
- Si alguna de las celdas está bloqueada, para cada movimiento posible, verificaremos si la celda está bloqueada o no.
- También comprobaremos si nos hemos salido de los límites, es decir, hemos cruzado los límites de la matriz.
- Se dará el número de filas y columnas.
Nuestro pseudo-código será:
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
Como hemos discutido anteriormente, BFS solo funciona para gráficos no ponderados. Para gráficos ponderados, necesitaremos el algoritmo de Dijkstra . Para los ciclos de borde negativo, necesitamos el algoritmo de Bellman-Ford . Nuevamente este algoritmo es el algoritmo de ruta más corta de una sola fuente. Si necesitamos encontrar la distancia de cada nodo a todos los demás nodos, necesitaremos el algoritmo de Floyd-Warshall .
Componentes conectados de un gráfico no dirigido utilizando BFS.
BFS se puede usar para encontrar los componentes conectados de un gráfico no dirigido . También podemos encontrar si el gráfico dado está conectado o no. Nuestra discusión posterior asume que estamos tratando con gráficos no dirigidos. La definición de un gráfico conectado es:
Un gráfico está conectado si hay una ruta entre cada par de vértices.
A continuación se muestra un gráfico conectado .
El siguiente gráfico no está conectado y tiene 2 componentes conectados:
- Componente conectado 1: {a, b, c, d, e}
- Componente conectado 2: {f}
BFS es un algoritmo de recorrido gráfico. Entonces, a partir de un nodo de origen aleatorio, si al finalizar el algoritmo, se visitan todos los nodos, entonces el gráfico está conectado, de lo contrario no está conectado.
PseudoCódigo para el algoritmo.
boolean isConnected(Graph g)
{
BFS(v)//v is a random source node.
if(allVisited(g))
{
return true;
}
else return false;
}
Implementación de C para encontrar si un gráfico no dirigido está conectado o no:
#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';
}
}
}
Para encontrar todos los componentes conectados de un gráfico no dirigido, solo necesitamos agregar 2 líneas de código a la función BFS. La idea es llamar a la función BFS hasta que se visiten todos los vértices.
Las líneas a añadir son:
printf("\nConnected component %d\n",++count);
//count is a global variable initialized to 0
//add this as first line to BFS function
Y
printf("%d ",vertex+1);
add this as first line of while loop in BFS
Y definimos la siguiente función:
void listConnectedComponents(char **graph,int noOfVertices)
{
int i;
for(i = 0;i < noOfVertices;++i)
{
if(visited[i] == 'N')
BFS(graph,i,noOfVertices);
}
}