Búsqueda primero en amplitud (BFS)
BFS (búsqueda primero en amplitud, búsqueda primero en amplitud) - un método transversal de gráfico, usado muy a menudo en algoritmos simples y avanzados. La búsqueda primero en amplitud funciona recorriendo los niveles individuales del gráfico, comenzando en el nodo de origen y alejándose gradualmente de él. Esto se muestra claramente en la animación.
Para escribir el BFS más simple, debe poder trabajar con una estructura de datos que le permita tomar desde el principio y ponerlo hasta el final, y también poder almacenar el gráfico en forma de lista de adyacencia (es decir, con una cola).
Descripción formal del algoritmo
1) Coloque el número del vértice desde el que comienza la búsqueda en la cola inicialmente vacía.
2) Extraiga el vértice U del principio de la cola y márquelo como usado en una matriz separada.
3) Al final de la cola, agregar todos los vértices que podamos alcanzar usando el borde del vértice U, y que aún no estén etiquetados.
4) Si la cola está vacía, entonces se escanearon todos los nodos del gráfico conectado; de lo contrario, regrese al paso 2.
Complejidad
Dado que el algoritmo visita todos los nodos del gráfico en el peor de los casos, al almacenar el gráfico como listas de adyacencia, la complejidad temporal del algoritmo es O(|V| + |E|) , donde V es el conjunto de vértices del gráfico y E es el conjunto de aristas. En otras palabras, el algoritmo funciona en el peor de los casos para number de aristas + número de vértices.
|
BFS (búsqueda primero en amplitud) es un método de recorrido de gráficos, que se usa con mucha frecuencia en algoritmos simples y avanzados. La búsqueda primero en amplitud funciona recorriendo los niveles individuales del gráfico, comenzando en el nodo de origen y alejándose gradualmente de él. Esto se muestra claramente en la animación.
Para escribir un BFS simple, debe poder trabajar con una cola, una estructura de datos que le permita tomar desde el principio y ponerlo hasta el final, y también poder almacenar un gráfico en el formulario de una lista de adyacencia.
Descripción formal del algoritmo
1) Coloque el número del vértice desde el que comienza la búsqueda en la cola inicialmente vacía.
2) Extraiga el vértice U del principio de la cola y márquelo como usado en una matriz separada.
3) Al final de la cola, agregar todos los vértices que podemos alcanzar usando el borde del vértice U y que aún no están marcados.
4) Si la cola está vacía, entonces se escanearon todos los nodos del gráfico conectado; de lo contrario, regrese al paso 2.
Dificultad de trabajo
Dado que, en el peor de los casos, el algoritmo visita todos los nodos del grafo, al almacenar el grafo en forma de listas de adyacencia, la complejidad temporal del algoritmo es O(|V| + |E|), donde V es el conjunto de vértices del grafo, y E es el conjunto de aristas. ;
En otras palabras, el algoritmo funciona en el peor de los casos para el número de aristas + el número de vértices.
|
Para restaurar las rutas más cortas, cree una matriz de "ancestros" \(p[]\) , en el que, para cada vértice, almacena el número del vértice por el que golpeamos este vértice.
|