Tietorakenteet, syksy 2004
Kurssikoe 2
Tehtävä 4

Annettu siis suunnattu verkko G=(V,E) ja kaksi verkon solmua, s1 ja
s2. Kysytään, onko verkossa polku solmusta s1 solmuun s2.

Käytetään leveys- tai syvyyssuuntaista etsintää. Olkoon jokaisessa
solmussa v attribuutti p[v]. Nillä solmuilla, joita ei etsinnän aikana
ole vielä nähty, p[v] = NIL. Etsinnän aikana jokaiselle käsitellylle
solmulle v asetetaan attribuutin p[v] arvoksi se solmu, jonka kautta v
saavutettiin. Etsintä aloitetaan solmusta s1, jolla erikoistapauksena
p[s1] = s1.

Jos solmu s2 saavutetaan, polku solmusta s1 solmuun s2 saadaan
kääntämällä solmusta s2 alkava p-linkkien muodostama solmujen lista
takaperin pinon avulla.

Leveyssuuntainen etsintä:

etsi-leveyssuuntaan(G=(V,E), s1, s2)
  for each v in V do p[v] := NIL
  Q := uusi jono
  p[s1] := s1
  enqueue(Q,s1)
  while not empty(Q)
     do x := dequeue(Q)
        if x != s2
           then for each y : (x,y) in E and p[y] = NIL do
                    p[y] := x
                    enqueue(Q,y)
           else S := uusi pino
                repeat
                  push(S,x)
                  x := p[x]
                until x = top(S)
                while not empty(S)
                   do print(pop(S))
                return

Syvyyssuuntainen etsintä:

etsi-syvyyssuuntaan(G=(V,E), s1, s2)
  for each v in V do p[v] := NIL
  p[s1] := s1
  x := syvyyssuuntaan-vierailu(G, s1, s2)
  if x != NIL
     then S := uusi pino
          repeat
            push(S,x)
            x := p[x]
          until x = top(S)
          while not empty(S)
             do print(pop(S))

syvyyssuuntaan-vierailu(G=(V,E), x, s)
  if x = s
     then return x
     else for each y : (x,y) in E and p[y] = NIL do
              p[y] := x
              z := syvyyssuuntaan-vierailu(G,y,s)
              if z != NIL then return z
          return NIL

Aikavaativuus: Molemmissa algoritmeissa p-attribuutin alustukseen
kuluu aikaa O(|V|) askelta. Polun tulostukseen kuluu myös O(|V|)
askelta, sillä polulla voi olla korkeintaan |V| solmua. Varsinaisen
etsinnän aikana jokainen verkon kaari käsitellään korkeintaan kerran,
yhteensä siis O(|E|) askelta.  Kokonaisuudessaan kummankin algoritmin
aikavaativuus on siis O(|V| + |E|).

Tilavaativuus: Leveyssuuntaisessa algoritmissa jonossa voi olla
kerralla O(|V|) solmua. Syvyyssuuntaisessa algoritmissa rekursiopinon
koko on O(|V|). Kummassakin algoritmissa tulostukseen käytetyssä
pinossa on O(|V|) alkiota. Yhteensä tilavaativuus on siis molemmilla
algoritmeilla O(|V|).

Pisteytys: algoritmi max 3 pistettä, aika- ja tilavaativuus max 2 pistettä.