TAD de los grafos: Recorrido en profundidad
Usando el tipo abstracto de datos de los grafos, definir la función,
|
1 |
recorridoEnProfundidad :: (Num p, Eq p, Ix v) => v -> Grafo v p -> [v] |
tal que recorridoEnProfundidad i g es el recorrido en profundidad del grafo g desde el vértice i. Por ejemplo, en el grafo
|
1 2 3 4 5 6 7 |
+---> 2 <---+ | | | | 1 --> 3 --> 6 --> 5 | | | | +---> 4 <---------+ |
definido por
|
1 2 |
grafo1 :: Grafo Int Int grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)] |
entonces
|
1 |
recorridoEnProfundidad 1 grafo1 == [1,2,3,6,5,4] |
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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
module Grafo_Recorrido_en_profundidad where import TAD.Grafo (Grafo, Orientacion (D, ND), adyacentes, creaGrafo') import Data.Ix (Ix) import Test.Hspec (Spec, hspec, it, shouldBe) grafo1 :: Grafo Int Int grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)] -- 1ª solución -- =========== recorridoEnProfundidad1 :: (Num p, Eq p, Ix v) => v -> Grafo v p -> [v] recorridoEnProfundidad1 i g = rp [i] [] where rp [] vis = vis rp (c:cs) vis | c `elem` vis = rp cs vis | otherwise = rp (adyacentes g c ++ cs) (vis ++ [c]) -- Traza del cálculo de (recorridoEnProfundidad1 1 grafo1) -- recorridoEnProfundidad1 1 grafo1 -- = rp [1] [] -- = rp [2,3,4] [1] -- = rp [3,4] [1,2] -- = rp [6,4] [1,2,3] -- = rp [2,5,4] [1,2,3,6] -- = rp [5,4] [1,2,3,6] -- = rp [4,4] [1,2,3,6,5] -- = rp [4] [1,2,3,6,5,4] -- = rp [] [1,2,3,6,5,4] -- = [1,2,3,6,5,4] -- 2ª solución -- =========== recorridoEnProfundidad :: (Num p, Eq p, Ix v) => v -> Grafo v p -> [v] recorridoEnProfundidad i g = reverse (rp [i] []) where rp [] vis = vis rp (c:cs) vis | c `elem` vis = rp cs vis | otherwise = rp (adyacentes g c ++ cs) (c:vis) -- Traza del cálculo de (recorridoEnProfundidad 1 grafo1) -- RecorridoEnProfundidad 1 grafo1 -- = reverse (rp [1] []) -- = reverse (rp [2,3,4] [1]) -- = reverse (rp [3,4] [2,1]) -- = reverse (rp [6,4] [3,2,1]) -- = reverse (rp [2,5,4] [6,3,2,1]) -- = reverse (rp [5,4] [6,3,2,1]) -- = reverse (rp [4,4] [5,6,3,2,1]) -- = reverse (rp [4] [4,5,6,3,2,1]) -- = reverse (rp [] [4,5,6,3,2,1]) -- = reverse [4,5,6,3,2,1] -- = [1,2,3,6,5,4] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ recorridoEnProfundidad1 1 grafo1 `shouldBe` [1,2,3,6,5,4] it "e2" $ recorridoEnProfundidad 1 grafo1 `shouldBe` [1,2,3,6,5,4] it "e3" $ recorridoEnProfundidad1 1 grafo2 `shouldBe` [1,2,6,3,5,4] it "e4" $ recorridoEnProfundidad 1 grafo2 `shouldBe` [1,2,6,3,5,4] where grafo2 :: Grafo Int Int grafo2 = creaGrafo' ND (1,6) [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0022 seconds -- 4 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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
from src.TAD.Grafo import Grafo, Orientacion, Vertice, adyacentes, creaGrafo_ grafo1: Grafo = creaGrafo_(Orientacion.D, (1,6), [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)]) # 1ª solución # =========== def recorridoEnProfundidad1(i: Vertice, g: Grafo) -> list[Vertice]: def rp(cs: list[Vertice], vis: list[Vertice]) -> list[Vertice]: if not cs: return vis d, *ds = cs if d in vis: return rp(ds, vis) return rp(adyacentes(g, d) + ds, vis + [d]) return rp([i], []) # Traza del cálculo de recorridoEnProfundidad1(1, grafo1) # recorridoEnProfundidad1(1, grafo1) # = rp([1], []) # = rp([2,3,4], [1]) # = rp([3,4], [1,2]) # = rp([6,4], [1,2,3]) # = rp([2,5,4], [1,2,3,6]) # = rp([5,4], [1,2,3,6]) # = rp([4,4], [1,2,3,6,5]) # = rp([4], [1,2,3,6,5,4]) # = rp([], [1,2,3,6,5,4]) # = [1,2,3,6,5,4] # 2ª solución # =========== def recorridoEnProfundidad(i: Vertice, g: Grafo) -> list[Vertice]: def rp(cs: list[Vertice], vis: list[Vertice]) -> list[Vertice]: if not cs: return vis d, *ds = cs if d in vis: return rp(ds, vis) return rp(adyacentes(g, d) + ds, [d] + vis) return list(reversed(rp([i], []))) # Traza del cálculo de (recorridoEnProfundidad(1, grafo1) # recorridoEnProfundidad(1, grafo1) # = reverse(rp([1], [])) # = reverse(rp([2,3,4], [1])) # = reverse(rp([3,4], [2,1])) # = reverse(rp([6,4], [3,2,1])) # = reverse(rp([2,5,4], [6,3,2,1])) # = reverse(rp([5,4], [6,3,2,1])) # = reverse(rp([4,4], [5,6,3,2,1])) # = reverse(rp([4], [4,5,6,3,2,1])) # = reverse(rp([], [4,5,6,3,2,1])) # = reverse([4,5,6,3,2,1]) # = [1,2,3,6,5,4] # Verificación # ============ def test_recorridoEnProfundidad() -> None: grafo2 = creaGrafo_(Orientacion.ND, (1,6), [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)]) assert recorridoEnProfundidad1(1, grafo1) == [1,2,3,6,5,4] assert recorridoEnProfundidad1(1, grafo2) == [1,2,6,3,5,4] assert recorridoEnProfundidad(1, grafo1) == [1,2,3,6,5,4] assert recorridoEnProfundidad(1, grafo2) == [1,2,6,3,5,4] print("Verificado") # La verificación es # >>> test_recorridoEnProfundidad() # Verificado |