Exercitium

Algoritmo divide y vencerás

PorJosé A. Alonso 26-junio-202319-junio-2023

La técnica divide y vencerás consta de los siguientes pasos:

Dividir el problema en subproblemas menores.
Resolver por separado cada uno de los subproblemas:
- si los subproblemas son complejos, usar la misma técnica recursivamente;
- si son simples, resolverlos directamente.
Combinar todas las soluciones de los subproblemas en una solución simple.

Definir la función

   divideVenceras :: (p -> Bool)
                  -> (p -> s)
                  -> (p -> [p])
                  -> (p -> [s] -> s)
                  -> p
                  -> s

divideVenceras :: (p -> Bool)

-> (p -> s)

-> (p -> [p])

-> (p -> [s] -> s)

-> p

-> s

tal que divideVenceras ind resuelve divide combina pbInicial resuelve el problema pbInicial mediante la técnica de divide y vencerás, donde

ind pb se verifica si el problema pb es indivisible
resuelve pb es la solución del problema indivisible pb
divide pb es la lista de subproblemas de pb
combina pb ss es la combinación de las soluciones ss de los subproblemas del problema pb.
pbInicial es el problema inicial

Usando la función DivideVenceras, definir las funciones

   ordenaPorMezcla :: Ord a => [a] -> [a]
   ordenaRapida    :: Ord a => [a] -> [a]

1 2	ordenaPorMezcla :: Ord a => [a] -> [a] ordenaRapida :: Ord a => [a] -> [a]

tales que

ordenaPorMezcla xs es la lista obtenida ordenando xs por el procedimiento de ordenación por mezcla. Por ejemplo,

     λ> ordenaPorMezcla [3,1,4,1,5,9,2,8]
     [1,1,2,3,4,5,8,9]

1 2	λ> ordenaPorMezcla [3,1,4,1,5,9,2,8] [1,1,2,3,4,5,8,9]

ordenaRapida xs es la lista obtenida ordenando xs por el procedimiento de ordenación rápida. Por ejemplo,

     λ> ordenaRapida [3,1,4,1,5,9,2,8]
     [1,1,2,3,4,5,8,9]

1 2	λ> ordenaRapida [3,1,4,1,5,9,2,8] [1,1,2,3,4,5,8,9]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

module DivideVenceras (divideVenceras) where

import Test.Hspec (Spec, hspec, it, shouldBe)

divideVenceras :: (p -> Bool)
               -> (p -> s)
               -> (p -> [p])
               -> (p -> [s] -> s)
               -> p
               -> s
