Typer grafer i datastruktur med eksempler
Sarah Chen
⚡ Smart oppsummering
Grafer i datastruktur er ikke-lineære samlinger av hjørner og kanter klassifisert i familier som rettede, urettede, vektede, sykliske, asykliske, komplette, sammenhengende, todelte, Euler- og Hamilton-grafer basert på struktur.
En graf er en ikke-lineær datastruktur som består av hjørner og kanter. Hjørnpunktene inneholder informasjonen eller dataene, og kantene fungerer som en kobling mellom et par hjørner.
Grafer kan være av flere typer, avhengig av plasseringen av nodene og kantene. Her er noen viktige typer grafer:
Regissert graf
Kantene på den rettede grafen inneholder piler som angir retningen. Pilen bestemmer hvor kanten peker mot eller slutter. Her er et eksempel på den rettede grafen.
Regissert graf
- Vi kan gå fra node A til D.
- Vi kan imidlertid ikke gå fra node D til node A, ettersom kanten peker fra A til D.
- Siden grafen ikke har vekter, vil det å reise fra toppunkt A til D koste det samme som å reise fra D til F.
Udirigert graf
En urettet graf inneholder kanter uten pekere. Det betyr at vi kan bevege oss omvendt mellom to hjørner. Her er et enkelt eksempel på en urettet graf.
Udirigert graf
I grafen ovenfor,
- Vi kan bevege oss fra A til B.
- Vi kan også bevege oss fra B til A.
- Kanter inneholder ingen retninger.
Det er et eksempel på en urettet graf med et endelig antall hjørner og kanter uten vekter.
Vektet graf
En graf som inneholder vekter eller kostnader på kantene kalles en vektet graf. Den numeriske verdien representerer vanligvis den bevegelige kostnaden fra ett hjørne til et annet. Både rettede og ikke-rettede grafer kan ha vekter på kantene sine. Her er et eksempel på en vektet graf (rettet).
Regissert graf med vekt
- Fra A til B er det en kant, og vekten er 5, som betyr at å flytte fra A til B vil koste oss 5.
- A peker mot B, men i denne grafen har B ingen direkte kant over A. Så vi kan ikke reise fra B til A.
- Men hvis vi ønsker å gå fra A til F, finnes det flere veier. Veiene er ADF og ABF. ADF vil koste (10+11) eller 21.
- Her vil banen ABF koste (5+15) eller 20. Her legger vi sammen vekten av hver kant i banen.
Her er et eksempel på en urettet graf med vekter:
Urettet graf med vekt
Her har kanten vekt, men ingen retning. Så det betyr at å reise fra toppunkt A til D vil koste 10 og omvendt.
Toveis graf
Toveis grafer og ikke-veis grafer har en felles egenskap. Det er:
- Vanligvis kan en urettet graf ha én kant mellom to hjørner.
For eksempel:
- Her vil det å flytte fra A til D eller D til A koste 10.
- I en toveis graf kan vi ha to kanter mellom to hjørner.
Her er et eksempel:
Toveis graf
Å reise fra A til D vil koste oss 17, men å reise fra D til A vil koste oss 12. Så vi kan ikke tildele to forskjellige vekter hvis det er en urettet graf.
Uendelig graf
Grafen vil inneholde et uendelig antall kanter og noder. Hvis en graf er uendelig og også er en sammenhengende graf, vil den også inneholde et uendelig antall kanter. Her betyr de utvidede kantene at flere kanter kan være koblet til disse nodene via kanter. Her er et eksempel på den uendelige grafen:
Uendelig graf
Null graf
En nullgraf inneholder bare noder eller hjørner, men uten kanter. Hvis gitt en graf G = (V, E), hvor V er hjørner og E er kanter, vil den være null hvis antallet kanter E er null. Her er et eksempel på en nullgraf:
Null graf
Triviell graf
En grafdatastruktur regnes som triviell hvis bare ett hjørne eller én node er tilstede uten kanter. Her er et eksempel på en triviell graf:
Multi Graph
En graf kalles en multigraf når det er flere kanter mellom to hjørner, eller når hjørnet har en løkke. Begrepet «løkke» i grafdatastruktur betyr en kant som peker mot samme node eller hjørne. En multigraf kan være rettet eller ikke-rettet. Her er et eksempel på en multigraf:
Det er to kanter fra B til A. Dessuten har hjørne E en selvløkke. Grafen ovenfor er en rettet graf uten vekter på kantene.
Komplett graf
En graf er komplett hvis hvert hjørne har rettede eller ikke-rettede kanter med alle andre hjørner. Anta at det er totalt V antall hjørner, og hvert hjørne har nøyaktig V-1 kanter. Da vil denne grafen bli kalt en komplett graf. I denne typen graf er hvert hjørne forbundet med alle andre hjørner via kanter. Her er et eksempel på en komplett graf med fem hjørner:
Du kan se på bildet at det totale antallet noder er fem, og alle nodene har nøyaktig fire kanter.
Tilkoblet graf
En graf kalles en sammenhengende graf hvis vi starter fra en node eller et hjørne og kan bevege oss til alle nodene fra startnoden. For dette bør det være minst én kant mellom hvert par av noder eller hjørner. Her er et eksempel på en sammenhengende graf:
Her er en forklaring på den tilkoblede grafen ovenfor:
- Forutsatt at det ikke er noen kant mellom C og F, kan vi ikke reise fra A til G. Kanten C til F lar oss imidlertid reise til en hvilken som helst node fra en gitt node.
- En komplett graf er en koblet graf fordi vi kan flytte fra en node til en hvilken som helst annen node i den gitte grafen.
Syklisk graf
En graf sies å være syklisk hvis det er én eller flere sykluser tilstede i grafen. Her er et eksempel på en syklisk graf:
Her danner hjørnene A, B og C en syklus. En graf kan ha flere sykluser inni seg.
Regissert syklisk graf (DAG)
En graf kalles en rettet asyklisk graf eller DAG hvis det ikke er noen sykluser inni grafen. DAG er viktig når man gjør Topologisk sortering eller finne utførelsesrekkefølgen. DAG er også viktig for å lage planleggingssystemer eller skanne avhengigheter av ressurser, osv. Grafen ovenfor inneholder imidlertid ingen syklus inni. Her er et enkelt eksempel på en rettet asyklisk graf (DAG):
Syklusgraf
En syklusgraf er ikke det samme som en syklisk graf. I en syklusgraf vil hver node ha nøyaktig to kanter forbundet, noe som betyr at hver node vil ha nøyaktig to grader. Her er et eksempel på en syklusgraf:
Todelt graf
Slike grafer er spesielle typer grafer der noder er tilordnet to sett. En todelt graf må følge regelen:
- De to settene med hjørner skal være forskjellige, noe som betyr at alle hjørnene må deles inn i to grupper eller sett.
- Samme mengde hjørner skal ikke danne noen kanter.
Euler graf
En grafdatastruktur regnes som en Euler-graf hvis alle hjørnene har en partallsgrad. Begrepet graden av hjørner betyr antall kanter som peker mot eller ut fra et bestemt hjørne. Her er et eksempel på en Euler-graf:
Alle hjørnene har partallsgrader. Hjørnetoppene A, D, E og H har to grader. Her har node C fire grader, som er partallsgrader.
Hamilton-graf
En Hamilton-graf er en sammenhengende graf, hvor du kan besøke alle hjørnene fra et gitt hjørne uten å besøke den samme noden eller bruke den samme kanten. Denne typen sammenhengende graf er kjent som «Hamilton-grafen». Banen du besøker for å bekrefte om den gitte grafen er en Hamilton-graf eller ikke er kjent som Hamilton-banen. Her er et enkelt grafeksempel på en Hamilton:
I dette bildet kan vi besøke alle toppunktene fra hvilken som helst node i grafen ovenfor. En av stiene kan være ADCHBEDet er også mulig å finne en Hamilton-syklus. En Hamilton-syklus starter og slutter i samme hjørne. Så Hamilton-syklusen vil være ADCHBEA.
