0votos

Recorrer un grafo en profundidad en Haskell

por josejuan hace 6 años

En anchura recursivo.

Dado un grafo, recorrerlo completamente de forma eficiente.

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
import Data.List (nub) 
 
-- en anchura ingenuo, porque expande todos los nodos todas las veces 
walk' g vs = if a' == [] 
               then vs 
               else walk' g (vs ++ a') 
  where a' = adjacents' g vs 
 
-- en anchura eficiente, expande por capas (como una cebolla) 
walk'' g v = w g [v] [v] 
  where w g ws ps = if a' == [] 
                      then ws 
                      else w g (ws ++ a') a' 
                    where a' = filter (\n -> not $ n `elem` ws) $ adjacents' g ps -- expandimos los pendientes y quitamos visitados 
 
 
 
adjacents :: Eq a => [(a, a)] -> a -> [a] 
adjacents g v = c fst snd ++ c snd fst 
  where c p q = map q $ filter (\x -> p x == v && q x /= v) g 
 
adjacents' :: Eq a => [(a, a)] -> [a] -> [a] 
adjacents' g vs = filter (\n -> not $ n `elem` vs) $ nub $ concatMap (adjacents g) vs 
 
g = [(1, 2), (2, 3), (2, 11), (3, 5), (4, 5), (5, 6), (5, 7), (7, 9), (8, 9), (9, 10), (10, 11)] 
 
 
 
-- previas 
 
-- en profundidad 
walk g v = w v [v] 
  where w v vs = a vs $ adjacents g v 
        a vs [] = vs 
        a vs (x:xs) = if x `elem` vs 
                        then a vs xs 
                        else a (w x (x:vs)) xs 
2 comentarios
0votos

Escrito por jneira hace 6 años

Fiuuu, entonces mi texto de programacion avanzada no es muy correcto, ahi es donde he leido que el recorrido en anchura no es "de naturaleza recursiva" y proponen el siguiente algoritmo
fun RecAnchura(v: nodo, visitado: Vector)
  var
    u,w: nodo
    Q: TCola
  fvar
  Q <- Cola Vacía
  visitado[v] <- cierto
  Encolar(v,Q)
  mientras no vacia(Q) hacer
    u <- Primero(Q)
    Desencolar(u,Q)
    para cada w adyacente a u hacer
      si no visitado[w] entonces
        visitado[w] <- cierto
        Encolar(w,Q)
      fsi
    fpara
  mientras
ffun


por lo que hice un algoritmo corecursivo que va generando la cola y los visitados.
Tal vez con lo de "naturaleza" quieren decir que no es inmediatamente recursivo aunque pueda hacerse ????
0votos

Escrito por josejuan hace 6 años

Claro, voraz.

De hecho es mi solución de haskell, en cierta forma, mi if a' == [] es el mientras no vacia(Q).

Con "no recursivo" yo entiendo que se refieren a la imposibilidad de usar "divide y vencerás", aunque puede paralelizarse usando "divide y vence" usando bloqueos (STM o similar), vaya, que no puede hacerse intrínsecamente paralelo (como pueda ser recorrer un árbol).

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.