0votos

Recorrer un grafo en profundidad en Haskell

por josejuan hace 6 años

Por recursión.

Dado un grafo, recorrerlo completamente de forma eficiente.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 
 
 
 
 
 
 
adjacents g v = c fst snd ++ c snd fst 
  where c p q = map q $ filter (\x -> p x == v && q x /= v) g 
 
g = [(1, 2), (2, 3), (2, 11), (3, 5), (4, 5), (5, 6), (5, 7), (7, 9), (8, 9), (9, 10), (10, 11)] 
3 comentarios
0votos

Escrito por jneira hace 6 años

Canonico!!
Pero me interesaba mas el recorrido en anchura, que parece ser que no puede hacerse recursivamente aunque si corecursivamente: los breadthWalk en https://gist.github.com/4069104
Sin embargo no me gusta como han quedado, ni con unfoldr ni con iterate
0votos

Escrito por josejuan hace 6 años

Uhm... por aquí puse yo uno en anchura ¡ah sí, en el desafío de los amigos!, aunque allí no era eficiente.

En anchura no debería ser mucho más diferente, veamos...
0votos

Escrito por josejuan hace 6 años

No, no es muy diferente (ver otra solución)

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.