Haskell - Camí en un graf? Z99626

Statement

thehtml

Els grafs dirigits amb llistes d’adjacència venen donats pel tipus:

data Node a = Node a [a] data Graf a = Graf [Node a]

on Node correspon a un vèrtex i la seva llista d’adjacència i Graf a un graf com una llista de nodes.

Feu que un graf sigui instància de la classe Show i mostri els grafs com a l’exemple:
ghci> Graf [Node "bcn" ["prs"], Node "prs" ["bcn", "tls"], Node "tls" []] "bcn" : "prs" "prs" : "bcn", "tls" "tls"
Escriviu una funció cami :: Eq a => Graf a -> (a, a) -> Bool que, donat un graf i una tupla (origen, destí) ens digui si existeix un camí entre el vèrtex origen i el vèrtex destí:
ghci> g = Graf [Node "bcn" ["prs"], Node "prs" ["bcn", "tls"], Node "tls" []] ghci> cami g ("bcn", "tls") True ghci> cami g ("tls", "bcn") False
Escriviu un programa que obtingui un origen i un destí com a primera línea i un graf de la resta (on cada línea correspon a un node: vèrtex més llista d’adjacència sense repetits) i escrigui si hi ha un camí al graf donat entre el vèrtex origen i el destí.

Public test cases

Input

bcn mad
bcn prs ber
prs mad
mad lon
rom lsb dub 
lsb dub
ber lon bcn
lon 
dub lsb

Output

True

Input

rom bcn
bcn prs ber
prs mad
mad lon
rom lsb dub 
lsb dub
ber lon bcn
lon 
dub lsb

Output

False

Information