Menu Close

Caminos en un grafo

José A. Alonso,

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
Tagged , , , , , , , , , ,

2 Comments

  1. fercarnav
    Responder 
    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
    Responder 
    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.