Primera búsqueda en amplitud (BFS) es un fundamental algoritmo de recorrido de gráfico . Implica visitar todos los nodos conectados de un gráfico nivel por nivel. En este artículo analizaremos el concepto de BFS y cómo se puede aplicar a gráficos de manera efectiva
Tabla de contenidos
- Primera búsqueda en amplitud o BFS para un gráfico
- Relación entre BFS para Graph y BFS para Tree
- Búsqueda en amplitud (BFS) para un algoritmo gráfico
- ¿Cómo funciona el algoritmo BFS?
- Implementación de BFS para Graph usando la lista de adyacencia
- Complejidad del algoritmo de búsqueda en amplitud (BFS)
- Aplicaciones de BFS en gráficos
- Problemas en la búsqueda en amplitud o BFS para un gráfico
- Preguntas frecuentes sobre la búsqueda en amplitud (BFS) para un gráfico
Búsqueda en amplitud (BFS) para un gráfico:
Primera búsqueda en amplitud (BFS) es un algoritmo de recorrido de gráfico que explora todos los vértices de un gráfico en la profundidad actual antes de pasar a los vértices en el siguiente nivel de profundidad. Comienza en un vértice específico y visita a todos sus vecinos antes de pasar al siguiente nivel de vecinos. BFS se usa comúnmente en algoritmos para búsqueda de rutas, componentes conectados y problemas de ruta más corta en gráficos.
Relación entre BFS para Graph y BFS para Tree:
El recorrido primero en amplitud (BFS) para un gráfico es similar al Recorrido primero en amplitud de un árbol .
El único inconveniente aquí es que, a diferencia de árboles , graficos puede contener ciclos, por lo que podemos llegar al mismo nodo nuevamente. Para evitar procesar un nodo más de una vez, dividimos los vértices en dos categorías:
- visitado y
- No visitado.
Se utiliza una matriz booleana visitada para marcar los vértices visitados. Por simplicidad, se supone que todos los vértices son accesibles desde el vértice inicial. BFS usos a Búsqueda en amplitud (BFS) para un algoritmo gráfico:
Analicemos el algoritmo para BFS:
- Inicialización: Coloque el nodo inicial en una cola y márquelo como visitado.
- Exploración: Mientras la cola no esté vacía:
- Retire un nodo de la cola y visítelo (por ejemplo, imprima su valor).
- Para cada vecino no visitado del nodo retirado de la cola:
- Coloque al vecino en la cola.
- Marcar al vecino como visitado.
- Terminación: Repita el paso 2 hasta que la cola esté vacía.
Este algoritmo garantiza que todos los nodos del gráfico se visiten primero en amplitud, comenzando desde el nodo inicial.
mientras y hacer bucle while en java
¿Cómo funciona el algoritmo BFS?
Comenzando desde la raíz, primero se visitan todos los nodos de un nivel particular y luego se atraviesan los nodos del siguiente nivel hasta visitar todos los nodos.
Para ello se utiliza una cola. Todos los nodos adyacentes no visitados del nivel actual se colocan en la cola y los nodos del nivel actual se marcan como visitados y se retiran de la cola.
Ilustración:
Entendamos el funcionamiento del algoritmo con la ayuda del siguiente ejemplo.
Paso 1: Inicialmente, la cola y las matrices visitadas están vacías.
La cola y las matrices visitadas están vacías inicialmente.
Paso 2: Empuje el nodo 0 a la cola y márquelo como visitado.
Empuje el nodo 0 a la cola y márquelo como visitado.
Paso 3: Elimine el nodo 0 del frente de la cola, visite a los vecinos no visitados y empújelos a la cola.
Elimine el nodo 0 del frente de la cola y visite a los vecinos no visitados y póngalos en la cola.
Etapa 4: Elimine el nodo 1 del frente de la cola, visite a los vecinos no visitados y empújelos a la cola.
Elimine el nodo 1 del frente de la cola y visite a los vecinos no visitados y presione
Paso 5: Elimine el nodo 2 del frente de la cola, visite a los vecinos no visitados y empújelos a la cola.
Elimine el nodo 2 del frente de la cola, visite a los vecinos no visitados y empújelos a la cola.
Paso 6: Elimine el nodo 3 del frente de la cola, visite a los vecinos no visitados y empújelos a la cola.
Como podemos ver, se visitan todos los vecinos del nodo 3, así que pase al siguiente nodo que está al frente de la cola.Elimine el nodo 3 del frente de la cola, visite a los vecinos no visitados y empújelos a la cola.
Pasos 7: Elimine el nodo 4 del frente de la cola, visite a los vecinos no visitados y empújelos a la cola.
Como podemos ver, todos los vecinos del nodo 4 son visitados, así que pase al siguiente nodo que está al frente de la cola.Elimine el nodo 4 del frente de la cola, visite a los vecinos no visitados y empújelos a la cola.
Ahora, la cola queda vacía, por lo tanto, finalice este proceso de iteración.
Implementación de BFS para Graph usando Lista de Adyacencia:
C++ #include #include #include using namespace std; // Function to perform Breadth First Search on a graph // represented using adjacency list void bfs(vector>& adjList, int inicioNodo, vector & visitado) { // Crear una cola para la cola BFS q; // Marca el nodo actual como visitado y ponlo en cola visitado[startNode] = true; q.push(startNode); // Iterar sobre la cola while (!q.empty()) { // Quitar un vértice de la cola e imprimirlo int currentNode = q.front(); q.pop(); corte<< currentNode << ' '; // Get all adjacent vertices of the dequeued vertex // currentNode If an adjacent has not been visited, // then mark it visited and enqueue it for (int neighbor : adjList[currentNode]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } } // Function to add an edge to the graph void addEdge(vector>& adjList, int u, int v) { adjList[u].push_back(v); } int main() { // Número de vértices en el gráfico int vertices = 5; // Representación de lista de adyacencia del vector gráfico> adjList(vértices); // Agrega aristas al gráfico addEdge(adjList, 0, 1); agregarBorde(adjList, 0, 2); agregarBorde(adjList, 1, 3); agregarBorde(adjList, 1, 4); agregarBorde(adjList, 2, 4); // Marca todos los vértices como vector no visitado visitado(vértices, falso); // Realiza un recorrido BFS comenzando desde el vértice 0 cout<< 'Breadth First Traversal starting from vertex ' '0: '; bfs(adjList, 0, visited); return 0; }>
C #include #include #define MAX_VERTICES 100 // Structure to represent a node in adjacency list struct Node { int data; struct Node* next; }; // Function to create a new node struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->datos = datos; nuevoNodo->siguiente = NULL; devolver nuevoNodo; } // Función para agregar un borde al gráfico void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v); nuevoNodo->siguiente = adjList[u]; adjList[u] = nuevoNodo; } // Función para realizar una búsqueda en amplitud en un gráfico // representado usando la lista de adyacencia void bfs(struct Node* adjList[], int vertices, int startNode, int visited[]) { // Crea una cola para BFS int queue[ MAX_VERTICES]; int frente = 0, trasero = 0; // Marca el nodo actual como visitado y ponlo en cola visitado[startNode] = 1; cola[trasero++] = startNode; // Iterar sobre la cola while (front != rear) { // Quitar un vértice de la cola e imprimirlo int currentNode = queue[front++]; printf('%d ', nodoactual); // Obtener todos los vértices adyacentes del vértice retirado de la cola // currentNode Si un adyacente no ha sido visitado, // márquelo como visitado y póngalo en cola struct Node* temp = adjList[currentNode]; while (temp! = NULL) { int vecino = temp->datos; if (!visitado[vecino]) { visitado[vecino] = 1; cola[trasero++] = vecino; } temperatura = temperatura->siguiente; } } } int main() { // Número de vértices en el gráfico int vertices = 5; // Representación de la lista de adyacencia del gráfico struct Node* adjList[vertices]; para (int i = 0; i< vertices; ++i) adjList[i] = NULL; // Add edges to the graph addEdge(adjList, 0, 1); addEdge(adjList, 0, 2); addEdge(adjList, 1, 3); addEdge(adjList, 1, 4); addEdge(adjList, 2, 4); // Mark all the vertices as not visited int visited[vertices]; for (int i = 0; i < vertices; ++i) visited[i] = 0; // Perform BFS traversal starting from vertex 0 printf( 'Breadth First Traversal starting from vertex 0: '); bfs(adjList, vertices, 0, visited); return 0; }> Java import java.util.LinkedList; import java.util.Queue; // Class to represent a graph using adjacency list class Graph { int vertices; LinkedList [] listaadj; @SuppressWarnings('unchecked') Graph(int vertices) { this.vertices = vertices; adjList = nueva ListaEnlazada[vértices]; para (int i = 0; i< vertices; ++i) adjList[i] = new LinkedList(); } // Function to add an edge to the graph void addEdge(int u, int v) { adjList[u].add(v); } // Function to perform Breadth First Search on a graph // represented using adjacency list void bfs(int startNode) { // Create a queue for BFS Queue cola = nueva ListaEnlazada(); booleano[] visitado = nuevo booleano[vértices]; // Marca el nodo actual como visitado y ponlo en cola visitado[startNode] = true; cola.add(startNode); // Iterar sobre la cola while (!queue.isEmpty()) { // Quitar un vértice de la cola e imprimirlo int currentNode = queue.poll(); System.out.print(currentNode + ' '); // Obtener todos los vértices adyacentes del // vértice currentNode retirado de la cola Si un adyacente // no ha sido visitado, márquelo como visitado y // pongalo en cola for (int vecino: adjList[currentNode]) { if (!visited[neighbor] ) { visitado[vecino] = verdadero; cola.add(vecino); } } } } } public class Main { public static void main(String[] args) { // Número de vértices en el gráfico int vertices = 5; // Crear un gráfico Gráfico gráfico = nuevo Gráfico(vértices); // Agrega bordes al gráfico graph.addEdge(0, 1); gráfico.addEdge(0, 2); gráfico.addEdge(1, 3); gráfico.addEdge(1, 4); gráfico.addEdge(2, 4); // Realizar recorrido BFS comenzando desde el vértice 0 System.out.print( 'Primer recorrido de amplitud comenzando desde el vértice 0: '); gráfico.bfs(0); } }> Python3 from collections import deque # Function to perform Breadth First Search on a graph # represented using adjacency list def bfs(adjList, startNode, visited): # Create a queue for BFS q = deque() # Mark the current node as visited and enqueue it visited[startNode] = True q.append(startNode) # Iterate over the queue while q: # Dequeue a vertex from queue and print it currentNode = q.popleft() print(currentNode, end=' ') # Get all adjacent vertices of the dequeued vertex # If an adjacent has not been visited, then mark it visited and enqueue it for neighbor in adjList[currentNode]: if not visited[neighbor]: visited[neighbor] = True q.append(neighbor) # Function to add an edge to the graph def addEdge(adjList, u, v): adjList[u].append(v) def main(): # Number of vertices in the graph vertices = 5 # Adjacency list representation of the graph adjList = [[] for _ in range(vertices)] # Add edges to the graph addEdge(adjList, 0, 1) addEdge(adjList, 0, 2) addEdge(adjList, 1, 3) addEdge(adjList, 1, 4) addEdge(adjList, 2, 4) # Mark all the vertices as not visited visited = [False] * vertices # Perform BFS traversal starting from vertex 0 print('Breadth First Traversal starting from vertex 0:', end=' ') bfs(adjList, 0, visited) if __name__ == '__main__': main()> C# using System; using System.Collections.Generic; // Class to represent a graph using adjacency list class Graph { int vertices; List [] listaadj; gráfico público (int vértices) { this.vertices = vértices; adjList = nueva lista [ vértices ]; para (int i = 0; i< vertices; ++i) adjList[i] = new List (); } // Función para agregar un borde al gráfico public void AddEdge(int u, int v) { adjList[u].Add(v); } // Función para realizar una búsqueda en amplitud en un gráfico // representado usando la lista de adyacencia public void BFS(int startNode) { // Crea una cola para BFS Queue cola = nueva cola (); bool[] visitado = nuevo bool[vértices]; // Marca el nodo actual como visitado y ponlo en cola visitado[startNode] = true; cola.Enqueue(startNode); // Iterar sobre la cola while (queue.Count != 0) { // Quitar un vértice de la cola e imprimirlo int currentNode = queue.Dequeue(); Console.Write(currentNode + ' '); // Obtener todos los vértices adyacentes del // vértice currentNode retirado de la cola Si un adyacente // no ha sido visitado, márquelo como visitado y // pongalo en cola foreach(int vecino in adjList[currentNode]) { if (!visited[neighbor] ) { visitado[vecino] = verdadero; queue.Enqueue(vecino); } } } } } class MainClass { public static void Main(string[] args) { // Número de vértices en el gráfico int vertices = 5; // Crear un gráfico Gráfico gráfico = nuevo Gráfico(vértices); // Agrega bordes al gráfico graph.AddEdge(0, 1); gráfico.AddEdge(0, 2); gráfico.AddEdge(1, 3); gráfico.AddEdge(1, 4); gráfico.AddEdge(2, 4); // Realizar recorrido BFS comenzando desde el vértice 0 Console.Write( 'Primer recorrido de amplitud comenzando desde el vértice 0: '); gráfico.BFS(0); } }> JavaScript // Class to represent a graph using adjacency list class Graph { constructor() { this.adjList = {}; } // Function to add an edge to the graph addEdge(u, v) { if (!this.adjList[u]) this.adjList[u] = []; this.adjList[u].push(v); } // Function to perform Breadth First Search on a graph represented using adjacency list bfs(startNode) { // Create a queue for BFS const queue = []; const visited = new Array(Object.keys(this.adjList).length).fill(false); // Mark the current node as visited and enqueue it visited[startNode] = true; queue.push(startNode); // Iterate over the queue while (queue.length !== 0) { // Dequeue a vertex from queue and print it const currentNode = queue.shift(); console.log(currentNode + ' '); // Get all adjacent vertices of the dequeued vertex currentNode // If an adjacent has not been visited, then mark it visited and enqueue it for (const neighbor of this.adjList[currentNode] || []) { if (!visited[neighbor]) { visited[neighbor] = true; queue.push(neighbor); } } } } } // Create a graph const graph = new Graph(); // Add edges to the graph graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 3); graph.addEdge(1, 4); graph.addEdge(2, 4); // Perform BFS traversal starting from vertex 0 console.log('Breadth First Traversal starting from vertex 0: '); graph.bfs(0);> Producción
Breadth First Traversal starting from vertex 0: 0 1 2 3 4>
Complejidad del tiempo: O(V+E), donde V es el número de nodos y E es el número de aristas.
Espacio Auxiliar: O(V)
Análisis de complejidad del algoritmo de búsqueda en amplitud (BFS):
Complejidad temporal del algoritmo BFS: O (V + E)
- BFS explora todos los vértices y aristas del gráfico. En el peor de los casos, visita cada vértice y arista una vez. Por lo tanto, la complejidad temporal de BFS es O (V + E), donde V y E son el número de vértices y aristas en el gráfico dado.
Complejidad espacial del algoritmo BFS: O (V)
- BFS utiliza una cola para realizar un seguimiento de los vértices que deben visitarse. En el peor de los casos, la cola puede contener todos los vértices del gráfico. Por lo tanto, la complejidad espacial de BFS es O (V), donde V y E son el número de vértices y aristas en el gráfico dado.
Aplicaciones de BFS en gráficos:
BFS tiene varias aplicaciones en teoría de grafos e informática, que incluyen:
- Búsqueda de ruta más corta: BFS se puede utilizar para encontrar el camino más corto entre dos nodos en un gráfico no ponderado. Al realizar un seguimiento del padre de cada nodo durante el recorrido, se puede reconstruir el camino más corto.
- Detección de ciclo: BFS se puede utilizar para detectar ciclos en un gráfico. Si un nodo se visita dos veces durante el recorrido, indica la presencia de un ciclo.
- Componentes conectados: BFS se puede utilizar para identificar componentes conectados en un gráfico. Cada componente conectado es un conjunto de nodos a los que se puede llegar entre sí.
- Clasificación topológica: BFS se puede utilizar para realizar una clasificación topológica en un gráfico acíclico dirigido (DAG). La clasificación topológica organiza los nodos en un orden lineal de modo que para cualquier arista (u, v), u aparece antes de v en el orden.
- Recorrido de orden de nivel de árboles binarios: BFS se puede utilizar para realizar un recorrido de orden de nivel de un árbol binario. Este recorrido visita todos los nodos en el mismo nivel antes de pasar al siguiente nivel.
- Enrutamiento de red: BFS se puede utilizar para encontrar la ruta más corta entre dos nodos en una red, lo que lo hace útil para enrutar paquetes de datos en protocolos de red.
Problemas en la búsqueda en amplitud o BFS para un gráfico:
| S.no | Problemas | Práctica |
|---|---|---|
| 1. | Encuentre el nivel de un nodo determinado en un gráfico no dirigido | Enlace |
| 2. | Minimizar la diferencia adyacente máxima en una ruta de arriba a la izquierda a abajo a la derecha | Enlace |
| 10. | Compruebe si se puede acceder al destino de una matriz determinada con los valores requeridos de celdas | Enlace |
Preguntas frecuentes sobre la búsqueda en amplitud (BFS) para un gráfico:
Pregunta 1: ¿Qué es BFS y cómo funciona?
Respuesta: BFS es un algoritmo de recorrido de gráficos que explora sistemáticamente un gráfico visitando todos los vértices en un nivel determinado antes de pasar al siguiente nivel. Comienza desde un vértice inicial, lo coloca en una cola y lo marca como visitado. Luego, retira un vértice de la cola, lo visita y coloca en la cola a todos sus vecinos no visitados. Este proceso continúa hasta que la cola esté vacía.
Pregunta 2: ¿Cuáles son las aplicaciones de BFS?
Respuesta: BFS tiene varias aplicaciones, incluida la búsqueda del camino más corto en un gráfico no ponderado, la detección de ciclos en un gráfico, la clasificación topológica de un gráfico acíclico dirigido (DAG), la búsqueda de componentes conectados en un gráfico y la resolución de acertijos como laberintos y Sudoku.
Pregunta 3: ¿Cuál es la complejidad temporal de BFS?
Respuesta: La complejidad temporal de BFS es O (V + E), donde V es el número de vértices y E es el número de aristas en el gráfico.
Pregunta 4: ¿Cuál es la complejidad espacial de BFS?
Respuesta: La complejidad espacial de BFS es O (V), ya que utiliza una cola para realizar un seguimiento de los vértices que deben visitarse.
Pregunta 5: ¿Cuáles son las ventajas de utilizar BFS?
Respuesta: BFS es sencillo de implementar y eficaz para encontrar el camino más corto en un gráfico no ponderado. También garantiza que se visiten todos los vértices del gráfico.
diagrama uml java
Artículos relacionados:
- Artículos recientes sobre BFS
- Primer recorrido en profundidad
- Aplicaciones del primer recorrido en amplitud
- Aplicaciones de la búsqueda en profundidad
- Complejidad temporal y espacial de la búsqueda en amplitud (BFS)