Video: Matthias Kriesell professor - modtager af Eliteforskprisen 2012 2024
Grafer er en form for vanlig datastruktur som brukes i algoritmer. Du ser grafer som brukes på steder som kart for GPS og alle andre steder hvor toppnettet tilnærming til en trestruktur ikke virker.
En graf er en slags treforlengelse. Som med trær, har du noder som kobler til hverandre for å skape relasjoner. I motsetning til binære trær kan en graf imidlertid ha mer enn en eller to tilkoblinger. Faktisk har grafnoder ofte en rekke tilkoblinger. For å holde det enkelt, bør du vurdere grafen som vises.
I dette tilfellet oppretter grafen en ring hvor A kobles til både B og F. Det behøver imidlertid ikke å være slik. A kan være en frakoblet node eller kunne også koble til C. En graf viser tilkobling mellom noder på en måte som er nyttig for å definere komplekse forhold.
Grafer legger også til noen få nye vendinger som du kanskje ikke har tenkt på før. For eksempel kan en graf inkludere begrepet directionality. I motsetning til et tre, som har foreldre / barns forhold, kan en grafnode koble til en hvilken som helst annen nod med en bestemt retning i tankene. Tenk på gatene i en by. De fleste gatene er toveis, men noen er enveisgater som tillater bevegelse i bare én retning.
Presentasjonen av en grafforbindelse kan ikke gjenspeile realiteten i grafen. En graf kan angi en vekt til en bestemt tilkobling. Vekten kan definere avstanden mellom to punkter, definere tiden som kreves for å krysse ruten, eller gi annen form for informasjon.
