TAD de los grafos: Grafos conexos
Un grafo no dirigido G se dice conexo, si para cualquier par de vértices u y v en G, existe al menos una trayectoria (una sucesión de vértices adyacentes) de u a v.
Usando el tipo abstracto de datos de los grafos, definir la función,
|
1 |
conexo :: (Ix a, Num p, Eq p) => Grafo a p -> Bool |
tal que conexo g se verifica si el grafo g es conexo. Por ejemplo,
|
1 2 3 |
conexo (creaGrafo' ND (1,3) [(1,2),(3,2)]) == True conexo (creaGrafo' ND (1,4) [(1,2),(3,2),(4,1)]) == True conexo (creaGrafo' ND (1,4) [(1,2),(3,4)]) == False |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
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 |
module Grafo_Grafos_conexos where import TAD.Grafo (Grafo, Orientacion (ND), nodos, creaGrafo') import Data.Ix (Ix) import Grafo_Recorrido_en_anchura (recorridoEnAnchura) import Test.Hspec (Spec, hspec, it, shouldBe) conexo :: (Ix a, Num p, Eq p) => Grafo a p -> Bool conexo g = length (recorridoEnAnchura i g) == n where xs = nodos g i = head xs n = length xs -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ conexo g1 `shouldBe` True it "e2" $ conexo g2 `shouldBe` True it "e3" $ conexo g3 `shouldBe` False where g1, g2, g3 :: Grafo Int Int g1 = creaGrafo' ND (1,3) [(1,2),(3,2)] g2 = creaGrafo' ND (1,4) [(1,2),(3,2),(4,1)] g3 = creaGrafo' ND (1,4) [(1,2),(3,4)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- -- Finished in 0.0003 seconds -- 3 examples, 0 failures |
|
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 |
from src.Grafo_Recorrido_en_anchura import recorridoEnAnchura from src.TAD.Grafo import Grafo, Orientacion, creaGrafo_, nodos def conexo(g: Grafo) -> bool: xs = nodos(g) i = xs[0] n = len(xs) return len(recorridoEnAnchura(i, g)) == n # Verificación # ============ def test_conexo() -> None: g1 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(3,2)]) g2 = creaGrafo_(Orientacion.ND, (1,4), [(1,2),(3,2),(4,1)]) g3 = creaGrafo_(Orientacion.ND, (1,4), [(1,2),(3,4)]) assert conexo(g1) assert conexo(g2) assert not conexo(g3) print("Verificado") # La verificación es # >>> test_conexo() # Verificado |