Grafer
En graf er helt basalt en matematisk struktur, der repræsenterer forhold mellem enheder i den virkelige verden. Dens formål er ofte at beskrive forbindelser mellem to enheder, og særligt inden for datalogi er det kendt at beskrive forbindelser mellem noder, klasser eller netværk. Det kan dog bruges til at løse et næsten uendeligt antal af problemstillinger.
En graf består af to grundlæggende enheder:
Punkter
Kanter
Punkterne er selve dataen, og kanterne benyttes til at forbinde disse data. Disse kanter kan have en værdi, som vi kalder for vægte. Er der vægtede kanter på en graf, vil det typisk afspejle tiden eller de ressourcer, der kræves for at komme fra punkt 1 til punkt 2.
En graf kan forekomme i mange typer, og der er en hel del begreber, som knytter sig til emnet graf. Dette vil blive gennemgået i de følgende afsnit.
Begreber til grafer:
Rettede eller urettede grafer
I en rettet graf har hver kant en retning, det vil sige, at vi kun kan gå én vej. I den urettede graf kan vi bevæge os begge veje på kanten. Nedenstående billede illustrerer dette:
Naboknuder
To knuder er naboer, hvis de er forbundet af en kant.
Incidente kanter
Kanter, som har samme knude som et af endepunkterne.
Parallelle kanter
To kanter, som har samme endepunkt.
Simpel graf og Delgraf
En simpel graf er en graf uden løkker og parallelle kanter. En delgraf er en subdel af en hel graf. Den fremviser altså nogle af den oprindelige grafs knuder og kanter. Dette bruges især i sammenhæng med at finde det letteste udspændende træ i en graf.
Grafgennemløb
Der findes et utal af forskellige tilgange til at gennemløbe en graf. Jeg vil dog tage udgangspunkt i de to primære, vi har beskæftiget os med i undervisningen, og som vi skal skulle implementere.
Depth-first-search
Depth-first-search (DFS) er en algoritme til at traversere træ- eller grafstrukturer. Den benytter en udforskende metode, hvor man bevæger sig gennem grafen ved at følge kanterne fra knude til knude så langt som muligt, uden at besøge knuder, der allerede er blevet besøgt. Den starter fra en specifik node, og derfra gennemløber den så langt den kan i grafen, for herefter at "gå-baglæns", oftest ved at den er implementeret ved hjælp af rekursion.
Der er to vigtige lister, der sørger for, at dette kan lade sig gøre:
En liste af besøgte noder/knuder
Callstacken
Listen af besøgte noder/knuder sikrer, at vi ikke besøger det samme punkt to gange, og callstacken sørger for, at når vi når til bunden af første gennemløb (dette sker, når alle en knudes naboer allerede har været besøgt), så kan vi gå opad i rekursionstræet og kigge videre.
