Análisis de un Algoritmo de Búsqueda en

Grafos en F#
1. Introducción
La programación funcional se basa en principios como la inmutabilidad, la expresividad y el uso de
funciones de orden superior. En este contexto, la recursividad se convierte en una herramienta
fundamental para la resolución de problemas, permitiendo expresar algoritmos sin necesidad de
estructuras iterativas como for o while . En este informe, se analiza la implementación de un
algoritmo en F# para encontrar caminos en un grafo ponderado mediante una variante del algoritmo
de búsqueda en profundidad (DFS, Depth First Search).

El objetivo es explorar el uso de recursividad y funciones de orden superior, identificando cómo

estos conceptos permiten estructurar el código de forma declarativa y eficiente. Se desglosa el
funcionamiento del algoritmo, se analiza su estructura y se resalta su aplicación en el paradigma
funcional.

2. Código
open System
// Tipo para representar un grafo como lista de adyacencia
let grafo =
[ "A", [ ("B", 2); ("C", 5) ]
"B", [ ("A", 2); ("D", 3); ("E", 4) ]
"C", [ ("A", 5); ("E", 1); ("F", 7) ]
"D", [ ("B", 3); ("E", 6) ]
"E", [ ("B", 4); ("C", 1); ("D", 6); ("F", 2) ]
"F", [ ("C", 7); ("E", 2) ] ]
|> [Link]

// Función recursiva para encontrar el camino más corto usando DFS

let rec buscarCamino (grafo: Map<string, (string * int) list>) (actual: string)
(destino: string) (visitados: Set<string>) (camino: (string * int) list) : (string
* int) list option =
if actual = destino then Some ([Link] camino)
else
let vecinos =
grafo |> [Link] actual |> [Link] []
|> [Link] (fun (nodo, _) -> not ([Link] nodo))
let explorar vecino =
let (siguiente, costo) = vecino
 buscarCamino grafo siguiente destino ([Link] actual)
((siguiente, costo) :: camino)
vecinos
|> [Link] explorar
|> [Link] ([Link] snd)
|> [Link]

// Función para leer datos dinámicamente

let leerEntrada () =
printf "Ingrese el nodo de inicio: "
let inicio = [Link]()
printf "Ingrese el nodo de destino: "
let destino = [Link]()
(inicio, destino)

// Función principal
let main () =
let (inicio, destino) = leerEntrada()
match buscarCamino grafo inicio destino [Link] [(inicio, 0)] with
| Some camino ->
printfn "Camino más corto: %A" ([Link] fst camino)
printfn "Costo total: %d" ([Link] snd camino)
| None ->
printfn "No se encontró camino."

main ()

3. Recursividad
La función buscarCamino implementa la búsqueda de un camino en un grafo utilizando recursión
en lugar de estructuras iterativas tradicionales (como bucles for o while ).

let rec buscarCamino (grafo: Map<string, (string * int) list>) (actual: string)
(destino: string) (visitados: Set<string>) (camino: (string * int) list) : (string
* int) list option =
if actual = destino then Some ([Link] camino)
else
let vecinos =
grafo |> [Link] actual |> [Link] []
|> [Link] (fun (nodo, _) -> not ([Link] nodo))
let explorar vecino =
let (siguiente, costo) = vecino
buscarCamino grafo siguiente destino ([Link] actual)
((siguiente, costo) :: camino)
vecinos
 |> [Link] explorar
|> [Link] ([Link] snd)
|> [Link]

1. Caso base:
Si el nodo actual ( actual ) es igual al nodo de destino ( destino ), se ha encontrado un
camino, por lo que se devuelve la lista de nodos recorridos en orden inverso ( [Link]
camino ).
2. Paso recursivo:
Se buscan los nodos vecinos del nodo actual ( actual ), excluyendo aquellos que ya han
sido visitados (para evitar ciclos).
Para cada nodo vecino (siguiente, costo) , se llama recursivamente a buscarCamino ,
agregando el nodo actual a la lista de visitados y actualizando el camino acumulado.
La función [Link] explorar filtra los caminos válidos encontrados en las llamadas
recursivas.
[Link] ([Link] snd) ordena los caminos encontrados según el costo total
(suma de los pesos de las aristas).
[Link] selecciona el camino de menor costo (si existe alguno).

