Video: Matthias Kriesell professor - modtager af Eliteforskprisen 2012 2024
Grafer er en form for fælles datastruktur, der anvendes i algoritmer. Du kan se grafer, der bruges på steder som kort til GPS og alle andre steder, hvor den øverste nedadgående tilgang til en træstruktur ikke virker.
En graf er en slags træforlængelse. Som med træer har du noder, der forbinder hinanden for at skabe relationer. I modsætning til binære træer kan en graf imidlertid have mere end en eller to forbindelser. Faktisk har grafnoder ofte en lang række forbindelser. For at holde tingene simple skal du overveje den viste graf.
I dette tilfælde opretter grafen en ring, hvor A forbinder til både B og F. Det behøver dog ikke at være sådan. A kunne være en afbrudt knude eller kunne også forbinde til C. En graf viser forbindelsen mellem knuder på en måde, som er nyttig til at definere komplekse relationer.
Grafer tilføjer også et par nye vendinger, som du måske ikke har tænkt på før. For eksempel kan en graf inkludere begrebet directionality. I modsætning til et træ, der har forældre / barns forhold, kan en grafnode forbinde til enhver anden knude med en bestemt retning i tankerne. Tænk på gader i en by. De fleste gader er tovejs, men nogle er envejs gader, der tillader bevægelse i kun én retning.
Præsentationen af en grafforbindelse kan ikke afspejle realiteten af grafen. En graf kan angive en vægt til en bestemt forbindelse. Vægten kunne definere afstanden mellem to punkter, definere den tid, der kræves for at krydse ruten eller give anden form for information.
