{"id":8224,"date":"2023-06-23T06:00:31","date_gmt":"2023-06-23T04:00:31","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8224"},"modified":"2023-06-16T17:47:14","modified_gmt":"2023-06-16T15:47:14","slug":"23-jun-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/23-jun-23\/","title":{"rendered":"TAD de los grafos: Algoritmo de Prim"},"content":{"rendered":"<p>El <a href=\"https:\/\/bit.ly\/466fwRe\">algoritmo de Prim<\/a> calcula un \u00e1rbol recubridor m\u00ednimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un \u00e1rbol, incluyen todos los v\u00e9rtices y donde el valor de la suma de todas las aristas del \u00e1rbol es el m\u00ednimo.<\/p>\n<p>El algoritmo de Prim funciona de la siguiente manera:<\/p>\n<ul>\n<li>Inicializar un \u00e1rbol con un \u00fanico v\u00e9rtice, elegido arbitrariamente, del grafo.<\/li>\n<li>Aumentar el \u00e1rbol por un lado. Llamamos lado a la uni\u00f3n entre dos v\u00e9rtices: de las posibles uniones que pueden conectar el \u00e1rbol a los v\u00e9rtices que no est\u00e1n a\u00fan en el \u00e1rbol, encontrar el lado de menor distancia y unirlo al \u00e1rbol.<\/li>\n<li>Repetir el paso 2 (hasta que todos los v\u00e9rtices pertenezcan al \u00e1rbol)<\/li>\n<\/ul>\n<p>Usando el <a href=\"https:\/\/bit.ly\/45cQ3Fo\">tipo abstracto de datos de los grafos<\/a>, definir la funci\u00f3n,<\/p>\n<pre lang=\"text\">\n   prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]\n<\/pre>\n<p>tal que <code>prim g<\/code> es el \u00e1rbol de expansi\u00f3n m\u00ednimo del grafo <code>g<\/code> calculado mediante el algoritmo de Prim. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por<\/p>\n<pre lang=\"text\">\n   g1, g2, g3, g4 :: Grafo Int Int\n   g1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),\n                            (2,4,55),(2,5,32),\n                            (3,4,61),(3,5,44),\n                            (4,5,93)]\n   g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78),\n                            (2,4,12),(2,5,32),\n                            (3,4,14),(3,5,44),\n                            (4,5,93)]\n   g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                            (2,3,7),\n                            (3,4,8),(3,5,7),\n                            (4,5,5),\n                            (5,6,3),(5,7,9),\n                            (6,7,11)]\n   g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                            (2,3,7),\n                            (3,4,8),(3,5,1),\n                            (4,5,5),\n                            (5,6,3),(5,7,9),\n                            (6,7,11)]\n<\/pre>\n<p>entonces<\/p>\n<pre lang=\"text\">\n   prim g1  == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]\n   prim g2  == [(32,2,5),(12,2,4),(13,1,2),(11,1,3)]\n   prim g3  == [(9,5,7),(7,2,3),(5,5,4),(3,6,5),(6,1,6),(5,1,2)]\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Grafo_Algoritmo_de_Prim where\n\nimport TAD.Grafo (Grafo, Orientacion (ND), aristas, creaGrafo, nodos)\nimport Data.Ix (Ix)\nimport Data.List (delete)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ng1, g2, g3, g4 :: Grafo Int Int\ng1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),\n                         (2,4,55),(2,5,32),\n                         (3,4,61),(3,5,44),\n                         (4,5,93)]\ng2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78),\n                         (2,4,12),(2,5,32),\n                         (3,4,14),(3,5,44),\n                         (4,5,93)]\ng3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                         (2,3,7),\n                         (3,4,8),(3,5,7),\n                         (4,5,5),\n                         (5,6,3),(5,7,9),\n                         (6,7,11)]\ng4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                         (2,3,7),\n                         (3,4,8),(3,5,1),\n                         (4,5,5),\n                         (5,6,3),(5,7,9),\n                         (6,7,11)]\n\nprim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]\nprim g = prim' [n]              -- Nodos colocados\n               ns               -- Nodos por colocar\n               []               -- \u00c1rbol de expansi\u00f3n\n               (aristas g)      -- Aristas del grafo\n  where\n    (n:ns) = nodos g\n    prim' _ _ _  []  = []\n    prim' _ [] ae _  = ae\n    prim' t r  ae as = prim' (v':t) (delete v' r) (e:ae) as\n      where e@(_,_, v') = minimum [(c,u,v)| ((u,v),c) <- as,\n                                             u `elem` t,\n                                             v `elem` r]\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    prim g1 `shouldBe` [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]\n  it \"e2\" $\n    prim g2 `shouldBe` [(32,2,5),(12,2,4),(13,1,2),(11,1,3)]\n  it \"e3\" $\n    prim g3 `shouldBe` [(9,5,7),(7,2,3),(5,5,4),(3,6,5),(6,1,6),(5,1,2)]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--\n--    Finished in 0.0026 seconds\n--    3 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom src.TAD.Grafo import (Grafo, Orientacion, Peso, Vertice, aristas,\n                           creaGrafo, nodos)\n\ng1 = creaGrafo (Orientacion.ND,\n                (1,5),\n                [((1,2),12),((1,3),34),((1,5),78),\n                 ((2,4),55),((2,5),32),\n                 ((3,4),61),((3,5),44),\n                 ((4,5),93)])\ng2 = creaGrafo (Orientacion.ND,\n                (1,5),\n                [((1,2),13),((1,3),11),((1,5),78),\n                 ((2,4),12),((2,5),32),\n                 ((3,4),14),((3,5),44),\n                 ((4,5),93)])\ng3 = creaGrafo (Orientacion.ND,\n                (1,7),\n                [((1,2),5),((1,3),9),((1,5),15),((1,6),6),\n                 ((2,3),7),\n                 ((3,4),8),((3,5),7),\n                 ((4,5),5),\n                 ((5,6),3),((5,7),9),\n                 ((6,7),11)])\ng4 = creaGrafo (Orientacion.ND,\n                (1,7),\n                [((1,2),5),((1,3),9),((1,5),15),((1,6),6),\n                 ((2,3),7),\n                 ((3,4),8),((3,5),1),\n                 ((4,5),5),\n                 ((5,6),3),((5,7),9),\n                 ((6,7),11)])\n\ndef prim(g: Grafo) -> list[tuple[Peso, Vertice, Vertice]]:\n    n, *ns = nodos(g)\n    def prim_(t: list[Vertice],\n              r: list[Vertice],\n              ae: list[tuple[Peso, Vertice, Vertice]],\n              as_: list[tuple[tuple[Vertice, Vertice], Peso]]) \\\n              -> list[tuple[Peso, Vertice, Vertice]]:\n        if not as_:\n            return []\n        if not r:\n            return ae\n        e = min(((c,u,v)\n                 for ((u,v),c) in as_\n                 if u in t and v in r))\n        (_,_, v_) = e\n        return prim_([v_] + t, [x for x in r if x != v_], [e] + ae, as_)\n    return prim_([n], ns, [], aristas(g))\n\n# Verificaci\u00f3n\n# ============\n\ndef test_prim() -> None:\n    assert prim(g1)  == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]\n    assert prim(g2)  == [(32,2,5),(12,2,4),(13,1,2),(11,1,3)]\n    assert prim(g3)  == [(9,5,7),(7,2,3),(5,5,4),(3,6,5),(6,1,6),(5,1,2)]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_prim()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>El algoritmo de Prim calcula un \u00e1rbol recubridor m\u00ednimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un \u00e1rbol, incluyen todos los v\u00e9rtices y donde el valor de la suma de todas las aristas del \u00e1rbol es el m\u00ednimo. El algoritmo de Prim funciona de la siguiente manera:&#8230;<\/p>\n","protected":false},"author":1,"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":[581],"tags":[453],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8224"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=8224"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8224\/revisions"}],"predecessor-version":[{"id":8225,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8224\/revisions\/8225"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8224"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8224"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8224"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}