Búsqueda en profundidad y búsqueda en ancho / Sudo Null IT News
Prefacio
¡Bienvenido al artículo final de la serie sobre estructuras de datos para desarrolladores de iOS! A lo largo de los años, hemos profundizado en las estructuras de datos básicas que le ayudan a resolver eficientemente problemas de programación y procesamiento de datos. Hoy concluimos esta serie con una descripción general de los gráficos y métodos de búsqueda en amplitud (BFS) y búsqueda en profundidad (DFS). Estos algoritmos son una parte importante de muchas aplicaciones, desde la búsqueda de la ruta más corta hasta el análisis de conectividad de gráficos y muchos otros problemas.
En esta serie ya hemos estudiado:
Notación O grande: Una forma formal de evaluar la complejidad de los algoritmos, que ayuda a comprender con qué eficiencia funcionan a medida que aumenta el volumen de datos. Lea más aquí y aquí.
Matrices: Estructuras básicas para almacenar datos secuenciales, sus ventajas y desventajas. Lea más aquí.
Listas enlazadas: Estructuras de datos flexibles que permiten una gestión eficiente de la memoria y un cambio de tamaño sobre la marcha. Los detalles y ejemplos de uso se pueden encontrar aquí.
Pilas y colas: Estructuras de datos básicas para gestionar la secuencia de operaciones y procesar datos por orden de llegada o prioridad. Descubra más aquí.
Tablas hash: Una forma eficiente de almacenar y acceder rápidamente a datos mediante funciones hash. El artículo está disponible aquí.
Árboles y árboles de búsqueda binarios: Estructuras de datos fundamentales para organizar y recuperar información. Descubra más aquí.
Algoritmos de clasificación: Métodos clave para organizar datos, incluida la clasificación por burbujas, la clasificación por combinación, la clasificación rápida y otros. Obtenga más información sobre los enfoques de clasificación aquí.
Serie de Fibonacci y memorización: Aplique programación dinámica y optimización computacional cuando trabaje con problemas recursivos como el cálculo de números de Fibonacci. Puedes leerlo aquí.
Estos materiales proporcionan una base sólida para comprender y aplicar estructuras de datos a problemas del mundo real. El artículo de hoy es la conclusión lógica de la serie, en la que profundizaremos en el uso de gráficos para resolver diversos problemas mediante algoritmos de búsqueda.
¡Suscríbete a mi canal de Telegram!
Si te gustó esta serie de artículos y te gustaría recibir contenido aún más útil sobre algoritmos y estructuras de datos, además de participar en discusiones y recibir materiales exclusivos, ¡te invito a unirte a mi canal de Telegram! Suscribir en el enlace y mantente al día con todas las novedades y actualizaciones.
¿Qué son los gráficos?
Un gráfico es una estructura matemática que consta de un conjunto de vértices (o nodos) y un conjunto de aristas (o caras) que conectan pares de vértices. Los gráficos se utilizan para modelar relaciones y conexiones entre objetos. Un grafo puede ser dirigido o no dirigido.
Si ha leído artículos anteriores, entonces ya ha visto un gráfico, y este gráfico se llama árbol binario. ¿Pero cuáles son sus limitaciones? En primer lugar, cada padre sólo puede tener dos hijos. En segundo lugar, el gráfico siempre tiene una dirección de arriba hacia abajo. En otras palabras, las aristas o conexiones siempre van de padre a hijo.
Los gráficos que consideraremos no estarán limitados por el número de vértices o aristas. Nuestros vértices y aristas pueden ir a cualquier parte. Puede tomar cualquier estructura de datos y pensar en los nodos como vértices y los enlaces como aristas.
Cuando hablamos de costillas, existen dos tipos. El tipo que vimos en un árbol binario es un borde dirigido que va en una dirección de un vértice a otro. Pero aquí, con los gráficos ordinarios, no nos limitamos a esto. Estos bordes pueden ser bidireccionales, es decir, van en ambas direcciones. Además, nuestros vértices pueden conectarse a cualquier otro vértice que queramos. No tenemos que pasar sólo de padres a hijos.
A medida que profundicemos en las gráficas veremos que estas aristas también pueden tener pesos. El peso en el gráfico representa el costo relativo de moverse a lo largo de un borde de un vértice a otro. Por ejemplo, si queremos encontrar el vuelo más barato de Moscú a Sydney o la distancia más corta, podemos construir un gráfico de bordes y determinar qué camino es el más corto.
En pocas palabras, un gráfico es simplemente una serie de vértices y aristas que representan algún problema o área que normalmente queremos explorar o navegar. Antes de comenzar a construir gráficos, será útil tener algunas estructuras de datos básicas que podamos usar para representar los datos.
Primero exploraremos tres formas diferentes en las que las gráficas se pueden representar como datos. Luego veremos las dos formas más comunes de utilizar estas estructuras de datos para la búsqueda de gráficos.
¿Cómo funcionan los gráficos?
Cuando se trata de modelar estructuras de datos de gráficos, nuestro objetivo es representar cada uno de estos vértices y aristas como una estructura de datos subyacente simple. Y tres estructuras de datos de gráficos muy comunes son las listas de bordes, las matrices de adyacencia y las listas de adyacencia.
Comencemos con una lista de aristas. En una lista de aristas, simplemente tomamos cada arista del gráfico, como de cero a uno, y la representamos como dos elementos en una matriz: cero y uno. Este es el objetivo de la lista. La belleza de una lista es su simplicidad. No hay nada complicado en su presentación. El único inconveniente es que si necesitamos encontrar un borde específico en una lista, será una búsqueda lineal y tendremos que buscar en toda la lista, en otras palabras, O(n).
Por otro lado, la matriz de adyacencia tiene un tiempo de búsqueda muy rápido. Aquí tomamos cada arista del gráfico y la representamos como una unidad en una matriz bidimensional. Por ejemplo, si una arista va de cero a uno, cero sería nuestro elemento i y uno sería nuestro elemento j. Encontraremos este lugar en la matriz y pondremos uno allí. Lo mismo ocurre con los bordes uno y dos: encontraremos un lugar en la matriz e insertaremos un uno en las posiciones uno y dos para representar ese borde. La ventaja de la matriz de adyacencia es que proporciona búsquedas rápidas de O (1). El único inconveniente es que no es el que ahorra más memoria. Si tenemos pocas aristas, la matriz tendrá muchos ceros, provocando pérdida de memoria.
Pero existe una estructura de datos que combina la simplicidad de una lista de aristas con la velocidad de una matriz de adyacencia: la lista de adyacencia. En esta estructura, tomamos cada vértice y simplemente registramos cada uno de sus vecinos como una lista en una matriz. Por ejemplo, el vértice 0 tiene dos vecinos: los vértices 1 y 4. Simplemente almacenamos 1 y 4 en una matriz, y estos serán los vecinos del vértice 0. Lo mismo ocurre con el vértice 1, que tiene un vecino 2. El vértice 2 no tiene vecinos . El vértice 3 tiene dos vecinos: 1 y 2, y el vértice 4 tiene tres vecinos. Almacenar una matriz de matrices o listas vinculadas de estos elementos le permite crear rápidamente una colección de vecinos para cada vértice y luego encontrarlos rápidamente.
Si hace que todos los bordes en el gráfico no estén dirigidos, entonces, en el caso de una lista de bordes, esto simplemente significa que para cada borde existente, se agrega lo opuesto. Por ejemplo, si había una arista de un vértice a otro, entonces se agrega una arista inversa. Por tanto, el número de nervaduras se duplica y cada nervadura se vuelve de doble cara.
Para la matriz de adyacencia, esto hace que la matriz se vuelva simétrica. Es decir, los valores de la matriz a ambos lados de la diagonal principal serán los mismos, lo cual es una buena forma visual de comprobar la validez de la matriz para un gráfico no dirigido.
En cuanto a la lista de adyacencia, se agregan vecinos en ambas direcciones para cada vértice. Como resultado, cada vértice recibe conexiones adicionales con otros vértices, que reflejan aristas bidireccionales.
Ahora que tenemos las estructuras de datos básicas para gráficas, podemos pasar a practicar. Veremos el algoritmo de búsqueda en amplitud, la principal herramienta para trabajar con gráficos.
Primera búsqueda en amplitud
En la búsqueda en amplitud, comenzamos en el vértice central y ampliamos nuestra búsqueda hacia afuera. Observamos los nodos más cercanos a nosotros, los atravesamos todos y luego pasamos al siguiente nivel del gráfico. Piense en ello como una búsqueda de vecino más cercano. Este método se utiliza para encontrar amigos en gráficos sociales, generar recomendaciones de canciones en Spotify e identificar jugadores de baja latencia en juegos en línea para distribuir la carga de manera más uniforme.
La búsqueda en profundidad, por otro lado, comienza en un nodo y profundiza, ignorando todos los demás nodos excepto uno, y continúa hasta que da la vuelta completa o no encuentra bordes para expandirse. Este algoritmo es útil para encontrar un camino a través de un laberinto o resolver problemas con soluciones únicas, como encontrar un camino a través de un laberinto, y para detectar ciclos en un gráfico.
La primera búsqueda en amplitud se refiere principalmente al mantenimiento de registros. Realizamos un seguimiento de los nodos que hemos visitado a medida que recorremos el gráfico. Para permanecer en el nivel superior y visitar a los vecinos cercanos en lugar de profundizar más, utilizamos una cola. Las colas funcionan según el principio FIFO (primero en entrar, primero en salir). La cola es la base del algoritmo de búsqueda en amplitud: agregamos los nodos que queremos visitar a un extremo de la cola y los recuperamos en orden de llegada desde el otro extremo. Así es como apoyamos la búsqueda en amplitud. Veamos cómo se ve esto en código.
import Foundation
// Очередь для поиска в ширину
struct Queue<T> {
private var array: (T)
init() {
array = ()
}
var isEmpty: Bool {
return array.isEmpty
}
var count: Int {
return array.count
}
mutating func add(_ element: T) {
array.append(element)
}
mutating func remove() -> T? {
if isEmpty {
return nil
} else {
return array.removeFirst()
}
}
func peek() -> T? {
return array.first
}
}
// Стек для поиска в глубину
struct Stack<T> {
fileprivate var array = (T)()
var isEmpty: Bool {
return array.isEmpty
}
var count: Int {
return array.count
}
mutating func push(_ element: T) {
array.append(element)
}
mutating func pop() -> T? {
return array.popLast()
}
var top: T? {
return array.last
}
}
class Graph {
var V = 0 // количество вершин
var adj = ((Int))() // список смежности
init(_ V: Int) {
self.V = V
for _ in 0..<V {
adj.append((Int)()) // создать пустой массив списков смежности
}
}
func addEdge(v: Int, w: Int) {
adj(v).append(w)
}
// Обход в ширину (BFS) от заданной начальной вершины s
func BFS(s: Int) -> (Int) {
var result = (Int)()
// Отметить все вершины как не посещенные
var visited = adj.map { _ in false }
// Создать очередь для обхода в ширину (BFS Queue)
var queue = Queue<Int>()
// Отметить первую вершину как посещенную и добавить в очередь
visited(s) = true
print("Starting at \(s)")
queue.add(s)
result.append(s)
while queue.count > 0 {
let current = queue.remove()!
print("De-queueing \(current)")
// Получить все смежные вершины текущей вершины
// Если смежная вершина еще не посещена,
// отметить её как посещенную и добавить в очередь
for n in adj(current) {
if visited(n) == false {
visited(n) = true
print("Queuing \(n)")
queue.add(n)
result.append(n)
}
}
}
return result
}
// Обход в глубину (DFS) от заданной начальной вершины s
func DFS(s: Int) -> (Int) {
var result = (Int)()
// Отметить все вершины как не посещенные
var visited = adj.map { _ in false }
// Создать стек для обхода в глубину (DFS Stack)
var stack = Stack<Int>()
// Отметить первую вершину как посещенную и добавить в стек
// print("Начало с вершины \(s)")
visited(s) = true
stack.push(s)
while stack.count > 0 {
let current = stack.pop()!
// print("Извлечение из стека \(current)")
result.append(current)
// Перебрать всех соседей, добавляя их в стек и извлекая по мере углубления
for n in adj(current) {
for n in adj(current) {
if visited(n) == false {
visited(n) = true
// print("Добавление в стек - \(n)")
stack.push(n)
}
}
}
return result
}
}
// Нужно создать столько вершин, сколько есть рёбер
let g = Graph(8)
g.addEdge(v: 0, w: 1)
g.addEdge(v: 1, w: 4)
g.addEdge(v: 4, w: 6)
g.addEdge(v: 6, w: 0)
g.addEdge(v: 1, w: 5)
g.addEdge(v: 5, w: 3)
g.addEdge(v: 3, w: 0)
g.addEdge(v: 5, w: 2)
g.addEdge(v: 2, w: 7)
//g.BFS(s: 0)
print(g.DFS(s: 0))
análisis de código
Lo primero que haremos será crear un gráfico. Indicaremos cuántos nodos o vértices tenemos en el gráfico. En nuestro caso, ese número sería ocho, el mismo gráfico que usamos antes, de 0 a 7. Y para configurar esto, necesitamos definir todos los bordes en nuestro gráfico.
Este es un gráfico no dirigido, lo que significa que tenemos aristas que van de cero a uno, pero también tenemos aristas que van de uno a cero. Dado que todas las aristas de nuestro gráfico no están dirigidas, las sumamos todas aquí en ambas direcciones (agregar aristas).
Cuando estemos listos para buscar, simplemente llamamos a la función de búsqueda en amplitud, comenzando en el nodo 0. Y si la ejecutamos, obtendremos el mismo resultado que vimos antes: comenzando en el nodo 0, yendo en amplitud a nodo 7.
En nuestro gráfico, configuramos los datos de esta manera: tenemos una variable V que realiza un seguimiento del número de vértices y tenemos una matriz de matrices de números enteros. Esto es lo que mantendrá seguros a todos nuestros vecinos. Esta es nuestra lista de adyacencia como vimos anteriormente. Realizará un seguimiento de todos los vecinos de cada nodo, almacenándolos como una matriz de matrices de números enteros.
Cuando creamos un gráfico, simplemente sabemos cuántos vértices tenemos. Luego creamos nuestra lista de adyacencia y estamos listos para comenzar. Para cualquier vértice V conectado a otro W, simplemente encontramos la matriz y agregamos ese otro vértice como vecino.
Cuando se trata de recorrido, comenzamos marcando todos los nodos visitados como falsos, lo que significa que aún no hemos visitado ningún nodo. Luego creamos nuestra cola para realizar un seguimiento de dónde hemos estado. Tomamos el primer nodo pasado a la función de búsqueda en amplitud. Lo marcamos como visitado, lo mostramos para mostrar que estuvimos allí y lo agregamos a la cola. En nuestro caso este será el nodo 0.
Mientras tenemos algo en la cola, sacamos el siguiente nodo de la cola, eliminándolo así. Luego visitamos a todos sus vecinos. Vamos a la matriz de matrices, nuestra lista de adyacencia, obtenemos un iterador y simplemente iteramos a través de cada una. Si aún no lo hemos visitado, lo marcamos como visitado y lo agregamos a la cola. Hacemos esto para todos los vecinos y continuamos hasta que hayamos visitado todos los vértices del gráfico.
Así es como funciona la búsqueda en amplitud en pocas palabras. Un pequeño algoritmo elegante, absolutamente hermoso. Ahora tienes un ejemplo con el que trabajar y jugar contigo mismo.
Primera búsqueda en profundidad
La búsqueda en profundidad funciona de manera muy similar a la búsqueda en amplitud. Aquí tenemos el mismo gráfico que usamos en la búsqueda en amplitud, pero observe que ahora tenemos una pila en lugar de una cola. Recuerde que la pila utiliza el principio LIFO (último en entrar, primero en salir): el último valor ingresado sale primero. Esto nos permite profundizar más que ampliar. Ésta es la diferencia entre la búsqueda en profundidad y la búsqueda en amplitud.
Ahora veamos cómo se ve en el código.
análisis de código
El código para la búsqueda en profundidad es casi el mismo que para la búsqueda en amplitud. La única diferencia aquí es que en lugar de una cola usamos una pila. Y en lugar de agregar y extraer elementos de la cola, agregamos y extraemos elementos de la pila. Aparte de eso, es el mismo algoritmo.
Tenemos la misma prueba con la misma gráfica. Si lo ejecutamos y miramos, veremos que en lugar de ampliarnos, profundizaremos. Entonces, como en nuestro ejemplo, el primer camino que tomamos es del 0 al 3, luego al 5, luego al 2 y al 7. Luego volvemos y tomamos el camino restante: 6, 4 y 1.
Ahora repasemos este algoritmo y veamos en detalle cómo funciona. Agregué algunas declaraciones de inferencia para que cuando ejecute la prueba, al igual que la búsqueda en amplitud, pueda ver dónde se agregan y recuperan los diferentes elementos.
Comenzamos en el nodo 0. Vamos allí, lo visitamos, lo agregamos a la pila y lo marcamos como visitado. Ahora estamos listos para seguir adelante. Sacamos el nodo 0 de la pila. Lo primero que hacemos es mirar a sus vecinos: tenemos los nodos 1, 6 y 3. Los agregamos a la pila en orden aleatorio, ya que 3 fue el último elemento agregado, lo sacamos primero y miramos a sus vecinos. Tenemos el nodo 5, así que lo marcamos como visitado, lo agregamos a la pila y continuamos hasta el nodo 5.
Cuando llegamos al nodo 5, miramos a nuestro alrededor y vemos que ya se han visitado todos los nodos excepto el nodo 2. Entonces agregamos el nodo 2 a la pila y continuamos hacia él. Recuperamos el nodo 2, miramos a sus vecinos y vemos que el nodo 7 es el único nodo no visitado. Lo marcamos como visitado, lo agregamos a la pila y en este punto finaliza la ruta.
Observe el camino que tomamos: de 0 a 3, luego a 5, luego a 2 y a 7. Esta es una búsqueda en profundidad. En lugar de permanecer en la parte superior y visitar los nodos 1, 6 y 3 desde el nodo 0, elegimos el nodo 3 y avanzamos lo más posible por ese camino hasta llegar al nodo 7.
Cuando ese camino se agota, regresamos y vemos que el siguiente elemento en nuestra pila es el nodo 6. Ahora tomamos otro camino, hacemos estallar el nodo 6, vamos a él, miramos a nuestro alrededor y vemos que tenemos un nodo 4 no visitado. Marcamos Como visitado, lo agregamos a la pila y continuamos hasta el nodo 4. Habiendo llegado al nodo 4, vemos que no tenemos más nodos no visitados. Ya hemos marcado el nodo 1 como visitado. Ahora extraemos el nodo 4, luego el nodo 1 y listo. Simplemente tomamos una ruta diferente para el último tramo del viaje, pasando del nodo 0 al nodo 6, luego al nodo 4 y finalmente al nodo 1.
Conclusión
Una de las preguntas más comunes en las entrevistas cuando se trata de gráficos es qué algoritmo es mejor: ¿la búsqueda en amplitud o la búsqueda en profundidad? Y para ayudarle a responder esta pregunta, es útil tener en mente algunos ejemplos clave de cada uno para poder explicar que la respuesta a esta pregunta depende del contexto.
Por ejemplo, se podría decir que la búsqueda en amplitud es mejor para encontrar objetos que se encuentran en los niveles superiores del gráfico. Cuando utilizamos la búsqueda en amplitud, buscamos vecinos más cercanos, algo cercano. Esto incluye cosas como redes sociales como Facebook y LinkedIn donde necesitas hacer nuevos amigos, juegos de computadora y cualquier cosa donde creas que la solución al problema que estás buscando en un gráfico está cerca o en la parte superior de la estructura del gráfico. En tales casos, utilizará la búsqueda en amplitud.
La búsqueda en profundidad, por otro lado, es más adecuada para encontrar objetos que están lejos. Cuando piensas en la búsqueda en profundidad, piensas en la idea de que hay una solución o algo lejano que sólo se puede encontrar de manera eficiente profundizando. Un ejemplo clásico de esto es la inteligencia artificial en el juego de ajedrez. Para determinar la mejor manera de ganar en el ajedrez, debes observar gradualmente los movimientos de tu oponente para extrapolarlos hasta el final del juego y ver si hay una solución, y luego trabajar hacia atrás para elegir el siguiente movimiento. Con la búsqueda en amplitud, se amplía y se utiliza una cola, y con la búsqueda en profundidad, se profundiza y se utiliza una pila. Ahora podrás explicar la diferencia entre búsqueda en amplitud y búsqueda en profundidad, y cuando te pregunten cuál es mejor, podrás decir que depende de la tarea y luego dar ejemplos específicos.
