La semana en Exercitium (24 de junio de 2023)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas sobre el tipo abstracto de datos de los grafos
- 1. Coloreado correcto de un mapa
- 2. Nodos aislados de un grafo
- 3. Nodos conectados en un grafo
- 4. Algoritmo de Kruskal
- 5. Algoritmo de Prim
A continuación se muestran las soluciones.
1. Coloreado correcto de un mapa
Un mapa se puede representar mediante un grafo donde los vértices son las regiones del mapa y hay una arista entre dos vértices si las correspondientes regiones son vecinas. Por ejemplo, el mapa siguiente
1 2 3 4 5 6 7 8 9 |
+----------+----------+ | 1 | 2 | +----+-----+-----+----+ | | | | | 3 | 4 | 5 | | | | | +----+-----+-----+----+ | 6 | 7 | +----------+----------+ |
se pueden representar por
1 2 3 4 |
mapa :: Grafo Int Int mapa = creaGrafo' ND (1,7) [(1,2),(1,3),(1,4),(2,4),(2,5),(3,4), (3,6),(4,5),(4,6),(4,7),(5,7),(6,7)] |
Para colorear el mapa se dispone de 4 colores definidos por
1 2 |
data Color = A | B | C | D deriving (Eq, Show) |
Usando el tipo abstracto de datos de los grafos, definir la función,
1 |
correcta :: [(Int,Color)] -> Grafo Int Int -> Bool |
tal que correcta ncs m
se verifica si ncs
es una coloración del mapa m
tal que todos las regiones vecinas tienen colores distintos. Por ejemplo,
1 2 |
correcta [(1,A),(2,B),(3,B),(4,C),(5,A),(6,A),(7,B)] mapa == True correcta [(1,A),(2,B),(3,A),(4,C),(5,A),(6,A),(7,B)] mapa == False |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
module Grafo_Coloreado_correcto_de_un_mapa where import TAD.Grafo (Grafo, Orientacion (ND), aristas, creaGrafo') import Test.Hspec (Spec, hspec, it, shouldBe) mapa :: Grafo Int Int mapa = creaGrafo' ND (1,7) [(1,2),(1,3),(1,4),(2,4),(2,5),(3,4), (3,6),(4,5),(4,6),(4,7),(5,7),(6,7)] data Color = A | B | C | E deriving (Eq, Show) correcta :: [(Int,Color)] -> Grafo Int Int -> Bool correcta ncs g = and [color x /= color y | ((x,y),_) <- aristas g] where color x = head [c | (y,c) <- ncs, y == x] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ correcta [(1,A),(2,B),(3,B),(4,C),(5,A),(6,A),(7,B)] mapa `shouldBe` True it "e2" $ correcta [(1,A),(2,B),(3,A),(4,C),(5,A),(6,A),(7,B)] mapa `shouldBe` False -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.0004 seconds -- 2 examples, 0 failures |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
from enum import Enum from src.TAD.Grafo import Grafo, Orientacion, aristas, creaGrafo_ mapa: Grafo = creaGrafo_(Orientacion.ND, (1,7), [(1,2),(1,3),(1,4),(2,4),(2,5),(3,4), (3,6),(4,5),(4,6),(4,7),(5,7),(6,7)]) Color = Enum('Color', ['A', 'B', 'C', 'E']) def correcta(ncs: list[tuple[int, Color]], g: Grafo) -> bool: def color(x: int) -> Color: return [c for (y, c) in ncs if y == x][0] return all(color(x) != color(y) for ((x, y), _) in aristas(g)) # Verificación # ============ def test_correcta() -> None: assert correcta([(1,Color.A), (2,Color.B), (3,Color.B), (4,Color.C), (5,Color.A), (6,Color.A), (7,Color.B)], mapa) assert not correcta([(1,Color.A), (2,Color.B), (3,Color.A), (4,Color.C), (5,Color.A), (6,Color.A), (7,Color.B)], mapa) print("Verificado") # La verificación es # >>> test_correcta() # Verificado |
2. Nodos aislados de un grafo
Dado un grafo dirigido G, diremos que un nodo está aislado si o bien de dicho nodo no sale ninguna arista o bien no llega al nodo ninguna arista. Por ejemplo, en el siguiente grafo
1 2 3 |
grafo1 :: Grafo Int Int grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6), (5,4),(6,2),(6,5)] |
podemos ver que del nodo 1 salen 3 aristas pero no llega ninguna, por lo que lo consideramos aislado. Así mismo, a los nodos 2 y 4 llegan aristas pero no sale ninguna, por tanto también estarán aislados.
Usando el tipo abstracto de datos de los grafos, definir la función,
1 |
aislados :: (Ix v, Num p) => Grafo v p -> [v] |
tal que aislados g
es la lista de nodos aislados del grafo g
. Por ejemplo,
1 |
aislados grafo1 == [1,2,4] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
module Grafo_Nodos_aislados_de_un_grafo where import TAD.Grafo (Grafo, Orientacion (D), adyacentes, nodos, creaGrafo') import Data.Ix (Ix) import Grafo_Incidentes_de_un_vertice (incidentes) import Test.Hspec (Spec, hspec, it, shouldBe) grafo1 :: Grafo Int Int grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6), (5,4),(6,2),(6,5)] aislados :: (Ix v, Num p) => Grafo v p -> [v] aislados g = [n | n <- nodos g, null (adyacentes g n) || null (incidentes g n)] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ aislados grafo1 `shouldBe` [1,2,4] -- La verificación es -- λ> verifica -- -- e1 -- -- Finished in 0.0008 seconds -- 1 example, 0 failures |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
from src.Grafo_Incidentes_de_un_vertice import incidentes from src.TAD.Grafo import (Grafo, Orientacion, Vertice, adyacentes, creaGrafo_, nodos) grafo1: Grafo = creaGrafo_(Orientacion.D, (1,6), [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)]) def aislados(g: Grafo) -> list[Vertice]: return [n for n in nodos(g) if not adyacentes(g, n) or not incidentes(g, n)] # Verificación # ============ def test_aislados() -> None: assert aislados(grafo1) == [1, 2, 4] print("Verificado") # La verificación es # >>> test_aislados() # Verificado |
3. Nodos conectados en un grafo
Usando el tipo abstracto de datos de los grafos, definir la función,
1 |
conectados :: Grafo Int Int -> Int -> Int -> Bool |
tal que conectados g v1 v2
se verifica si los vértices v1
y v2
están conectados en el grafo g
. Por ejemplo, si grafo1 es el grafo definido por
1 2 3 |
grafo1 :: Grafo Int Int grafo1 = creaGrafo' D (1,6) [(1,3),(1,5),(3,5),(5,1),(5,50), (2,4),(2,6),(4,6),(4,4),(6,4)] |
entonces,
1 2 3 4 |
conectados grafo1 1 3 == True conectados grafo1 1 4 == False conectados grafo1 6 2 == False conectados grafo1 3 1 == True |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
module Grafo_Nodos_conectados_en_un_grafo where import TAD.Grafo (Grafo, Orientacion (D, ND), adyacentes, creaGrafo') import Data.List (union) import Test.Hspec (Spec, hspec, it, shouldBe) conectados :: Grafo Int Int -> Int -> Int -> Bool conectados g v1 v2 = v2 `elem` conectadosAux g [] [v1] conectadosAux :: Grafo Int Int -> [Int] -> [Int] -> [Int] conectadosAux _ vs [] = vs conectadosAux g vs (w:ws) | w `elem` vs = conectadosAux g vs ws | otherwise = conectadosAux g ([w] `union` vs) (ws `union` adyacentes g w) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ conectados grafo1 1 3 `shouldBe` True it "e2" $ conectados grafo1 1 4 `shouldBe` False it "e3" $ conectados grafo1 6 2 `shouldBe` False it "e4" $ conectados grafo1 3 1 `shouldBe` True it "e5" $ conectados grafo2 1 3 `shouldBe` True it "e6" $ conectados grafo2 1 4 `shouldBe` False it "e7" $ conectados grafo2 6 2 `shouldBe` True it "e8" $ conectados grafo2 3 1 `shouldBe` True where grafo1, grafo2 :: Grafo Int Int grafo1 = creaGrafo' D (1,6) [(1,3),(1,5),(3,5),(5,1),(5,50), (2,4),(2,6),(4,6),(4,4),(6,4)] grafo2 = creaGrafo' ND (1,6) [(1,3),(1,5),(3,5),(5,1),(5,50), (2,4),(2,6),(4,6),(4,4),(6,4)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- e5 -- e6 -- e7 -- e8 -- -- Finished in 0.0032 seconds -- 8 examples, 0 failures |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
from src.TAD.Grafo import Grafo, Orientacion, Vertice, adyacentes, creaGrafo_ def unionV(xs: list[Vertice], ys: list[Vertice]) -> list[Vertice]: return list(set(xs) | set(ys)) def conectadosAux(g: Grafo, vs: list[Vertice], ws: list[Vertice]) -> list[Vertice]: if not ws: return vs w, *ws = ws if w in vs: return conectadosAux(g, vs, ws) return conectadosAux(g, unionV([w], vs), unionV(ws, adyacentes(g, w))) def conectados(g: Grafo, v1: Vertice, v2: Vertice) -> bool: return v2 in conectadosAux(g, [], [v1]) # Verificación # ============ def test_conectados() -> None: grafo1 = creaGrafo_(Orientacion.D, (1,6), [(1,3),(1,5),(3,5),(5,1),(5,50), (2,4),(2,6),(4,6),(4,4),(6,4)]) grafo2 = creaGrafo_(Orientacion.ND, (1,6), [(1,3),(1,5),(3,5),(5,1),(5,50), (2,4),(2,6),(4,6),(4,4),(6,4)]) assert conectados(grafo1, 1, 3) assert not conectados(grafo1, 1, 4) assert not conectados(grafo1, 6, 2) assert conectados(grafo1, 3, 1) assert conectados(grafo2, 1, 3) assert not conectados(grafo2, 1, 4) assert conectados(grafo2, 6, 2) assert conectados(grafo2, 3, 1) print("Verificado") # La verificación es # >>> test_conectados() # Verificado |
4. Algoritmo de Kruskal
El algoritmo de Kruskal calcula un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.
El algoritmo de Kruskal funciona de la siguiente manera:
- se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separado
- se crea un conjunto C que contenga a todas las aristas del grafo
- mientras C es no vacío,
- eliminar una arista de peso mínimo de C
- si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol
- en caso contrario, se desecha la arista
Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de expansión mínimo del grafo.
Usando el tipo abstracto de datos de los grafos, definir la función,
1 |
kruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)] |
tal que kruskal g
es el árbol de expansión mínimo del grafo g
calculado mediante el algoritmo de Kruskal. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
g1, g2, g3, g4 :: Grafo Int Int g1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78), (2,4,12),(2,5,32), (3,4,14),(3,5,44), (4,5,93)] g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,7), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,1), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] |
entonces
1 2 3 4 |
kruskal g1 == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)] kruskal g2 == [(32,2,5),(13,1,2),(12,2,4),(11,1,3)] kruskal g3 == [(9,5,7),(7,2,3),(6,1,6),(5,4,5),(5,1,2),(3,5,6)] kruskal g4 == [(9,5,7),(6,1,6),(5,4,5),(5,1,2),(3,5,6),(1,3,5)] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 |
module Grafo_Algoritmo_de_Kruskal where import TAD.Grafo (Grafo, Orientacion (ND), aristas, creaGrafo, nodos) import Data.Ix (Ix) import qualified Data.Map as M (Map, (!), fromList, keys, update) import Data.List (sort) import Test.Hspec (Spec, hspec, it, shouldBe) g1, g2, g3, g4 :: Grafo Int Int g1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78), (2,4,12),(2,5,32), (3,4,14),(3,5,44), (4,5,93)] g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,7), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,1), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] kruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)] kruskal g = aux (sort [(p,x,y) | ((x,y),p) <- aristas g]) (M.fromList [(x,x) | x <- nodos g]) [] (length (nodos g) - 1) where aux _ _ ae 0 = ae aux [] _ _ _ = error "Imposible" aux ((p,x,y):as) d ae n | actualizado = aux as d' ((p,x,y):ae) (n-1) | otherwise = aux as d ae n where (actualizado,d') = buscaActualiza (x,y) d -- (raiz d n) es la raíz de n en el diccionario. Por ejemplo, -- raiz (M.fromList [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 5 == 1 -- raiz (M.fromList [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 2 == 6 raiz :: (Eq n, Ord n) => M.Map n n -> n -> n raiz d x | v == x = v | otherwise = raiz d v where v = d M.! x -- (buscaActualiza a d) es el par formado por False y el diccionario d, -- si los dos vértices de la arista a tienen la misma raíz en d y el par -- formado por True y la tabla obtenida añadiéndole a d la arista -- formada por el vértice de a de mayor raíz y la raíz del vértice de a -- de menor raíz. Y actualizando las raices de todos los elementos -- afectados por la raíz añadida. Por ejemplo, -- λ> d = M.fromList [(1,1),(2,1),(3,3),(4,4),(5,5),(6,5),(7,7)] -- λ> buscaActualiza (5,4) d -- (True,fromList [(1,1),(2,1),(3,3),(4,4),(5,4),(6,4),(7,7)]) -- λ> d' = snd it -- λ> buscaActualiza (6,1) d' -- (True,fromList [(1,1),(2,1),(3,3),(4,1),(5,1),(6,1),(7,7)]) buscaActualiza :: (Eq n, Ord n) => (n,n) -> M.Map n n -> (Bool,M.Map n n) buscaActualiza (x,y) d | x' == y' = (False, d) | y' < x' = (True, modificaR x (d M.! x) y' d) | otherwise = (True, modificaR y (d M.! y) x' d) where x' = raiz d x y' = raiz d y -- (modificaR x y y' d) actualiza d como sigue: -- + el valor de todas las claves z con valor y es y' -- + el valor de todas las claves z con (z > x) con valor x es y' modificaR :: (Eq n, Ord n) => n -> n -> n -> M.Map n n -> M.Map n n modificaR x y y' d = aux2 ds (aux1 cs d) where cs = M.keys d ds = filter (>x) cs aux1 [] tb = tb aux1 (a:as) tb | tb M.! a == y = aux1 as (M.update (\_ -> Just y') a tb) | otherwise = aux1 as tb aux2 [] tb = tb aux2 (b:bs) tb | tb M.! b == x = aux2 bs (M.update (\_ -> Just y') b tb) | otherwise = aux2 bs tb -- Traza del diccionario correspondiente al grafo g3 -- ================================================= -- Lista de aristas, ordenadas según su peso: -- [(3,5,6),(5,1,2),(5,4,5),(6,1,6),(7,2,3),(7,3,5),(8,3,4),(9,1,3),(9,5,7),(11,6,7),(15,1,5)] -- -- Inicial -- fromList [(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7)] -- -- Después de añadir la arista (5,6) de peso 3 -- fromList [(1,1),(2,2),(3,3),(4,4),(5,5),(6,5),(7,7)] -- -- Después de añadir la arista (1,2) de peso 5 -- fromList [(1,1),(2,1),(3,3),(4,4),(5,5),(6,5),(7,7)] -- -- Después de añadir la arista (4,5) de peso 5 -- fromList [(1,1),(2,1),(3,3),(4,4),(5,4),(6,4),(7,7)] -- -- Después de añadir la arista (1,6) de peso 6 -- fromList [(1,1),(2,1),(3,3),(4,1),(5,1),(6,1),(7,7)] -- -- Después de añadir la arista (2,3) de peso 7 -- fromList [(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,7)] -- -- Las posibles aristas a añadir son: -- + la (3,5) con peso 7, que no es posible pues la raíz de 3 -- coincide con la raíz de 5, por lo que formaría un ciclo -- + la (3,4) con peso 8, que no es posible pues la raíz de 3 -- coincide con la raíz de 4, por lo que formaría un ciclo -- + la (1,3) con peso 9, que no es posible pues la raíz de 3 -- coincide con la raíz de 1, por lo que formaría un ciclo -- + la (5,7) con peso 9, que no forma ciclo -- -- Después de añadir la arista (5,7) con peso 9 -- fromList [(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,1)] -- -- No es posible añadir más aristas, pues formarían ciclos. -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ kruskal g1 `shouldBe` [(55,2,4),(34,1,3),(32,2,5),(12,1,2)] it "e2" $ kruskal g2 `shouldBe` [(32,2,5),(13,1,2),(12,2,4),(11,1,3)] it "e3" $ kruskal g3 `shouldBe` [(9,5,7),(7,2,3),(6,1,6),(5,4,5),(5,1,2),(3,5,6)] it "e4" $ kruskal g4 `shouldBe` [(9,5,7),(6,1,6),(5,4,5),(5,1,2),(3,5,6),(1,3,5)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0044 seconds -- 4 examples, 0 failures |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 |
from src.TAD.Grafo import (Grafo, Orientacion, Peso, Vertice, aristas, creaGrafo, nodos) g1 = creaGrafo (Orientacion.ND, (1,5), [((1,2),12),((1,3),34),((1,5),78), ((2,4),55),((2,5),32), ((3,4),61),((3,5),44), ((4,5),93)]) g2 = creaGrafo (Orientacion.ND, (1,5), [((1,2),13),((1,3),11),((1,5),78), ((2,4),12),((2,5),32), ((3,4),14),((3,5),44), ((4,5),93)]) g3 = creaGrafo (Orientacion.ND, (1,7), [((1,2),5),((1,3),9),((1,5),15),((1,6),6), ((2,3),7), ((3,4),8),((3,5),7), ((4,5),5), ((5,6),3),((5,7),9), ((6,7),11)]) g4 = creaGrafo (Orientacion.ND, (1,7), [((1,2),5),((1,3),9),((1,5),15),((1,6),6), ((2,3),7), ((3,4),8),((3,5),1), ((4,5),5), ((5,6),3),((5,7),9), ((6,7),11)]) # raiz(d, n) es la raíz de n en el diccionario. Por ejemplo, # raiz({1:1, 3:1, 4:3, 5:4, 2:6, 6:6}, 5) == 1 # raiz({1:1, 3:1, 4:3, 5:4, 2:6, 6:6}, 2) == 6 def raiz(d: dict[Vertice, Vertice], x: Vertice) -> Vertice: v = d[x] if v == x: return v return raiz(d, v) # modificaR(x, y, y_, d) actualiza d como sigue: # + el valor de todas las claves z con valor y es y_ # + el valor de todas las claves z con (z > x) con valor x es y_ def modificaR(x: Vertice, y: Vertice, y_: Vertice, d: dict[Vertice, Vertice]) -> dict[Vertice, Vertice]: def aux1(vs: list[Vertice], tb: dict[Vertice, Vertice], y: Vertice) -> dict[Vertice, Vertice]: for a in vs: if tb[a] == y: tb[a] = y_ return tb def aux2(vs: list[Vertice], tb: dict[Vertice, Vertice], y_: Vertice) -> dict[Vertice, Vertice]: for b in vs: if tb[b] == x: tb[b] = y_ return tb cs = list(d.keys()) ds = [c for c in cs if c > x] tb = aux1(cs, d, y) tb = aux2(ds, tb, y_) return tb # buscaActualiza(a, d) es el par formado por False y el diccionario d, # si los dos vértices de la arista a tienen la misma raíz en d y el par # formado por True y la tabla obtenida añadiéndole a d la arista # formada por el vértice de a de mayor raíz y la raíz del vértice de a # de menor raíz. Y actualizando las raices de todos los elementos # afectados por la raíz añadida. Por ejemplo, # >>> buscaActualiza((5,4), {1:1, 2:1, 3:3, 4:4, 5:5, 6:5, 7:7}) # (True, {1: 1, 2: 1, 3: 3, 4: 4, 5: 4, 6: 4, 7: 7}) # >>> buscaActualiza((6,1), {1:1, 2:1, 3:3, 4:4, 5:4, 6:4, 7:7}) # (True, {1: 1, 2: 1, 3: 3, 4: 1, 5: 1, 6: 1, 7: 7}) # >>> buscaActualiza((6,2), {1:1, 2:1, 3:3, 4:1, 5:4, 6:5, 7:7}) # (False, {1: 1, 2: 1, 3: 3, 4: 1, 5: 4, 6: 5, 7: 7}) def buscaActualiza(a: tuple[Vertice, Vertice], d: dict[Vertice, Vertice]) -> tuple[bool, dict[Vertice, Vertice]]: x, y = a x_ = raiz(d, x) y_ = raiz(d, y) if x_ == y_: return False, d if y_ < x_: return True, modificaR(x, d[x], y_, d) return True, modificaR(y, d[y], x_, d) def kruskal(g: Grafo) -> list[tuple[Peso, Vertice, Vertice]]: def aux(as_: list[tuple[Peso, Vertice, Vertice]], d: dict[Vertice, Vertice], ae: list[tuple[Peso, Vertice, Vertice]], n: int) -> list[tuple[Peso, Vertice, Vertice]]: if n == 0: return ae p, x, y = as_[0] actualizado, d = buscaActualiza((x, y), d) if actualizado: return aux(as_[1:], d, [(p, x, y)] + ae, n - 1) return aux(as_[1:], d, ae, n) return aux(list(sorted([(p, x, y) for ((x, y), p) in aristas(g)])), {x: x for x in nodos(g)}, [], len(nodos(g)) - 1) # Traza del diccionario correspondiente al grafo g3 # ================================================= # Lista de aristas, ordenadas según su peso: # [(3,5,6),(5,1,2),(5,4,5),(6,1,6),(7,2,3),(7,3,5),(8,3,4),(9,1,3),(9,5,7),(11,6,7),(15,1,5)] # # Inicial # {1:1, 2:2, 3:3, 4:4, 5:5, 6:6, 7:7} # # Después de añadir la arista (5,6) de peso 3 # {1:1, 2:2, 3:3, 4:4, 5:5, 6:5, 7:7} # # Después de añadir la arista (1,2) de peso 5 # {1:1, 2:1, 3:3, 4:4, 5:5, 6:5, 7:7} # # Después de añadir la arista (4,5) de peso 5 # {1:1, 2:1, 3:3, 4:4, 5:4, 6:4, 7:7} # # Después de añadir la arista (1,6) de peso 6 # {1:1, 2:1, 3:3, 4:1, 5:1, 6:1, 7:7} # # Después de añadir la arista (2,3) de peso 7 # {1:1, 2:1, 3:1, 4:1, 5:1, 6:1, 7:7} # # Las posibles aristas a añadir son: # + la (3,5) con peso 7, que no es posible pues la raíz de 3 # coincide con la raíz de 5, por lo que formaría un ciclo # + la (3,4) con peso 8, que no es posible pues la raíz de 3 # coincide con la raíz de 4, por lo que formaría un ciclo # + la (1,3) con peso 9, que no es posible pues la raíz de 3 # coincide con la raíz de 1, por lo que formaría un ciclo # + la (5,7) con peso 9, que no forma ciclo # # Después de añadir la arista (5,7) con peso 9 # {1:1, 2:1, 3:1, 4:1, 5:1, 6:1, 7:1} # # No es posible añadir más aristas, pues formarían ciclos. # Verificación # ============ def test_kruskal() -> None: assert kruskal(g1) == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)] assert kruskal(g2) == [(32,2,5),(13,1,2),(12,2,4),(11,1,3)] assert kruskal(g3) == [(9,5,7),(7,2,3),(6,1,6),(5,4,5),(5,1,2),(3,5,6)] assert kruskal(g4) == [(9,5,7),(6,1,6),(5,4,5),(5,1,2),(3,5,6),(1,3,5)] print("Vefificado") # La verificación es # >>> test_kruskal() # Vefificado |
5. Algoritmo de Prim
El algoritmo de Prim calcula un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.
El algoritmo de Prim funciona de la siguiente manera:
- Inicializar un árbol con un único vértice, elegido arbitrariamente, del grafo.
- Aumentar el árbol por un lado. Llamamos lado a la unión entre dos vértices: de las posibles uniones que pueden conectar el árbol a los vértices que no están aún en el árbol, encontrar el lado de menor distancia y unirlo al árbol.
- Repetir el paso 2 (hasta que todos los vértices pertenezcan al árbol)
Usando el tipo abstracto de datos de los grafos, definir la función,
1 |
prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)] |
tal que prim g
es el árbol de expansión mínimo del grafo g
calculado mediante el algoritmo de Prim. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
g1, g2, g3, g4 :: Grafo Int Int g1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78), (2,4,12),(2,5,32), (3,4,14),(3,5,44), (4,5,93)] g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,7), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,1), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] |
entonces
1 2 3 |
prim g1 == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)] prim g2 == [(32,2,5),(12,2,4),(13,1,2),(11,1,3)] prim g3 == [(9,5,7),(7,2,3),(5,5,4),(3,6,5),(6,1,6),(5,1,2)] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
module Grafo_Algoritmo_de_Prim where import TAD.Grafo (Grafo, Orientacion (ND), aristas, creaGrafo, nodos) import Data.Ix (Ix) import Data.List (delete) import Test.Hspec (Spec, hspec, it, shouldBe) g1, g2, g3, g4 :: Grafo Int Int g1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78), (2,4,12),(2,5,32), (3,4,14),(3,5,44), (4,5,93)] g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,7), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,1), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)] prim g = prim' [n] -- Nodos colocados ns -- Nodos por colocar [] -- Árbol de expansión (aristas g) -- Aristas del grafo where (n:ns) = nodos g prim' _ _ _ [] = [] prim' _ [] ae _ = ae prim' t r ae as = prim' (v':t) (delete v' r) (e:ae) as where e@(_,_, v') = minimum [(c,u,v)| ((u,v),c) <- as, u `elem` t, v `elem` r] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ prim g1 `shouldBe` [(55,2,4),(34,1,3),(32,2,5),(12,1,2)] it "e2" $ prim g2 `shouldBe` [(32,2,5),(12,2,4),(13,1,2),(11,1,3)] it "e3" $ prim g3 `shouldBe` [(9,5,7),(7,2,3),(5,5,4),(3,6,5),(6,1,6),(5,1,2)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- -- Finished in 0.0026 seconds -- 3 examples, 0 failures |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
from src.TAD.Grafo import (Grafo, Orientacion, Peso, Vertice, aristas, creaGrafo, nodos) g1 = creaGrafo (Orientacion.ND, (1,5), [((1,2),12),((1,3),34),((1,5),78), ((2,4),55),((2,5),32), ((3,4),61),((3,5),44), ((4,5),93)]) g2 = creaGrafo (Orientacion.ND, (1,5), [((1,2),13),((1,3),11),((1,5),78), ((2,4),12),((2,5),32), ((3,4),14),((3,5),44), ((4,5),93)]) g3 = creaGrafo (Orientacion.ND, (1,7), [((1,2),5),((1,3),9),((1,5),15),((1,6),6), ((2,3),7), ((3,4),8),((3,5),7), ((4,5),5), ((5,6),3),((5,7),9), ((6,7),11)]) g4 = creaGrafo (Orientacion.ND, (1,7), [((1,2),5),((1,3),9),((1,5),15),((1,6),6), ((2,3),7), ((3,4),8),((3,5),1), ((4,5),5), ((5,6),3),((5,7),9), ((6,7),11)]) def prim(g: Grafo) -> list[tuple[Peso, Vertice, Vertice]]: n, *ns = nodos(g) def prim_(t: list[Vertice], r: list[Vertice], ae: list[tuple[Peso, Vertice, Vertice]], as_: list[tuple[tuple[Vertice, Vertice], Peso]]) \ -> list[tuple[Peso, Vertice, Vertice]]: if not as_: return [] if not r: return ae e = min(((c,u,v) for ((u,v),c) in as_ if u in t and v in r)) (_,_, v_) = e return prim_([v_] + t, [x for x in r if x != v_], [e] + ae, as_) return prim_([n], ns, [], aristas(g)) # Verificación # ============ def test_prim() -> None: assert prim(g1) == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)] assert prim(g2) == [(32,2,5),(12,2,4),(13,1,2),(11,1,3)] assert prim(g3) == [(9,5,7),(7,2,3),(5,5,4),(3,6,5),(6,1,6),(5,1,2)] print("Verificado") # La verificación es # >>> test_prim() # Verificado |