divideVenceras ind resuelve divide combina = dv'
  where
    dv' pb
      | ind pb    = resuelve pb
      | otherwise = combina pb [dv' sp | sp <- divide pb]

ordenaPorMezcla :: Ord a => [a] -> [a]
ordenaPorMezcla =
    divideVenceras ind id divide combina
    where
      ind xs            = length xs <= 1
      divide xs         = [take n xs, drop n xs]
                          where n = length xs `div` 2
      combina _ [l1,l2] = mezcla l1 l2

-- (mezcla xs ys) es la lista obtenida mezclando xs e ys. Por ejemplo,
--    mezcla [1,3] [2,4,6]  ==  [1,2,3,4,6]
mezcla :: Ord a => [a] -> [a] -> [a]
mezcla [] b = b
mezcla a [] = a
mezcla a@(x:xs) b@(y:ys) | x <= y    = x : mezcla xs b
                         | otherwise = y : mezcla a ys

ordenaRapida :: Ord a => [a] -> [a]
ordenaRapida =
    divideVenceras ind id divide combina
    where
      ind xs                = length xs <= 1
      divide (x:xs)         = [[ y | y <- xs, y <= x],
                               [ y | y <- xs, y > x]]
      combina (x:_) [l1,l2] = l1 ++ [x] ++ l2

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    ordenaPorMezcla [3,1,4,1,5,9,2,8] `shouldBe` [1,1,2,3,4,5,8,9]
  it "e2" $
    ordenaRapida [3,1,4,1,5,9,2,8] `shouldBe` [1,1,2,3,4,5,8,9]

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--
--    Finished in 0.0004 seconds
--    2 examples, 0 failures

module DivideVenceras (divideVenceras) where

import Test.Hspec (Spec, hspec, it, shouldBe)

divideVenceras :: (p -> Bool)

-> (p -> s)

-> (p -> [p])

-> (p -> [s] -> s)

-> p

-> s

divideVenceras ind resuelve divide combina = dv'

where

dv' pb

| ind pb = resuelve pb

| otherwise = combina pb [dv' sp | sp <- divide pb]

ordenaPorMezcla :: Ord a => [a] -> [a]

ordenaPorMezcla =

divideVenceras ind id divide combina

where

ind xs = length xs <= 1

divide xs = [take n xs, drop n xs]

where n = length xs `div` 2

combina _ [l1,l2] = mezcla l1 l2

-- (mezcla xs ys) es la lista obtenida mezclando xs e ys. Por ejemplo,

-- mezcla [1,3] [2,4,6] == [1,2,3,4,6]

mezcla :: Ord a => [a] -> [a] -> [a]

mezcla [] b = b

mezcla a [] = a

mezcla a@(x:xs) b@(y:ys) | x <= y = x : mezcla xs b

| otherwise = y : mezcla a ys

ordenaRapida :: Ord a => [a] -> [a]

ordenaRapida =

divideVenceras ind id divide combina

where

ind xs = length xs <= 1

divide (x:xs) = [[ y | y <- xs, y <= x],

[ y | y <- xs, y > x]]

combina (x:_) [l1,l2] = l1 ++ [x] ++ l2

-- Verificación

-- ============

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

ordenaPorMezcla [3,1,4,1,5,9,2,8] `shouldBe` [1,1,2,3,4,5,8,9]

it "e2" $

ordenaRapida [3,1,4,1,5,9,2,8] `shouldBe` [1,1,2,3,4,5,8,9]

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- Finished in 0.0004 seconds

-- 2 examples, 0 failures

Soluciones en Python

from typing import Callable, TypeVar

P = TypeVar('P')
S = TypeVar('S')

def divideVenceras(ind: Callable[[P], bool],
                   resuelve: Callable[[P], S],
                   divide: Callable[[P], list[P]],
                   combina: Callable[[P, list[S]], S],
                   p: P) -> S:
    def dv(pb: P) -> S:
        if ind(pb):
            return resuelve(pb)
        return combina(pb, [dv(sp) for sp in divide(pb)])
    return dv(p)

def ordenaPorMezcla(xs: list[int]) -> list[int]:
    def ind(xs: list[int]) -> bool:
        return len(xs) <= 1

    def divide(xs: list[int]) -> list[list[int]]:
        n = len(xs) // 2
        return [xs[:n], xs[n:]]

    def combina(_: list[int], xs: list[list[int]]) -> list[int]:
        return mezcla(xs[0], xs[1])

    return divideVenceras(ind, lambda x: x, divide, combina, xs)

# (mezcla xs ys) es la lista obtenida mezclando xs e ys. Por ejemplo,
#    mezcla([1,3], [2,4,6]) == [1,2,3,4,6]
def mezcla(a: list[int], b: list[int]) -> list[int]:
    if not a:
        return b
    if not b:
        return a
    if a[0] <= b[0]:
        return [a[0]] + mezcla(a[1:], b)
    return [b[0]] + mezcla(a, b[1:])

def ordenaRapida(xs: list[int]) -> list[int]:
    def ind(xs: list[int]) -> bool:
        return len(xs) <= 1

    def divide(xs: list[int]) -> list[list[int]]:
        x, *xs = xs
        return [[y for y in xs if y <= x],
                [y for y in xs if y > x]]

    def combina(xs: list[int], ys: list[list[int]]) -> list[int]:
        x = xs[0]
        return ys[0] + [x] + ys[1]

    return divideVenceras(ind, lambda x: x, divide, combina, xs)

# Verificación
# ============

def test_divideVenceras() -> None:
    assert ordenaPorMezcla([3,1,4,1,5,9,2,8]) == [1,1,2,3,4,5,8,9]
    assert ordenaRapida([3,1,4,1,5,9,2,8]) == [1,1,2,3,4,5,8,9]
    print("Verificado")

# La verificación es
#    >>> test_divideVenceras()
#    Verificado

from typing import Callable, TypeVar

P = TypeVar('P')

S = TypeVar('S')

def divideVenceras(ind: Callable[[P], bool],

resuelve: Callable[[P], S],

divide: Callable[[P], list[P]],

combina: Callable[[P, list[S]], S],

p: P) -> S:

def dv(pb: P) -> S:

if ind(pb):

return resuelve(pb)

return combina(pb, [dv(sp) for sp in divide(pb)])

return dv(p)

def ordenaPorMezcla(xs: list[int]) -> list[int]:

def ind(xs: list[int]) -> bool:

return len(xs) <= 1

def divide(xs: list[int]) -> list[list[int]]:

n = len(xs) // 2

return [xs[:n], xs[n:]]

def combina(_: list[int], xs: list[list[int]]) -> list[int]:

return mezcla(xs[0], xs[1])

return divideVenceras(ind, lambda x: x, divide, combina, xs)

# (mezcla xs ys) es la lista obtenida mezclando xs e ys. Por ejemplo,

# mezcla([1,3], [2,4,6]) == [1,2,3,4,6]

def mezcla(a: list[int], b: list[int]) -> list[int]:

if not a:

return b

if not b:

return a

if a[0] <= b[0]:

return [a[0]] + mezcla(a[1:], b)

return [b[0]] + mezcla(a, b[1:])

def ordenaRapida(xs: list[int]) -> list[int]:

def ind(xs: list[int]) -> bool:

return len(xs) <= 1

def divide(xs: list[int]) -> list[list[int]]:

x, *xs = xs

return [[y for y in xs if y <= x],

[y for y in xs if y > x]]

def combina(xs: list[int], ys: list[list[int]]) -> list[int]:

x = xs[0]

return ys[0] + [x] + ys[1]

return divideVenceras(ind, lambda x: x, divide, combina, xs)

# Verificación

# ============

def test_divideVenceras() -> None:

assert ordenaPorMezcla([3,1,4,1,5,9,2,8]) == [1,1,2,3,4,5,8,9]

assert ordenaRapida([3,1,4,1,5,9,2,8]) == [1,1,2,3,4,5,8,9]

print("Verificado")

# La verificación es

# >>> test_divideVenceras()

# Verificado

TAD de los grafos: Algoritmo de Prim

PorJosé A. Alonso 23-junio-202316-junio-2023

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,

   prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]

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

   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)]

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

   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)]

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.

