{"id":1542,"date":"2011-08-31T11:16:20","date_gmt":"2011-08-31T11:16:20","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1542"},"modified":"2011-08-31T11:16:20","modified_gmt":"2011-08-31T11:16:20","slug":"recorridos-de-grafos-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/recorridos-de-grafos-en-haskell\/","title":{"rendered":"Recorridos de grafos en Haskell"},"content":{"rendered":"<p>En este art\u00edculo presento una implementaci\u00f3n en Haskell de algoritmos de recorridos de grafos en <a href=\"http:\/\/en.wikipedia.org\/wiki\/Depth-first_search\">profundidad<\/a> y en <a href=\"http:\/\/en.wikipedia.org\/wiki\/Breadth-first_search\">anchura<\/a>. En las implementaciones he usado los siguientes tipos de datos abstractos, presentados en anteriores art\u00edculos, de los <a  href=\"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-tipo-abstracto-de-datos-de-los-grafos-en-haskell\/\">grafos<\/a>, de las <a href=\"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-tipo-abstracto-de-datos-de-las-pilas-en-haskell\/\">pilas<\/a> y de las <a href=\"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-tipo-abstracto-de-datos-de-las-colas-en-haskell\/\">colas<\/a>.<br \/>\n<!--more--><\/p>\n<h3>Recorrido de grafos en profundidad<\/h3>\n<pre lang=\"haskell\">\r\nmodule RecorridoEnProfundidad where\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Librer\u00edas auxiliares                                               --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Nota: Elegir una implementaci\u00f3n de los grafos.\r\nimport GrafoConVectorDeAdyacencia\r\n-- import GrafoConMatrizDeAdyacencia\r\n\r\n-- Nota: Elegir una implementaci\u00f3n de las pilas.\r\nimport PilaConListas\r\n-- import PilaConTipoDeDatoAlgebraico\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejemplo de grafo                                                   --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- g es el grafo\r\n--    +---> 2 <---+\r\n--    |           |\r\n--    |           |\r\n--    1 --> 3 --> 6 --> 5\r\n--    |                 |\r\n--    |                 |\r\n--    +---> 4 <---------+\r\ng = creaGrafo True (1,6) \r\n              [(1,2,0),(1,3,0),(1,4,0),(3,6,0),(5,4,0),(6,2,0),(6,5,0)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Recorrido en profundidad                                            --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (recorridoEnProfundidad i g) es el recorrido en profundidad del grafo g\r\n-- desde el v\u00e9rtice i. Por ejemplo,\r\n--    recorridoEnProfundidad 1 g  ==  [1,2,3,6,5,4]\r\nrecorridoEnProfundidad i g = rp [i] []\r\n    where \r\n      rp [] vis    = vis\r\n      rp (c:cs) vis \r\n          | elem c vis = rp cs vis\r\n          | otherwise  = rp ((adyacentes g c)++cs) (vis++[c])\r\n\r\n-- Traza del c\u00e1lculo de (recorridoEnProfundidad 1 g)\r\n--    recorridoEnProfundidad 1 g\r\n--    = rp [1]     []\r\n--    = rp [2,3,4] [1]\r\n--    = rp [3,4]   [1,2]\r\n--    = rp [6,4]   [1,2,3]\r\n--    = rp [2,5,4] [1,2,3,6]\r\n--    = rp [5,4]   [1,2,3,6]\r\n--    = rp [4,4]   [1,2,3,6,5]\r\n--    = rp [4]     [1,2,3,6,5,4]\r\n--    = rp []      [1,2,3,6,5,4]\r\n--    = [1,2,3,6,5,4]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Recorrido en profundidad con acumuladores                           --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (recorridoEnProfundidad' i g) es el recorrido en profundidad del\r\n-- grafo g desde el v\u00e9rtice i, usando la lista de los visitados como\r\n-- acumulador. Por ejemplo, \r\n--    recorridoEnProfundidad' 1 g  ==  [1,2,3,6,5,4]\r\nrecorridoEnProfundidad' i g = reverse (rp [i] [])\r\n    where\r\n      rp [] vis     = vis\r\n      rp (c:cs) vis \r\n          | elem c vis = rp cs vis\r\n          | otherwise  = rp ((adyacentes g c)++cs) (c:vis)\r\n\r\n-- Traza del c\u00e1lculo de (recorridoEnProfundidad' 1 g)\r\n--    RecorridoEnProfundidad' 1 g\r\n--    = reverse (rp [1]     [])\r\n--    = reverse (rp [2,3,4] [1])\r\n--    = reverse (rp [3,4]   [2,1])\r\n--    = reverse (rp [6,4]   [3,2,1])\r\n--    = reverse (rp [2,5,4] [6,3,2,1])\r\n--    = reverse (rp [5,4]   [6,3,2,1])\r\n--    = reverse (rp [4,4]   [5,6,3,2,1])\r\n--    = reverse (rp [4]     [4,5,6,3,2,1])\r\n--    = reverse (rp []      [4,5,6,3,2,1])\r\n--    = reverse [4,5,6,3,2,1]\r\n--    = [1,2,3,6,5,4]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Recorrido en profundidad con pilas                                  --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (recorridoEnProfundidad'' i g) es el recorrido en profundidad del\r\n-- grafo g desde el v\u00e9rtice i, usando pilas. Por ejemplo, \r\n--    recorridoEnProfundidad'' 1 g  ==  [1,2,3,6,5,4]\r\nrecorridoEnProfundidad'' i g = reverse (rp (apila i vacia) [])\r\n where\r\n   rp s vis \r\n    | esVacia s         = vis\r\n    | elem (cima s) vis = rp (desapila s) vis\r\n    | otherwise         = rp (foldr apila (desapila s) (adyacentes g c)) \r\n                             (c:vis)\r\n                          where c = cima s\r\n<\/pre>\n<h3>Recorrido de grafos en anchura<\/h3>\n<pre lang=\"haskell\">\r\nmodule RecorridoEnAnchura where\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Librer\u00edas auxiliares                                               --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Nota: Elegir una implementaci\u00f3n de los grafos.\r\nimport GrafoConVectorDeAdyacencia\r\n-- import GrafoConMatrizDeAdyacencia\r\n\r\n-- Nota: Elegir una implementaci\u00f3n de las colas\r\nimport ColaConListas\r\n-- import ColaConDosListas\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejemplo de grafo                                                   --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- g es el grafo\r\n--    +---> 2 <---+\r\n--    |           |\r\n--    |           |\r\n--    1 --> 3 --> 6 --> 5\r\n--    |                 |\r\n--    |                 |\r\n--    +---> 4 <---------+\r\ng = creaGrafo True (1,6) \r\n              [(1,2,0),(1,3,0),(1,4,0),(3,6,0),(5,4,0),(6,2,0),(6,5,0)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Recorrido en anchura con colas                                      --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (recorridoEnAnchura i g) es el recorrido en anchura del grafo g\r\n-- desde el v\u00e9rtice i, usando colas. Por ejemplo, \r\n--    recorridoEnAnchura 1 g  ==  [1,4,3,2,6,5]\r\nrecorridoEnAnchura i g = reverse (ra (inserta i vacia) [])\r\n where\r\n  ra q vis \r\n   | esVacia q = vis\r\n   | elem (primero q) vis = ra (resto q) vis\r\n   | otherwise  = ra (foldr inserta (resto q) (adyacentes g c))\r\n                     (c:vis)\r\n                  where c = primero q\r\n<\/pre>\n<p>Los c\u00f3digos utilizados se encuentran en<\/p>\n<ul>\n<li> <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/codigos\/PilaConListas.hs\">PilaConListas<\/a>: Implementaci\u00f3n de las pilas mediante listas.\n<li> <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/codigos\/PilaConTipoDeDatoAlgebraico.hs\">PilaConTipoDeDatoAlgebraico<\/a>: Implementaci\u00f3n de las pilas mediante tipos de datos algebraicos.\n<li> <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/codigos\/ColaConListas.hs\">ColaConListas<\/a>: Implementaci\u00f3n de las colas mediante listas.\n<li> <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/codigos\/ColaConDosListas.hs\">ColaConDosListas<\/a>: Implementaci\u00f3n de las colas mediante pares de listas.\n<li> <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/codigos\/GrafoConVectorDeAdyacencia.hs\"> GrafoConVectorDeAdyacencia<\/a>: Implementaci\u00f3n de los grafos mediante vectores de adyacencia.\n<li> <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/codigos\/GrafoConMatrizDeAdyacencia.hs\"> GrafoConMatrizDeAdyacencia<\/a>: Implementaci\u00f3n de los grafos mediante matrices de adyacencia.\n<li> <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/codigos\/RecorridoEnProfundidad.hs\"> RecorridoEnProfundidad<\/a>: Recorrido en profundidad.\n<li> <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/codigos\/RecorridoEnAnchura.hs\"> RecorridoEnAnchura<\/a>: Recorrido en anchura.\n<\/ul>\n<p>El objetivo de la serie es la elaboraci\u00f3n de los temas de TAD del curso de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\">Inform\u00e1tica del Grado en Matem\u00e1ticas<\/a>.<\/p>\n<h3>Fuentes<\/h3>\n<ul>\n<li> <a href=\"http:\/\/www.iro.umontreal.ca\/~lapalme\/Algorithms-functional.html\">Algorithms: A Functional Programming Approach<\/a> por Fethi Rabhi y Guy Lapalme.\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>En este art\u00edculo presento una implementaci\u00f3n 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\u00edculos, de los grafos, de las pilas y de las colas.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[5],"tags":[169,180,270,147,124],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1542"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=1542"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1542\/revisions"}],"predecessor-version":[{"id":1546,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1542\/revisions\/1546"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1542"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1542"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1542"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}