INF1020 ukeoppgaver uke 9 (24/10-28/10)
=======================================


OPPGAVE 1
---------

a) Tegn den rettede grafen som tilsvarer denne nabomatrisen:
       0    1    2    3
   0   T    F    T    F
   1   T    F    F    F
   2   F    F    F    T
   3   T    F    T    F

b) Tegn nabo-liste representasjonen av denne grafen.



OPPGAVE 2
---------

Vi skal se p? noen typer rettede grafer, der alle typene er slik at
alle noder har maksimalt en etterf?lger, men gjerne flere forgjengere.
Blant disse grafene finnes blant annet vanlige line?re lister, enkle
sykliske strukturer (l?kker), samt rotrettede tr?r. Det finnes
imidlertid ogs? mange andre grafer innenfor denne rammen. Tegn
forskjellige forslag.

Vi skal anta at vi har en slik graf representert ved noder av typen:
   class Node {
      Node etterf;   // Er null om det ikke finnes etterf?lger
      int merke;
      // Eventuelle data..
   }

Det er n noder, og for ? f? tilgang til nodene har vi en array
   Node[] graf = new Node[n];
som peker ut alle nodene i TILFELDIG rekkef?lge.

Vi skal lage tre boolske metoder:
a) En som unders?ker om grafen er en enkel line?r liste, som ender med 
   null.
b) En som unders?ker om grafen best?r av en enkel rettet l?kke.
c) En som unders?ker om grafen er ETT rotrettet tre.

Det er alts? en int variabel "merke" i hver node, og denne vil v?re
null n?r metodene starter, og metodene kan bruke den som de vil.
Fors?k ? klare deg med ? bruke s? f? forskjellige verdier som mulig
for denne variabelen, eller helst ? IKKE BRUKE DEN I DET HELE TATT.



OPPGAVE 3 - LABYRINT
--------------------

Anta at en person st?r ved inngangen til en labyrint. Et eller annet
sted inne i labyrinten finnes det en skatt.

a) Hvordan vil du representere en slik labyrint som en graf?

b) Skriv et program som s?ker gjennom labyrinten (grafen) og dirigerer
   en skattejeger frem til rommet med skatten og ut igjen.
   (S?kingen gjennom labyrinten burde v?re en relativt grei oppgave,
   mens utskriften/dirigeringen fort kan bli litt fiklete.)

c) Gir instruksjonene som blir skrevet ut fra punkt b den raskeste
   veien til skatten? Hvis ikke, lag et nytt program som gj?r dette.

Lag sm? labyrint-eksempler slik at du f?r sjekket at programmet ditt
virker!