BFS en Español: Guía completa para principiantes
Este artículo fue publicado por el autor Editores el 09/02/2025 y actualizado el 09/02/2025. Esta en la categoria Artículos.
¡Bienvenidos a nuestra guía completa sobre el Algoritmo de Búsqueda en Amplitud (BFS) en español! Si eres un principiante en el mundo de la computación y la programación, este artículo es para ti. En este artículo, te explicaremos en detalle qué es el algoritmo de BFS, cómo funciona, y cómo implementarlo en diferentes lenguajes de programación.
¿Qué es el Algoritmo de Búsqueda en Amplitud (BFS)?
El Algoritmo de Búsqueda en Amplitud (BFS) es un algoritmo de búsqueda no informada que se utiliza para recorrer y buscar nodos en un grafo o árbol. El algoritmo de BFS se basa en el principio de "anchura primero", es decir, se exploran todos los nodos de un nivel antes de pasar al siguiente nivel.
El algoritmo de BFS utiliza una cola para almacenar los nodos que se van a explorar. Primero, se agrega el nodo inicial a la cola. Después, se extrae el nodo de la cola y se marca como visitado. Luego, se agrega a la cola todos los nodos adyacentes al nodo extraído que aún no han sido visitados. Este proceso se repite hasta que se hayan visitado todos los nodos del grafo o árbol.
¿Cómo funciona el Algoritmo de BFS?
Veamos un ejemplo sencillo para entender mejor cómo funciona el algoritmo de BFS. Imagine un grafo con cinco nodos (A, B, C, D, E) y las siguientes conexiones:
- A y B están conectados
- A y C están conectados
- B y D están conectados
- C y E están conectados
El proceso de BFS en este grafo sería el siguiente:
- Se agrega el nodo A a la cola y se marca como visitado.
- Se extrae el nodo A de la cola y se agrega sus nodos adyacentes (B y C) a la cola.
- Se extrae el nodo B de la cola y se agrega su nodo adyacente (D) a la cola.
- Se extrae el nodo C de la cola y se agrega su nodo adyacente (E) a la cola.
- Se extraen los nodos D y E de la cola y se marcan como visitados.
El algoritmo de BFS ha visitado todos los nodos del grafo.
Implementación del Algoritmo de BFS en Python
Veamos ahora cómo implementar el algoritmo de BFS en Python. Supongamos que tenemos el siguiente grafo representado como una matriz de adyacencia:
graph = [ [0, 1, 1, 0, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 1], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0]]
La implementación del algoritmo de BFS en Python sería la siguiente:
python from collections import deque
def bfs(graph, start): visited = [] queue = deque([start])
while queue: node = queue.popleft() if node not in visited: visited.append(node) for neighbor in graph[node]: if neighbor not in visited: queue.append(neighbor)return visitedLa función bfs toma como entrada el grafo y el nodo inicial. Devuelve una lista de todos los nodos visitados en orden de búsqueda.
Implementación del Algoritmo de BFS en Java
La implementación del algoritmo de BFS en Java es similar a la de Python. Supongamos que tenemos el siguiente grafo representado como una lista de listas de enteros:
javaList<List<Integer>> graph = new ArrayList<>();graph.add(Arrays.asList(0, 1, 1, 0, 0));graph.add(Arrays.asList(1, 0, 0, 1, 0));graph.add(Arrays.asList(1, 0, 0, 0, 1));graph.add(Arrays.asList(0, 1, 0, 0, 0));graph.add(Arrays.asList(0, 0, 1, 0, 0));
La implementación del algoritmo de BFS en Java sería la siguiente:
java import java.util.ArrayDeque; import java.util.ArrayList; import java.util.List;
public class BFS {
public static List<Integer> bfs(List<List<Integer>> graph, int start) { boolean[] visited = new boolean[graph.size()]; ArrayDeque<Integer> queue = new ArrayDeque<>(); queue.offer(start); visited[start] = true; while (!queue.isEmpty()) { int node = queue.poll(); if (!visited[node]) { visited[node] = true; for (int neighbor : graph.get(node)) {
Deja un comentario