Cada llamada a buscarCamino se encarga de explorar un nodo y delega el resto del trabajo en
llamadas recursivas. Este enfoque divide el problema en subproblemas más pequeños, hasta que se
llega a un caso base.

Ejemplo de una búsqueda recursiva en un grafo:

1. Inicio: buscarCamino(grafo, "A", "D", [Link], [])

2. Explora los vecinos de A , por ejemplo: "B" y "C"
3. Llama recursivamente con "B" como actual
Explora los vecinos de "B" , por ejemplo: "D"
4. Llama recursivamente con "D" como actual
Como "D" es el destino, se devuelve el camino encontrado.

Cada nivel de recursión se encarga de un solo nodo y delega la búsqueda de caminos a los niveles
inferiores.

4. Orden Superior
Las funciones de orden superior son funciones que reciben otras funciones como argumento o
devuelven funciones como resultado. En este algoritmo, se utilizan varias funciones de orden
superior para mejorar la claridad y modularidad del código.
4.1. ** [Link] **
[Link] permite seleccionar solo los elementos que cumplen una condición. En este caso, se
usa para filtrar los vecinos no visitados:

|> [Link] (fun (nodo, _) -> not ([Link] nodo))

Esta expresión toma una lista de vecinos y descarta aquellos que ya han sido visitados, asegurando
que la búsqueda continúe de manera eficiente.

4.2. ** [Link] **
[Link] aplica una función a cada elemento de la lista y descarta los valores None ,
devolviendo solo los Some . En este caso, se usa para explorar caminos posibles:

|> [Link] explorar

Cada vecino es evaluado con explorar , que devuelve un Some camino si encuentra un camino
válido o None en caso contrario. [Link] garantiza que solo los caminos válidos sean
considerados en la siguiente etapa.

4.3. ** [Link] **
[Link] ordena una lista según una función de ordenación. En este caso, se ordenan los
caminos según el costo total:

|> [Link] ([Link] snd)

[Link] snd calcula el costo total de cada camino sumando los pesos de las aristas.
[Link] reordena los caminos para priorizar los de menor costo.

Este enfoque permite que el algoritmo siempre seleccione el camino más corto en cada iteración.

5. Relación entre Recursividad y Orden Superior

La combinación de recursividad y funciones de orden superior hace que el código sea
declarativo y eficiente:

Recursividad: Permite explorar el grafo de forma natural sin necesidad de estructuras iterativas,
dividiendo el problema en subproblemas hasta alcanzar una solución.
 Funciones de orden superior: Permiten manipular listas de manera expresiva y reutilizable,
filtrando, transformando y ordenando los datos sin estructuras imperativas.
Legibilidad y modularidad: Al separar la lógica de búsqueda (recursividad) de la manipulación
de datos (funciones de orden superior), el código es más fácil de entender y mantener.

6. Ejemplo
let grafo =
[Link] [
("A", [("B", 2); ("C", 5)]);
("B", [("D", 1); ("E", 3)]);
("C", [("E", 1)]);
("D", [("F", 4)]);
("E", [("F", 1)]);
("F", [])
]

Si llamamos:

buscarCamino grafo "A" "F" [Link] []

Paso a paso de la ejecución

1. Nodo Actual: "A"
Vecinos disponibles: B (costo 2) , C (costo 5)
Se exploran los vecinos recursivamente.
2. Nodo "B" (de A, costo acumulado: 2)
Vecinos disponibles: D (costo 1) , E (costo 3)
Se exploran los vecinos recursivamente.
3. Nodo "D" (de B, costo acumulado: 3)
Vecinos disponibles: F (costo 4)
4. Nodo "F" (de D, costo acumulado: 7) → Llega al destino
Se retorna el camino: [("A", 0); ("B", 2); ("D", 1); ("F", 4)]
Costo total: 2 + 1 + 4 = 7

Primera Respuesta Devuelta

El primer camino encontrado que llega de "A" a "F" en orden correcto será:
 Some [("A", 0); ("B", 2); ("D", 1); ("F", 4)]

Donde:

"A" es el inicio (costo 0).

"B" es visitado con un costo de 2 .
"D" es visitado desde "B" con un costo adicional de 1 (total 3 ).
"F" es alcanzado desde "D" con un costo adicional de 4 (total 7 ).

Este camino es retornado porque la función [Link] ([Link] snd) ordena los caminos
por costo total y [Link] selecciona el de menor costo.