<
# Definimos una función para realizar la búsqueda en amplitud.
def bfs(graph, start):
# Creamos un conjunto para llevar un registro de los nodos visitados.
visited = set()
# Inicializamos una lista como cola con el nodo de inicio.
queue = [start]
while queue:
# Sacamos el primer elemento de la lista como si fuera una cola.
node = queue.pop(0)
if node not in visited:
# Imprimimos el nodo visitado (puedes hacer otra cosa con él).
print(node)
visited.add(node) # Agregamos el nodo a la lista de visitados.
# Agregamos los nodos vecinos no visitados a la cola.
for neighbour in graph[node]:
if neighbour not in visited:
queue.append(neighbour)
# Creamos un grafo representado como un diccionario de listas de adyacencia.
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# Llamamos a la función BFS desde el nodo de inicio 'A'.
bfs(graph, 'A')
>
Introducción
¿Qué es un grafo?
¿Qué es un árbol?
¿Qué es recursión?
Aplicaciones reales de grafos y árboles
Formas de representar un grafo
DFS
Análisis de DFS: algoritmo de búsqueda en profundidad
Programando DFS de forma recursiva
Otras formas de programar DFS
Recorridos y profundidad de un Árbol
Sum Root to Leaf Numbers: análisis del problema
Solución de Sum Root to Leaf Numbers
Playground: Sum Root to Leaf Numbers
Programando Sum Root to Leaf Numbers en Golang
Number of Islands: análisis del problema
Solución de Number of Islands
Playground: Number of Islands
Programando Number of Islands en Python
Ejercicios recomendados de DFS
Ejercicios resueltos de DFS
BFS
Análisis de BFS: algoritmo de búsqueda en anchura
Programando BFS con Python
Minimum Knights Moves (movimientos de caballo en ajedrez): análisis del problema
Solución de Minimum Knights Moves
Playground: Minimum Knights Moves
Programando Minimum Knights Moves con Python
Rotting Oranges: análisis del problema
Solución de Rotting Oranges
Playground: Rotting Oranges
Rotting Oranges con Java
Shortest Bridge Between Islands: análisis del problema
Solución de Shortest Bridge Between Islands
Playground: Shortest Bridge Between Islands
Programando Shortest Bridge Between Islands con Python
Ejercicios recomendados de BFS
Ejercicios resueltos de BFS
Backtrack
Algoritmo de Backtrack
Letter Combinations of a Phone Number: análisis del problema
Solución de Letter Combinations of a Phone Number
Programando Letter Combinations of a Phone Number con C++
Playground: Letter Combinations of a Phone Number
Restore IP Addresses: análisis del problema
Programando Restore IP Addresses con C++
Playground: Restore IP Addresses
Word Search: análisis del problema
Solución de Word Search
Playgrund: Word Search
Programando Word Search JavaScript
Reto: N Queens Puzzle
Ejercicios recomendados de Backtrack
Ejercicios resueltos de Backtrack
Próximos pasos
¿Qué otros algoritmos y tipos de grafos puedes aprender?
¿Quieres más cursos avanzados de algoritmos?
No tienes acceso a esta clase
¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera
Si ya tienes una cuenta,
Programando BFS con Python
21/52Recursos
¿Cómo implementar BFS para recorrer un árbol?
El algoritmo de Búsqueda en Anchura (BFS, por sus siglas en inglés) es una técnica popular para explorar o recorrer estructuras de datos, como árboles o grafos. En este caso, aprenderemos cómo implementar BFS en un árbol y cómo imprimir todos sus valores de manera eficiente utilizando colas. Este enfoque es esencial para cualquier programador y puede aplicarse en diversos lenguajes de programación.
¿Cómo se configura la función BFS?
Primero, definimos una función que llamaremos BFS, la cual recibirá como entrada el nodo raíz del árbol. El objetivo es retornar una lista con los nodos organizados en el orden que BFS precisa. Aquí está cómo se estructura:
def BFS(raiz):
if not raiz:
return [] # Si no hay raíz, simplemente retornamos una lista vacía
respuesta = [] # Lista donde guardaremos el orden de los nodos
cola = [raiz] # Iniciamos la cola con el nodo raíz
nivel = 0 # Contador de niveles del árbol
while cola: # Mientras haya elementos en la cola
nivel += 1
for _ in range(len(cola)):
nodo_actual = cola.pop(0) # Sacamos el primer elemento de la cola
# Aquí se procesa el nodo_actual si es necesario
respuesta.append(nodo_actual) # Añadimos el nodo actual a la respuesta
# Añadimos los hijos del nodo actual a la cola
for hija in nodo_actual.hijas:
cola.append(hija)
print("La cantidad de niveles de este árbol es", nivel)
return respuesta
¿Cómo se trata el recorrido del árbol por niveles?
Durante la ejecución del algoritmo, se maneja un contador de nivel que incrementa cada vez que completamos un nivel del árbol. Esto es parte fundamental para entender la profundidad del árbol recorrido por BFS.
- Inicialización de la cola: Se comienza la cola con el nodo raíz.
- Iteración por nivel: Mientras existan nodos en la cola, se incrementa el contador de nivel y se procesa cada nodo.
- Procesamiento de nodos: Se extrae cada nodo de la cola, se procesa (si es necesario) y se agregan sus hijos a la cola, para así considerar el siguiente nivel.
¿Cómo se manejan los hijos de un nodo?
En este algoritmo, se supone inicialmente que los nodos podrías tener múltiples hijos almacenados en una lista llamada hijas. Este modelo se adapta a árboles n-arios, sin embargo, para árboles binarios, podrías manejarlo directamente mediante propiedades izquierda y derecha.
Ejemplo de manejo de hijos en un árbol binario:
if nodo_actual.izquierda:
cola.append(nodo_actual.izquierda)
if nodo_actual.derecha:
cola.append(nodo_actual.derecha)
Esta modificación permite adaptar BFS a cualquier tipo de árbol, siendo flexible y eficiente.
¿Qué hacemos al finalizar la iteración del árbol?
Una vez que el algoritmo ha recorrido todos los niveles y procesado cada nodo, puedes realizar diversas tareas como imprimir el resultado. En este caso, el BFS completo resultará en una lista respuesta que contiene los nodos en el orden específico de búsqueda en anchura.
El método BFS es un paradigma fundamental en informática para el manejo y procesamiento de estructuras de datos complejas. ¡Esperamos que estos conocimientos fortalezcan tus habilidades y te motiven a seguir explorando otros algoritmos esenciales!
Aportes 2
Preguntas 0
Ordenar por:
```
def bfs(graph, node):
visited = \[]
queue = \[]
visited.append(node)
queue.append(node)
while queue:
s = queue.pop(0)
print(s, end = "")
for n in graph\[s]:
if n not in visited:
visited.append(n)
queue.append(n)
graph = {
'A': \['B','C'],
'B': \['D','E','F'],
'C': \['G'],
'D': \[],
'E': \[],
'F': \['H'],
'G': \['I'],
'H': \[],
'I': \[],
}
```
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?