{"id":8212,"date":"2023-06-16T06:00:08","date_gmt":"2023-06-16T04:00:08","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8212"},"modified":"2023-06-10T13:26:14","modified_gmt":"2023-06-10T11:26:14","slug":"16-jun-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/16-jun-23\/","title":{"rendered":"TAD de los grafos: Grafos conexos"},"content":{"rendered":"

Un grafo no dirigido G se dice conexo, si para cualquier par de v\u00e9rtices u y v en G, existe al menos una trayectoria (una sucesi\u00f3n de v\u00e9rtices adyacentes) de u a v.<\/p>\n

Usando el tipo abstracto de datos de los grafos<\/a>, definir la funci\u00f3n,<\/p>\n

\n   conexo :: (Ix a, Num p, Eq p) => Grafo a p -> Bool\n<\/pre>\n
tal que conexo g<\/code> se verifica si el grafo g<\/code> es conexo. Por ejemplo,<\/p>\n
\n   conexo (creaGrafo' ND (1,3) [(1,2),(3,2)])        ==  True\n   conexo (creaGrafo' ND (1,4) [(1,2),(3,2),(4,1)])  ==  True\n   conexo (creaGrafo' ND (1,4) [(1,2),(3,4)])        ==  False\n<\/pre>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n
<\/a>
\nSoluciones en Haskell<\/b><\/p>\n
\nmodule Grafo_Grafos_conexos where\n\nimport TAD.Grafo (Grafo, Orientacion (ND), nodos, creaGrafo')\nimport Data.Ix (Ix)\nimport Grafo_Recorrido_en_anchura (recorridoEnAnchura)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\nconexo :: (Ix a, Num p, Eq p) => Grafo a p -> Bool\nconexo g = length (recorridoEnAnchura i g) == n\n  where xs = nodos g\n        i  = head xs\n        n  = length xs\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    conexo g1 `shouldBe` True\n  it \"e2\" $\n    conexo g2 `shouldBe` True\n  it \"e3\" $\n    conexo g3 `shouldBe` False\n  where\n    g1, g2, g3 :: Grafo Int Int\n    g1 = creaGrafo' ND (1,3) [(1,2),(3,2)]\n    g2 = creaGrafo' ND (1,4) [(1,2),(3,2),(4,1)]\n    g3 = creaGrafo' ND (1,4) [(1,2),(3,4)]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--\n--    Finished in 0.0003 seconds\n--    3 examples, 0 failures\n<\/pre>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom src.Grafo_Recorrido_en_anchura import recorridoEnAnchura\nfrom src.TAD.Grafo import Grafo, Orientacion, creaGrafo_, nodos\n\n\ndef conexo(g: Grafo) -> bool:\n    xs = nodos(g)\n    i = xs[0]\n    n = len(xs)\n    return len(recorridoEnAnchura(i, g)) == n\n\n# Verificaci\u00f3n\n# ============\n\ndef test_conexo() -> None:\n    g1 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(3,2)])\n    g2 = creaGrafo_(Orientacion.ND, (1,4), [(1,2),(3,2),(4,1)])\n    g3 = creaGrafo_(Orientacion.ND, (1,4), [(1,2),(3,4)])\n    assert conexo(g1)\n    assert conexo(g2)\n    assert not conexo(g3)\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_conexo()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Un grafo no dirigido G se dice conexo, si para cualquier par de v\u00e9rtices u y v en G, existe al menos una trayectoria (una sucesi\u00f3n de v\u00e9rtices adyacentes) de u a v. Usando el tipo abstracto de datos de los grafos, definir la funci\u00f3n, conexo :: (Ix a, Num p, Eq p) => Grafo…<\/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\/8212"}],"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=8212"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8212\/revisions"}],"predecessor-version":[{"id":8213,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8212\/revisions\/8213"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8212"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8212"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8212"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}