Hjemmeside
Nyheter
Forelesningsplan
Oppgaver
Pensumliste
Eksempler
Wiki
Emnebeskrivelse

Algoritmer og datastrukturer

Løsningsforslag til øvingsoppgaver: Grafer

[Oppgavesett]

Oppgave 1

Fordi grafen er uvektet, trenger vi for hver node bare å lagre "dataene" (som er et heltall) og nummeret på alle naboene (som vi også kan anta er hele tall). Da blir plassforbruket for å lagre grafen:
Med nabomatrise:

Her brukes en N X N matrise, der vi i rad nummer i lagrer nummeret til naboene til node nummer i. Tar vi med at vi også må lagre dataene for hver node i en array av lengde N, blir det totale plassforbruket:
32 · (N2 + N) bits

Med nabolister:

Vi trenger også her en array av lengde N for å lagre dataene i hver node. Alle nabolistene kan lagres i en array av lengde N med referanser til første element i nabolisten for hver node. Hvert element i en naboliste vil måtte lagre en referanse (til neste element i listen) og et heltall (nummeret på grafnoden). Siden det vil være en liste-node for hver kant i grafen, får vi her et totalt plassforbruk på:
32 · (2N + 2K) bits
Hvis vi skal regne enda nøyere, kan vi i tillegg ta med at det i Java er en ekstra kostnad på ca. 16 bit per listenode for klasseinformasjon.

Oppgave 2

a. S A D T E F B C

b. S A B C D E F T

Oppgave 3

Dette vil bli noe tilsvarende preorder traversering av binære søketrær, men her går vi gjennom høyre subtre før venstre. Et eksempel på rekkefølgen nodene vil oppsøkes i er gitt nedenfor: 
         1
        / \
       5   2
      / \   \
     /   \   \
    /     \   \
   11      6   3
  / \     / \   \
13   12  8   7   4
        / \
      10   9

Oppgave 4

Se Java-koden (metoden iDFS)

Oppgave 5

                               Korteste vei
Steg  S  A  B  C  D  E  F  T   funnet til
---- -- -- -- -- -- -- -- --   ----------------
  1   0  4  6  7  X  X  X  X   S
  2   0  4  6  7 11  9  X  X   S A
  3   0  4  6  7 11  9 13  X   S A B
  4   0  4  6  7 11  9 12  X   S A B C
  5   0  4  6  7 11  9 11 18   S A B C E
  6   0  4  6  7 11  9 11 18   S A B C E D
  7   0  4  6  7 11  9 11 17   S A B C E D F
  8   0  4  6  7 11  9 11 17   S A B C E D F T

Oppgave 6

Se Java-koden

Oppgave 7

Javakode:

Oppgave 8

  1. 
         ---
graf[5] |   |
         ---
          |
          |
          V       
   ----------------
  | ant_naboer: 2  |
  |                |    --- ---
  | nabo ------------->| 1 | 3 |
0 |                |    --- ---
  |                |    --- ---
  | lengde ----------->| 4 | 5 | 
  |                |    --- ---
   ----------------
  | ant_naboer: 3  |
  |                |    --- --- ---
  | nabo ------------->| 0 | 2 | 4 |
1 |                |    --- --- ---
  |                |    --- --- ---
  | lengde ----------->| 3 | 5 | 7 |
  |                |    --- --- ---
   ----------------
  | ant_naboer: 1  |
  |                |    --- 
  | nabo ------------->| 3 |
2 |                |    --- 
  |                |    --- 
  | lengde ----------->| 6 | 
  |                |    --- 
   ----------------
  | ant_naboer: 2  |
  |                |    --- ---
  | nabo ------------->| 0 | 4 |
3 |                |    --- ---
  |                |    --- ---
  | lengde ----------->| 5 | 6 | 
  |                |    --- ---
   ----------------
  | ant_naboer: 1  |
  |                |    --- 
  | nabo ------------->| 1 |
4 |                |    --- 
  |                |    --- 
  | lengde ----------->| 8 | 
  |                |    --- 
   ----------------
 

    b., c. og d.  Se Java-koden

 

Jan Høiberg