Representaciones de grafos
Los grafos no dirigidos puede representarse mediante matrices de adyacencia y también mediante listas de adyacencia. Por ejemplo, el grafo
1 2 3 4 5 |
1 ----- 2 | \ | | 3 | | / | 4 ----- 5 |
se puede representar por la matriz de adyacencia
1 2 3 4 5 |
|0 1 1 1 0| |1 0 0 0 1| |1 0 0 1 0| |1 0 1 0 1| |0 1 0 1 0| |
donde el elemento (i,j) es 1 si hay una arista entre los vértices i y j y es 0 si no la hay. También se puede representar por la lista de adyacencia
1 |
[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])] |
donde las primeras componentes son los vértices y las segundas la lista de los vértices conectados.
Definir las funciones
1 2 |
matrizAlista :: Matrix Int -> [(Int,[Int])] listaAmatriz :: [(Int,[Int])] -> Matrix Int |
tales que
- (matrizAlista a) es la lista de adyacencia correspondiente a la matriz de adyacencia a. Por ejemplo, definiendo la matriz anterior por
1 2 3 4 5 6 |
ejMatriz :: Matrix Int ejMatriz = fromLists [[0,1,1,1,0], [1,0,0,0,1], [1,0,0,1,0], [1,0,1,0,1], [0,1,0,1,0]] |
se tiene que
1 2 |
λ> matrizAlista ejMatriz [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])] |
- (listaAmatriz ps) es la matriz de adyacencia correspondiente a la lista de adyacencia ps. Por ejemplo,
1 2 3 4 5 6 7 8 |
λ> listaAmatriz [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])] ( 0 1 1 1 0 ) ( 1 0 0 0 1 ) ( 1 0 0 1 0 ) ( 1 0 1 0 1 ) ( 0 1 0 1 0 ) λ> matrizAlista it [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])] |
Soluciones
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
import Data.List (sort) import Data.Matrix ejMatriz :: Matrix Int ejMatriz = fromLists [[0,1,1,1,0], [1,0,0,0,1], [1,0,0,1,0], [1,0,1,0,1], [0,1,0,1,0]] matrizAlista :: Matrix Int -> [(Int,[Int])] matrizAlista a = [(i,[j | j <- [1..n], a!(i,j) == 1]) | i <- [1..n]] where n = nrows a listaAmatriz :: [(Int,[Int])] -> Matrix Int listaAmatriz ps = fromLists [fila n xs | (_,xs) <- sort ps] where n = length ps fila n xs = [f i | i <- [1..n]] where f i | i `elem` xs = 1 | otherwise = 0 |