Menu Close

Caminos en un grafo

Definir las funciones

   grafo   :: [(Int,Int)] -> Grafo Int Int
   caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

tales que

  • (grafo as) es el grafo no dirigido definido cuyas aristas son as. Por ejemplo,
     ghci> grafo [(2,4),(4,5)]
     G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])
  • (caminos g a b) es la lista los caminos en el grafo g desde a hasta b sin pasar dos veces por el mismo nodo. Por ejemplo,
     ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7)
     [[1,3,5,7],[1,3,7]]
     ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7)
     [[2,5,3,7],[2,5,7]]
     ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2)
     [[1,3,5,2],[1,3,7,5,2]]
     ghci> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4
     []
     ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
     109601

Soluciones

import Data.List (sort)
import I1M.Grafo
import I1M.BusquedaEnEspaciosDeEstados
 
grafo :: [(Int,Int)] -> Grafo Int Int
grafo as = creaGrafo ND (m,n) [(x,y,0) | (x,y) <- as]
  where ns = map fst as ++ map snd as
        m  = minimum ns
        n  = maximum ns
 
-- 1ª solución
-- ===========
 
caminos :: Grafo Int Int -> Int -> Int -> [[Int]]
caminos g a b = aux [[b]] where 
  aux [] = []
  aux ((x:xs):yss)
    | x == a    = (x:xs) : aux yss
    | otherwise = aux ([z:x:xs | z <- adyacentes g x
                               , z `notElem` (x:xs)] 
                       ++ yss) 
 
-- 2ª solución (mediante espacio de estados)
-- =========================================
 
caminos2 :: Grafo Int Int -> Int -> Int -> [[Int]]
caminos2 g a b = buscaEE sucesores esFinal inicial
  where inicial          = [b]
        sucesores (x:xs) = [z:x:xs | z <- adyacentes g x
                                   , z `notElem` (x:xs)] 
        esFinal (x:xs)   = x == a
 
-- Comparación de eficiencia
-- =========================
 
--    ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
--    109601
--    (3.57 secs, 500533816 bytes)
--    ghci> length (caminos2 (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
--    109601
--    (3.53 secs, 470814096 bytes)
Posted in Avanzado

2 Comments

  1. fercarnav
    import Data.Array
    import Data.List
     
    data Orientacion = D | ND
                       deriving (Eq, Show)
     
    data Grafo v p = G Orientacion (Array v [p])
                     deriving (Eq, Show)
     
    creaGrafo ::  Orientacion -> (Int,Int) -> [(Int,Int)]  -> Grafo Int (Int,Integer)
    creaGrafo ND cs as  = G ND (matrizVacia //  ([(z, (lista z as)) | z <- zs]))
      where
        matrizVacia = array cs [(x,[]) | x <- range cs]
        zs = nub (concat [[a,b] | (a,b) <-  as])
        lista n xs = [ (c,0) | (c,d) <- xs , d == n ]++ [ (d,0) | (c,d) <- xs , c == n ]
     
    grafo :: [(Int,Int)]  -> Grafo Int (Int,Integer)
    grafo xs = creaGrafo ND (a,b) xs
      where ys = concat[[a,b] | (a,b) <- xs ]
            a = minimum ys
            b = maximum ys
     
    caminos :: Grafo Int (Int,Integer) -> Int -> Int -> [[Int]]
    caminos (G _ g) a b= caminosAux g a b
     
    caminosAux :: Array Int [(Int,Integer)] -> Int -> Int -> [[Int]]
    caminosAux g a b
      | a == b = [[b]]
      | g!a == [] = []
      | otherwise = map (a:) (concatMap (f (g// [(a,[])]) b) (map fst (g!a)))
        where f g b a = caminosAux g a b
  2. Enrique Zubiría
    import I1M.Grafo
    import Data.List (sort)
     
    grafo   :: [(Int,Int)] -> Grafo Int Int
    grafo as = creaGrafo ND (minimum ns, maximum ns) [(v1, v2, 0) | (v1, v2) <- as]
      where ns = concat [[v1, v2] | (v1, v2) <- as]
     
    caminos :: Grafo Int Int -> Int -> Int -> [[Int]]
    caminos g ni nf = cmns [[ni]] []
      where cmns [] cts = cts
            cmns (cv:cvs) cts
              | lcv == nf = cmns cvs (cv:cts)
              | otherwise = cmns ((map (n -> cv++[n]) sns)++cvs) cts
              where lcv = last cv
                    sns = filter (a -> not $ elem a cv) (adyacentes g lcv)

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.