{"id":8222,"date":"2023-06-22T06:00:00","date_gmt":"2023-06-22T04:00:00","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8222"},"modified":"2023-06-16T12:47:11","modified_gmt":"2023-06-16T10:47:11","slug":"22-jun-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/22-jun-23\/","title":{"rendered":"TAD de los grafos: Algoritmo de Kruskal"},"content":{"rendered":"<p>El <a href=\"https:\/\/bit.ly\/3N8bOOg\">algoritmo de Kruskal<\/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 Kruskal funciona de la siguiente manera:<\/p>\n<ul>\n<li>se crea un bosque B (un conjunto de \u00e1rboles), donde cada v\u00e9rtice del grafo es un \u00e1rbol separado<\/li>\n<li>se crea un conjunto C que contenga a todas las aristas del grafo<\/li>\n<li>mientras C es no vac\u00edo,\n<ul>\n<li>eliminar una arista de peso m\u00ednimo de C<\/li>\n<li>si esa arista conecta dos \u00e1rboles diferentes se a\u00f1ade al bosque, combinando los dos \u00e1rboles en un solo \u00e1rbol<\/li>\n<li>en caso contrario, se desecha la arista<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un \u00e1rbol de expansi\u00f3n m\u00ednimo del grafo.<\/p>\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   kruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]\n<\/pre>\n<p>tal que <code>kruskal g<\/code> es el \u00e1rbol de expansi\u00f3n m\u00ednimo del grafo <code>g<\/code> calculado mediante el algoritmo de Kruskal. 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   kruskal g1  ==  [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]\n   kruskal g2  ==  [(32,2,5),(13,1,2),(12,2,4),(11,1,3)]\n   kruskal g3  ==  [(9,5,7),(7,2,3),(6,1,6),(5,4,5),(5,1,2),(3,5,6)]\n   kruskal g4  ==  [(9,5,7),(6,1,6),(5,4,5),(5,1,2),(3,5,6),(1,3,5)]\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_Kruskal where\n\nimport TAD.Grafo (Grafo, Orientacion (ND), aristas, creaGrafo, nodos)\nimport Data.Ix (Ix)\nimport qualified Data.Map as M (Map, (!), fromList, keys, update)\nimport Data.List (sort)\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\nkruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]\nkruskal g = aux (sort [(p,x,y) | ((x,y),p) <- aristas g])\n                (M.fromList [(x,x) | x <- nodos g])\n                []\n                (length (nodos g) - 1)\n  where aux _  _ ae 0 = ae\n        aux [] _ _  _ = error \"Imposible\"\n        aux ((p,x,y):as) d ae n\n          | actualizado = aux as d' ((p,x,y):ae) (n-1)\n          | otherwise   = aux as d ae n\n          where (actualizado,d') = buscaActualiza (x,y) d\n\n-- (raiz d n) es la ra\u00edz de n en el diccionario. Por ejemplo,\n--    raiz (M.fromList [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 5  == 1\n--    raiz (M.fromList [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 2  == 6\nraiz :: (Eq n, Ord n) => M.Map n n -> n -> n\nraiz d x | v == x    = v\n         | otherwise = raiz d v\n  where v = d M.! x\n\n-- (buscaActualiza a d) es el par formado por False y el diccionario d,\n-- si los dos v\u00e9rtices de la arista a tienen la misma ra\u00edz en d y el par\n-- formado por True y la tabla obtenida a\u00f1adi\u00e9ndole a d la arista\n-- formada por el v\u00e9rtice de a de mayor ra\u00edz y la ra\u00edz del v\u00e9rtice de a\n-- de menor ra\u00edz. Y actualizando las raices de todos los elementos\n-- afectados por la ra\u00edz a\u00f1adida. Por ejemplo,\n--   \u03bb> d = M.fromList [(1,1),(2,1),(3,3),(4,4),(5,5),(6,5),(7,7)]\n--   \u03bb> buscaActualiza (5,4) d\n--   (True,fromList [(1,1),(2,1),(3,3),(4,4),(5,4),(6,4),(7,7)])\n--   \u03bb> d' = snd it\n--   \u03bb> buscaActualiza (6,1) d'\n--   (True,fromList [(1,1),(2,1),(3,3),(4,1),(5,1),(6,1),(7,7)])\nbuscaActualiza :: (Eq n, Ord n) => (n,n) -> M.Map n n -> (Bool,M.Map n n)\nbuscaActualiza (x,y) d\n  | x' == y'  = (False, d)\n  | y' <  x'  = (True, modificaR x (d M.! x) y' d)\n  | otherwise = (True, modificaR y (d M.! y) x' d)\n  where x' = raiz d x\n        y' = raiz d y\n\n-- (modificaR x y y' d) actualiza d como sigue:\n-- + el valor de todas las claves z con valor y es y'\n-- + el valor de todas las claves z con (z > x) con valor x es y'\nmodificaR :: (Eq n, Ord n) => n -> n -> n -> M.Map n n -> M.Map n n\nmodificaR x y y' d = aux2 ds (aux1 cs d)\n  where cs = M.keys d\n        ds = filter (>x) cs\n        aux1 [] tb = tb\n        aux1 (a:as) tb | tb M.! a == y = aux1 as (M.update (\\_ -> Just y') a tb)\n                       | otherwise     = aux1 as tb\n        aux2 [] tb = tb\n        aux2 (b:bs) tb | tb M.! b == x = aux2 bs (M.update (\\_ -> Just y') b tb)\n                       | otherwise     = aux2 bs tb\n\n-- Traza del diccionario correspondiente al grafo g3\n-- =================================================\n\n-- Lista de aristas, ordenadas seg\u00fan su peso:\n-- [(3,5,6),(5,1,2),(5,4,5),(6,1,6),(7,2,3),(7,3,5),(8,3,4),(9,1,3),(9,5,7),(11,6,7),(15,1,5)]\n--\n-- Inicial\n--   fromList [(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7)]\n--\n-- Despu\u00e9s de a\u00f1adir la arista (5,6) de peso 3\n--   fromList [(1,1),(2,2),(3,3),(4,4),(5,5),(6,5),(7,7)]\n--\n-- Despu\u00e9s de a\u00f1adir la arista (1,2) de peso 5\n--   fromList [(1,1),(2,1),(3,3),(4,4),(5,5),(6,5),(7,7)]\n--\n-- Despu\u00e9s de a\u00f1adir la arista (4,5) de peso 5\n--   fromList [(1,1),(2,1),(3,3),(4,4),(5,4),(6,4),(7,7)]\n--\n-- Despu\u00e9s de a\u00f1adir la arista (1,6) de peso 6\n--   fromList [(1,1),(2,1),(3,3),(4,1),(5,1),(6,1),(7,7)]\n--\n-- Despu\u00e9s de a\u00f1adir la arista (2,3) de peso 7\n--   fromList [(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,7)]\n--\n-- Las posibles aristas a a\u00f1adir son:\n-- + la (3,5) con peso 7, que no es posible pues la ra\u00edz de 3\n--   coincide con la ra\u00edz de 5, por lo que formar\u00eda un ciclo\n-- + la (3,4) con peso 8, que no es posible pues la ra\u00edz de 3\n--   coincide con la ra\u00edz de 4, por lo que formar\u00eda un ciclo\n-- + la (1,3) con peso 9, que no es posible pues la ra\u00edz de 3\n--   coincide con la ra\u00edz de 1, por lo que formar\u00eda un ciclo\n-- + la (5,7) con peso 9, que no forma ciclo\n--\n-- Despu\u00e9s de a\u00f1adir la arista (5,7) con peso 9\n--    fromList [(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,1)]\n--\n-- No es posible a\u00f1adir m\u00e1s aristas, pues formar\u00edan ciclos.\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    kruskal g1 `shouldBe` [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]\n  it \"e2\" $\n    kruskal g2 `shouldBe` [(32,2,5),(13,1,2),(12,2,4),(11,1,3)]\n  it \"e3\" $\n    kruskal g3 `shouldBe` [(9,5,7),(7,2,3),(6,1,6),(5,4,5),(5,1,2),(3,5,6)]\n  it \"e4\" $\n    kruskal g4 `shouldBe` [(9,5,7),(6,1,6),(5,4,5),(5,1,2),(3,5,6),(1,3,5)]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--\n--    Finished in 0.0044 seconds\n--    4 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\n# raiz(d, n) es la ra\u00edz de n en el diccionario. Por ejemplo,\n#    raiz({1:1, 3:1, 4:3, 5:4, 2:6, 6:6}, 5)  == 1\n#    raiz({1:1, 3:1, 4:3, 5:4, 2:6, 6:6}, 2)  == 6\ndef raiz(d: dict[Vertice, Vertice], x: Vertice) -> Vertice:\n    v = d[x]\n    if v == x:\n        return v\n    return raiz(d, v)\n\n# modificaR(x, y, y_, d) actualiza d como sigue:\n# + el valor de todas las claves z con valor y es y_\n# + el valor de todas las claves z con (z > x) con valor x es y_\ndef modificaR(x: Vertice,\n              y: Vertice,\n              y_: Vertice,\n              d: dict[Vertice, Vertice]) -> dict[Vertice, Vertice]:\n    def aux1(vs: list[Vertice],\n             tb: dict[Vertice, Vertice],\n             y: Vertice) -> dict[Vertice, Vertice]:\n        for a in vs:\n            if tb[a] == y:\n                tb[a] = y_\n        return tb\n\n    def aux2(vs: list[Vertice],\n             tb: dict[Vertice, Vertice],\n             y_: Vertice) -> dict[Vertice, Vertice]:\n        for b in vs:\n            if tb[b] == x:\n                tb[b] = y_\n        return tb\n\n    cs = list(d.keys())\n    ds = [c for c in cs if c > x]\n\n    tb = aux1(cs, d, y)\n    tb = aux2(ds, tb, y_)\n\n    return tb\n\n# buscaActualiza(a, d) es el par formado por False y el diccionario d,\n# si los dos v\u00e9rtices de la arista a tienen la misma ra\u00edz en d y el par\n# formado por True y la tabla obtenida a\u00f1adi\u00e9ndole a d la arista\n# formada por el v\u00e9rtice de a de mayor ra\u00edz y la ra\u00edz del v\u00e9rtice de a\n# de menor ra\u00edz. Y actualizando las raices de todos los elementos\n# afectados por la ra\u00edz a\u00f1adida. Por ejemplo,\n#    >>> buscaActualiza((5,4), {1:1, 2:1, 3:3, 4:4, 5:5, 6:5, 7:7})\n#    (True, {1: 1, 2: 1, 3: 3, 4: 4, 5: 4, 6: 4, 7: 7})\n#    >>> buscaActualiza((6,1), {1:1, 2:1, 3:3, 4:4, 5:4, 6:4, 7:7})\n#    (True, {1: 1, 2: 1, 3: 3, 4: 1, 5: 1, 6: 1, 7: 7})\n#    >>> buscaActualiza((6,2), {1:1, 2:1, 3:3, 4:1, 5:4, 6:5, 7:7})\n#    (False, {1: 1, 2: 1, 3: 3, 4: 1, 5: 4, 6: 5, 7: 7})\ndef buscaActualiza(a: tuple[Vertice, Vertice],\n                   d: dict[Vertice, Vertice]) -> tuple[bool,\n                                                       dict[Vertice, Vertice]]:\n    x, y = a\n    x_ = raiz(d, x)\n    y_ = raiz(d, y)\n\n    if x_ == y_:\n        return False, d\n    if y_ < x_:\n        return True, modificaR(x, d[x], y_, d)\n    return True, modificaR(y, d[y], x_, d)\n\ndef kruskal(g: Grafo) -> list[tuple[Peso, Vertice, Vertice]]:\n    def aux(as_: list[tuple[Peso, Vertice, Vertice]],\n            d: dict[Vertice, Vertice],\n            ae: list[tuple[Peso, Vertice, Vertice]],\n            n: int) -> list[tuple[Peso, Vertice, Vertice]]:\n        if n == 0:\n            return ae\n        p, x, y = as_[0]\n        actualizado, d = buscaActualiza((x, y), d)\n        if actualizado:\n            return aux(as_[1:], d, [(p, x, y)] + ae, n - 1)\n        return aux(as_[1:], d, ae, n)\n    return aux(list(sorted([(p, x, y) for ((x, y), p) in aristas(g)])),\n               {x: x for x in nodos(g)},\n               [],\n               len(nodos(g)) - 1)\n\n# Traza del diccionario correspondiente al grafo g3\n# =================================================\n\n# Lista de aristas, ordenadas seg\u00fan su peso:\n# [(3,5,6),(5,1,2),(5,4,5),(6,1,6),(7,2,3),(7,3,5),(8,3,4),(9,1,3),(9,5,7),(11,6,7),(15,1,5)]\n#\n# Inicial\n#   {1:1, 2:2, 3:3, 4:4, 5:5, 6:6, 7:7}\n#\n# Despu\u00e9s de a\u00f1adir la arista (5,6) de peso 3\n#   {1:1, 2:2, 3:3, 4:4, 5:5, 6:5, 7:7}\n#\n# Despu\u00e9s de a\u00f1adir la arista (1,2) de peso 5\n#   {1:1, 2:1, 3:3, 4:4, 5:5, 6:5, 7:7}\n#\n# Despu\u00e9s de a\u00f1adir la arista (4,5) de peso 5\n#   {1:1, 2:1, 3:3, 4:4, 5:4, 6:4, 7:7}\n#\n# Despu\u00e9s de a\u00f1adir la arista (1,6) de peso 6\n#   {1:1, 2:1, 3:3, 4:1, 5:1, 6:1, 7:7}\n#\n# Despu\u00e9s de a\u00f1adir la arista (2,3) de peso 7\n#   {1:1, 2:1, 3:1, 4:1, 5:1, 6:1, 7:7}\n#\n# Las posibles aristas a a\u00f1adir son:\n# + la (3,5) con peso 7, que no es posible pues la ra\u00edz de 3\n#   coincide con la ra\u00edz de 5, por lo que formar\u00eda un ciclo\n# + la (3,4) con peso 8, que no es posible pues la ra\u00edz de 3\n#   coincide con la ra\u00edz de 4, por lo que formar\u00eda un ciclo\n# + la (1,3) con peso 9, que no es posible pues la ra\u00edz de 3\n#   coincide con la ra\u00edz de 1, por lo que formar\u00eda un ciclo\n# + la (5,7) con peso 9, que no forma ciclo\n#\n# Despu\u00e9s de a\u00f1adir la arista (5,7) con peso 9\n#    {1:1, 2:1, 3:1, 4:1, 5:1, 6:1, 7:1}\n#\n# No es posible a\u00f1adir m\u00e1s aristas, pues formar\u00edan ciclos.\n\n# Verificaci\u00f3n\n# ============\n\ndef test_kruskal() -> None:\n    assert kruskal(g1) == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]\n    assert kruskal(g2) == [(32,2,5),(13,1,2),(12,2,4),(11,1,3)]\n    assert kruskal(g3) == [(9,5,7),(7,2,3),(6,1,6),(5,4,5),(5,1,2),(3,5,6)]\n    assert kruskal(g4) == [(9,5,7),(6,1,6),(5,4,5),(5,1,2),(3,5,6),(1,3,5)]\n    print(\"Vefificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_kruskal()\n#    Vefificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>El algoritmo de Kruskal 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 Kruskal 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\/8222"}],"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=8222"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8222\/revisions"}],"predecessor-version":[{"id":8223,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8222\/revisions\/8223"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8222"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8222"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8222"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}