Soluciones en Haskell

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

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

Soluciones en Python

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

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

TAD de los grafos: Algoritmo de Kruskal

PorJosé A. Alonso 22-junio-202316-junio-2023

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,

   kruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]

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

   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)]

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

   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)]

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.

Soluciones en Haskell

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

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

Soluciones en Python

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

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

TAD de los grafos: Nodos conectados en un grafo

PorJosé A. Alonso 21-junio-202314-junio-2023

Usando el tipo abstracto de datos de los grafos, definir la función,

   conectados :: Grafo Int Int -> Int -> Int -> Bool

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

   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)]

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,

   conectados grafo1 1 3  ==  True
   conectados grafo1 1 4  ==  False
   conectados grafo1 6 2  ==  False
   conectados grafo1 3 1  ==  True

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.

Soluciones en Haskell

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

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

Soluciones en Python

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

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

TAD de los grafos: Nodos aislados de un grafo

PorJosé A. Alonso 20-junio-202312-junio-2023

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

   grafo1 :: Grafo Int Int
   grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6),
                                (5,4),(6,2),(6,5)]

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,

   aislados :: (Ix v, Num p) => Grafo v p -> [v]

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,

   aislados grafo1 == [1,2,4]

1	aislados grafo1 == [1,2,4]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

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

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

Soluciones en Python

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

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

Algoritmo divide y vencerás

TAD de los grafos: Algoritmo de Prim

TAD de los grafos: Algoritmo de Kruskal

TAD de los grafos: Nodos conectados en un grafo

TAD de los grafos: Nodos aislados de un grafo

Entradas recientes

Buscar

Correo electrónico