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
|
1 2 3 |
import I1M.Grafo camino :: Grafo Int Int -> [Int] -> Bool camino g vs = all (aristaEn g) (zip vs (tail vs)) |
Un comentario