Nodos y conexiones de un grafo
Un grafo no dirigido se representa por la lista de sus arcos. Por ejemplo, el grafo
1 -- 2 -- 4 | \ | | \ | 3 -- 5
se representa por [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)].
Se define el tipo de grafo por
type Grafo a = [(a,a)]
Definir las funciones
nodos :: Eq a => Grafo a -> [a] conectados :: Eq a => Grafo a -> a -> a -> Bool
tales que
- (nodos g) es la lista de los nodos del grafo g. Por ejemplo,
nodos [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] == [1,2,3,4,5]
- (conectados g x y) se verifica si el grafo no dirigido g posee un arco con extremos x e y. Por ejemplo,
conectados [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 3 2 == True conectados [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 2 3 == True conectados [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 3 4 == False
Nota: Escribir la solución en el módulo Grafo para poderlo usar en los siguientes ejercicios.
Soluciones
module Grafo where import Data.List (nub) type Grafo a = [(a,a)] nodos :: Eq a => Grafo a -> [a] nodos g = nub (concat [[x,y] | (x,y) <- g]) conectados :: Eq a => Grafo a -> a -> a -> Bool conectados g x y = (x,y) `elem` g || (y,x) `elem` g