Reconocimiento de camino en un grafo
Dado un grafo no dirigido G, un camino en G es una secuencia de nodos [v(1),v(2),v(3),…,v(n)] tal que para todo i entre 1 y n-1, (v(i),v(i+1)) es una arista de G. Por ejemplo, dados los grafos
1 2 3 |
g1, g2 :: Grafo Int Int g1 = creaGrafo ND (1,3) [(1,2,0),(1,3,0),(2,3,0)] g2 = creaGrafo ND (1,4) [(1,2,0),(1,3,0),(1,4,0),(2,4,0),(3,4,0)] |
la lista [1,2,3] es un camino en g1, pero no es un camino en g2 puesto que la arista (2,3) no existe en g2.
Definir la función
1 |
camino :: Grafo Int Int -> [Int] -> Bool |
tal que (camino g vs) se verifica si la lista de nodos vs es un camino en el grafo g. Por ejemplo,
1 2 |
camino g1 [1,2,3] == True camino g2 [1,2,3] == False |
Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo) que se describe aquí y se encuentra aquí.
Soluciones
[schedule expon=’2019-05-31′ expat=»06:00″]
- Las soluciones se pueden escribir en los comentarios hasta el 31 de mayo.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
Pensamiento
Dijo el árbol: teme al hacha,
palo clavado en el suelo:
contigo la poda es tala.Antonio Machado
[/schedule]
[schedule on=’2019-05-31′ at=»06:00″]
1 2 3 4 5 6 7 8 |
import I1M.Grafo g1, g2 :: Grafo Int Int g1 = creaGrafo ND (1,3) [(1,2,0),(1,3,0),(2,3,0)] g2 = creaGrafo ND (1,4) [(1,2,0),(1,3,0),(1,4,0),(2,4,0),(3,4,0)] camino :: Grafo Int Int -> [Int] -> Bool camino g vs = all (aristaEn g) (zip vs (tail vs)) |
[/schedule]