Oversikt
Graf Definisjoner og Representasjon
Korrigering fra videoen:
- å legge til en node i en nabomatrise tar O(|V|^2) tid, ikke O(|V|) som skrevet i slides.
- I gjennomgangen av representasjoner, var det meningen å påpeke at en naiv objektorientert tolkning av definisjonen av grafer (som mengder av noder og mengder av kanter) er lite effektiv. Det er ikke objektorienteringen i seg selv som er problemet her, heller den direkte oversettelsen som fører til ineffektivitet. Objektorientering står ikke i strid med de andre representasjonsformene. Det kan godt lønne seg å samle informasjon om noder/kanter i objekter, men da kan det f.eks. være lurt å ha med nabo-lister som objektattributer.
Graftraversering
Nyttig øvelse: implementer DFS og BFS ved bruk av stacker og køer!
Korrigering: I stack eksempelet av traversering burde G også bli lagt til som "Besøkt"