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
---
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
|