Algoritmer og datastrukturer

Øvingsoppgaver: Grafer

Oppgave 1

1. Hvor mye RAM kreves for å representere/lagre en uvektet graf med N noder og K kanter som en nabomatrise?

2. Hvor mye RAM krever representasjonen med nabolister?

Oppgave 2

De 8 nodene i grafen er S, A-F og T. Lengden/vekten på hver kant er et heltall angitt i sirkelen midt på kanten. Nodene er nummerert slik:

  S:0  A:1  B:2  C:3  D:4  E:5  F:6  T:7

Grafen skal traverseres med start i noden S.

1. I hvilken rekkefølge oppsøkes nodene i en dybde-først traversering?

2. I hvilken rekkefølge oppsøkes nodene i en bredde-først traversering?

Oppgave 3

Oppgave 4

Den iterative versjonen av DFS kan lages ganske enkelt ved å bytte ut køen som brukes i BFS med en stack, og bare gjøre et par andre små endringer.

Oppgave 5

Dijkstra's algoritme skal brukes for å finne korteste vei fra noden S til alle de 7 andre nodene.

Vi vet at Dijkstra finner korteste vei til én ny node i hver iterasjon. Sett opp en oversiktlig tabell som viser forløpet av Dijkstra's algoritme på denne grafen. Hver rad i tabellen skal vise tilstanden etter en iterasjon og skal angi:

• Hvilke noder som vi nå kjenner garantert korteste vei til, og hvor lang denne veien er.
• Hvilke andre noder som er oppsøkt og som vi kjenner en mulig korteste vei til, og hvor lang denne veien er.
• Hvilke noder som ennå ikke er oppsøkt.

Oppgave 6

Oppgave 7

Det skal brukes en heap som lagrer klasseobjekter som inneholder både nodenummeret og avstanden til noden, for alle noder som vi ikke har funnet korteste avstand til ennå. Programmer denne heapen først, med utgangspunkt i koden for en heap med enkle heltall. Det må her legges til en ny metode i tillegg til metodene for innsetting og fjerning av minste verdi, som kan brukes til å endre verdien for en node som allerede ligger i heapen. For at denne metoden skal bli O(log (n)), må det brukes en ekstra array, som til enhver tid inneholder indeksen i heapen der hver node i grafen er lagret.

Skriv deretter en ny versjon av Dijkstra som i hvert steg bruker denne heapen til å finne noden med kortest avstand til startnoden.

Oppgave 8

I en vektet, rettet graf er nodene representert slik:

  class node
  {
    int ant_naboer;  // Antall naboer
    int nabo[];      // Nodenummere for alle direkte naboer
    int lengde[];    // Kantlengder
  };

Det finnes maksimalt N noder i grafen (N er en globalt definert konstant), nummerert fra 0 til N-1. Hele grafen er lagret i en array graf med nodeobjekter:

  node graf[];

1. Tegn en figur som viser hvorledes datastrukturen beskrevet ovenfor ser ut for følgende graf:

   

2. Skriv en iterativ metode:

     void skriv_naboer(node graf[], int n)
   

   Metoden skal, for hver av de n nodene i grafen, skrive ut nodens nummer, etterfulgt av en liste med nodenummer og avstand til alle direkte naboer som denne noden har i grafen.

3. En mulig vei i grafen kan representeres som en array med nodenummere. For grafen som er tegnet ovenfor, vil f.eks. arrayen {2,3,0,1} representere en vei fra node 2 til node 1, mens veien {2,4,1,0} ikke er en lovlig/mulig vei, fordi kanten (2,4) ikke finnes i grafen.

   Lag en metode:

     boolean lovlig_vei(node graf[], int n, int vei[], int len);
   

   som returnerer true bare hvis veien med lengde len som er lagret i arrayen vei, finnes i grafen graf, som har n noder. Ellers skal metoden returnere false. Du kan velge om du vil lage en rekursiv eller en iterativ løsning.

4. I denne oppgaven skal du lage en metode som legger data om kantene i en graf inn i et binært søketre. Grafen er representert som beskrevet ovenfor. Det binære søketreet skal inneholde en node for hver kant i grafen, med informasjon om kantlengde og om hvilke to noder kanten går fra og til. Nodene i søketreet er definert slik:

     class tre_node
     {
       int lengde;    // Kantlengde
       int til, fra;  // Nodenummere i grafen for de to nodene som
                      // er knyttet til hverandre med denne kanten
       tre_node v,h;  // Pekere til venstre og høyre barn i treet
     };
   

   Søketreet skal være sortert på kantlengdene, slik at kantlengder som er mindre legges til venstre for en node, og kantlengder som er større eller lik lengden i en node legges til høyre for noden i treet.

   Skriv en metode

     tre_node kant_tre(node graf[], int n)
   

   som bygger opp et søketre med kant-informasjon som beskrevet ovenfor, og returnerer en peker til roten i dette treet. Parameter til metoden er arrayen graf, som inneholder de n nodene i grafen.