IN2010 Gruppe 4
Uke 5
Grafer
Representasjon
En graf er i bunn og grunn en mengde med noder og kanter
G = {N, E}
Denne kan vi representere på flere måter.
Nabomatriser og nabolister
Representasjon
Representasjon
Sammenheng
Om en graf er sammenhengende, kan man nå enhver node fra enhver annen node, ved å traversere over kanter og noder.
Sykler
For urettede grafer:
en sti med 3 eller flere noder, som forbinder første og siste node
For rettede grafer:
en sti med 2 eller flere noder, som forbinder første og siste node
DFS - Dybde først søk
Går så langt vekk man kan, til man ikke kan mer,
BFS
Sjekker alle de nærmeste nodene, før man går videre
Graden til en node
For en urettet graf: Hvor mange kanter som kobler noden med en annen node
For en rettet graf: skiller mellom inngrad og utgrad
Inngrad: Hvor mange kanter som ‘peker på’ noden
Utgrad: Hvor mange kanter noden bruker til å ‘peke på’ en annen node
Topsort - Topologisk Sortering
Fungerer kun på DAGs, og fungerer på alle DAGs (Directed Acyclic Graph)
Finn en node med inngrad 0, legg denne noden til i en output-liste, og fjerner den og alle kanter som peker ut fra den, fra grafen.