Búsqueda en Anchura (BFS)
Explora todos los nodos de un nivel (profundidad) antes de pasar al siguiente nivel.
Explicación:
Estructura del Grafo
El grafo está representado como un diccionario de listas de adyacencia. Cada clave del
diccionario es un nodo, y el valor asociado es una lista de nodos vecinos (nodos conectados
directamente).
Algoritmo BFS
El BFS es un algoritmo que recorre un grafo nivel por nivel, explorando todos los vecinos de
un nodo antes de pasar a los vecinos de los vecinos.
Inicialización:
• Se utiliza una cola (deque) para almacenar los nodos que se van a explorar. La cola se
inicializa con el nodo de inicio y el camino que lleva a ese nodo.
• También se utiliza un conjunto (visitados) para llevar un registro de los nodos que ya
han sido visitados.
Bucle Principal:
• Mientras la cola no esté vacía, se extrae el primer elemento de la cola, que contiene
el nodo actual y el camino que lleva a ese nodo.
• Si el nodo actual es el objetivo, se retorna el camino.
Exploración de Vecinos:
• Si el nodo actual no ha sido visitado, se marca como visitado y se exploran todos sus
vecinos.
• Para cada vecino no visitado, se añade a la cola junto con el camino actualizado que
incluye ese vecino.
• Si el bucle termina y no se encuentra el objetivo, se retorna None.
Búsqueda de Costo Uniforme (UCS)
Explora los nodos en orden de costo acumulado desde el nodo inicial.
Explicación:
Estructura del Grafo
El grafo está representado como un diccionario de diccionarios, donde cada clave del
diccionario principal es un nodo, y el valor asociado es otro diccionario que mapea nodos
vecinos a los costos de las aristas que los conectan.
Algoritmo UCS
El UCS es un algoritmo que encuentra el camino más corto en un grafo ponderado,
expandiendo siempre el nodo con el menor costo acumulado. Aquí está el desglose del
código:
Inicialización:
• Se utiliza una cola de prioridad (heapq) para almacenar los nodos que se van a
explorar. La cola se inicializa con el nodo de inicio, el costo acumulado
(inicialmente 0), y el camino que lleva a ese nodo.
• También se utiliza un conjunto (visitados) para llevar un registro de los nodos
que ya han sido visitados.
Bucle Principal:
• Mientras la cola no esté vacía, se extrae el elemento con el menor costo
acumulado de la cola ([Link]), que contiene el costo acumulado, el
nodo actual, y el camino que lleva a ese nodo.
• Si el nodo actual es el objetivo, se retorna el camino y el costo total .
Exploración de Vecinos:
• Si el nodo actual no ha sido visitado, se marca como visitado y se exploran todos
sus vecinos.
• Para cada vecino no visitado, se calcula el nuevo costo acumulado y se añade
a la cola de prioridad junto con el camino actualizado que incluye ese vecino.
• Si el bucle termina y no se encuentra el objetivo, se retorna None.
Búsqueda Primero en Profundidad (DFS)
Explora un camino hasta que no puede avanzar más, luego retrocede y prueba otro
camino.
Explicación:
Estructura del Grafo
El grafo está representado como un diccionario de listas de adyacencia. Cada clave
del diccionario es un nodo, y el valor asociado es una lista de nodos vecinos (nodos
conectados directamente).
Algoritmo DFS
El DFS es un algoritmo que recorre un grafo explorando lo más profundo posible a lo
largo de cada rama antes de retroceder. Aquí está el desglose del código:
Inicialización:
• La función dfs toma como parámetros el grafo, el nodo de inicio, el nodo
objetivo, un conjunto de nodos visitados, y el camino actual.
• Si no se proporcionan los conjuntos de nodos visitados o el camino, se
inicializan por defecto.
Condición de Parada:
• Si el nodo actual (inicio) es igual al nodo objetivo, se retorna el camino actual.
Exploración de Vecinos:
• Se marca el nodo actual como visitado.
• Se recorren todos los vecinos del nodo actual.
• Si un vecino no ha sido visitado, se realiza una llamada recursiva a dfs con ese
vecino como nuevo nodo actual, y se actualiza el camino.
• Si no se encuentra el objetivo después de explorar todos los vecinos, se
retorna None.
