Recorridos de grafos en Haskell
En este artículo presento una implementación en Haskell de algoritmos de recorridos de grafos en profundidad y en anchura. En las implementaciones he usado los siguientes tipos de datos abstractos, presentados en anteriores artículos, de los grafos, de las pilas y de las colas.
Recorrido de grafos en profundidad
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
module RecorridoEnProfundidad where -- --------------------------------------------------------------------- -- Librerías auxiliares -- -- --------------------------------------------------------------------- -- Nota: Elegir una implementación de los grafos. import GrafoConVectorDeAdyacencia -- import GrafoConMatrizDeAdyacencia -- Nota: Elegir una implementación de las pilas. import PilaConListas -- import PilaConTipoDeDatoAlgebraico -- --------------------------------------------------------------------- -- Ejemplo de grafo -- -- --------------------------------------------------------------------- -- g es el grafo -- +---> 2 <---+ -- | | -- | | -- 1 --> 3 --> 6 --> 5 -- | | -- | | -- +---> 4 <---------+ g = creaGrafo True (1,6) [(1,2,0),(1,3,0),(1,4,0),(3,6,0),(5,4,0),(6,2,0),(6,5,0)] -- --------------------------------------------------------------------- -- Recorrido en profundidad -- -- --------------------------------------------------------------------- -- (recorridoEnProfundidad i g) es el recorrido en profundidad del grafo g -- desde el vértice i. Por ejemplo, -- recorridoEnProfundidad 1 g == [1,2,3,6,5,4] recorridoEnProfundidad i g = rp [i] [] where rp [] vis = vis rp (c:cs) vis | elem c vis = rp cs vis | otherwise = rp ((adyacentes g c)++cs) (vis++[c]) -- Traza del cálculo de (recorridoEnProfundidad 1 g) -- recorridoEnProfundidad 1 g -- = rp [1] [] -- = rp [2,3,4] [1] -- = rp [3,4] [1,2] -- = rp [6,4] [1,2,3] -- = rp [2,5,4] [1,2,3,6] -- = rp [5,4] [1,2,3,6] -- = rp [4,4] [1,2,3,6,5] -- = rp [4] [1,2,3,6,5,4] -- = rp [] [1,2,3,6,5,4] -- = [1,2,3,6,5,4] -- --------------------------------------------------------------------- -- Recorrido en profundidad con acumuladores -- -- --------------------------------------------------------------------- -- (recorridoEnProfundidad' i g) es el recorrido en profundidad del -- grafo g desde el vértice i, usando la lista de los visitados como -- acumulador. Por ejemplo, -- recorridoEnProfundidad' 1 g == [1,2,3,6,5,4] recorridoEnProfundidad' i g = reverse (rp [i] []) where rp [] vis = vis rp (c:cs) vis | elem c vis = rp cs vis | otherwise = rp ((adyacentes g c)++cs) (c:vis) -- Traza del cálculo de (recorridoEnProfundidad' 1 g) -- RecorridoEnProfundidad' 1 g -- = reverse (rp [1] []) -- = reverse (rp [2,3,4] [1]) -- = reverse (rp [3,4] [2,1]) -- = reverse (rp [6,4] [3,2,1]) -- = reverse (rp [2,5,4] [6,3,2,1]) -- = reverse (rp [5,4] [6,3,2,1]) -- = reverse (rp [4,4] [5,6,3,2,1]) -- = reverse (rp [4] [4,5,6,3,2,1]) -- = reverse (rp [] [4,5,6,3,2,1]) -- = reverse [4,5,6,3,2,1] -- = [1,2,3,6,5,4] -- --------------------------------------------------------------------- -- Recorrido en profundidad con pilas -- -- --------------------------------------------------------------------- -- (recorridoEnProfundidad'' i g) es el recorrido en profundidad del -- grafo g desde el vértice i, usando pilas. Por ejemplo, -- recorridoEnProfundidad'' 1 g == [1,2,3,6,5,4] recorridoEnProfundidad'' i g = reverse (rp (apila i vacia) []) where rp s vis | esVacia s = vis | elem (cima s) vis = rp (desapila s) vis | otherwise = rp (foldr apila (desapila s) (adyacentes g c)) (c:vis) where c = cima s |
Recorrido de grafos en anchura
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
module RecorridoEnAnchura where -- --------------------------------------------------------------------- -- Librerías auxiliares -- -- --------------------------------------------------------------------- -- Nota: Elegir una implementación de los grafos. import GrafoConVectorDeAdyacencia -- import GrafoConMatrizDeAdyacencia -- Nota: Elegir una implementación de las colas import ColaConListas -- import ColaConDosListas -- --------------------------------------------------------------------- -- Ejemplo de grafo -- -- --------------------------------------------------------------------- -- g es el grafo -- +---> 2 <---+ -- | | -- | | -- 1 --> 3 --> 6 --> 5 -- | | -- | | -- +---> 4 <---------+ g = creaGrafo True (1,6) [(1,2,0),(1,3,0),(1,4,0),(3,6,0),(5,4,0),(6,2,0),(6,5,0)] -- --------------------------------------------------------------------- -- Recorrido en anchura con colas -- -- --------------------------------------------------------------------- -- (recorridoEnAnchura i g) es el recorrido en anchura del grafo g -- desde el vértice i, usando colas. Por ejemplo, -- recorridoEnAnchura 1 g == [1,4,3,2,6,5] recorridoEnAnchura i g = reverse (ra (inserta i vacia) []) where ra q vis | esVacia q = vis | elem (primero q) vis = ra (resto q) vis | otherwise = ra (foldr inserta (resto q) (adyacentes g c)) (c:vis) where c = primero q |
Los códigos utilizados se encuentran en
- PilaConListas: Implementación de las pilas mediante listas.
- PilaConTipoDeDatoAlgebraico: Implementación de las pilas mediante tipos de datos algebraicos.
- ColaConListas: Implementación de las colas mediante listas.
- ColaConDosListas: Implementación de las colas mediante pares de listas.
- GrafoConVectorDeAdyacencia: Implementación de los grafos mediante vectores de adyacencia.
- GrafoConMatrizDeAdyacencia: Implementación de los grafos mediante matrices de adyacencia.
- RecorridoEnProfundidad: Recorrido en profundidad.
- RecorridoEnAnchura: Recorrido en anchura.
El objetivo de la serie es la elaboración de los temas de TAD del curso de Informática del Grado en Matemáticas.
Fuentes
- Algorithms: A Functional Programming Approach por Fethi Rabhi y Guy Lapalme.