Typer grafer i datastruktur med eksempler
Sarah Chen
En graf er en ikke-lineær datastruktur som består av hjørner og kanter. Toppene inneholder informasjonen eller dataene, og kantene fungerer som en kobling mellom par av 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 betyr retningen. Pilen bestemmer hvor kanten peker mot eller slutter.
Her er et eksempel på Directed Graph.
- Vi kan gå fra node A til D.
- Vi kan imidlertid ikke gå fra node D til node A da 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
Udirigert graf inneholder kanter uten pekere. Det betyr at vi kan reise omvendt mellom to hjørner.
Her er et enkelt eksempel på den urettede grafen.
I grafen ovenfor,
- Vi kan gå fra A til B
- Vi kan også flytte fra B til A
- Kanter inneholder ingen retninger.
Det er et eksempel på en urettet graf som har et begrenset antall hjørner og kanter uten vekter.
Vektet graf
Graf som inneholder vekter eller kostnader på kantene kalles en vektet graf. Den numeriske verdien representerer vanligvis flyttekostnaden fra ett toppunkt til et annet toppunkt. Både Directed og Undirected Graph kan ha vekter på kantene.
Her er et eksempel på en vektet graf (rettet).
- A til B, det er en kant, og vekten er 5, noe som betyr å flytte fra A til B vil koste oss 5.
- Et punkt til 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 å flytte fra A til F, er det flere veier. Banene er ADF, ABF. ADF vil koste (10+11) eller 21.
- Her vil banen ABF koste (5+15) eller 20. Her legger vi til vekten av hver kant i banen.
Her er et eksempel på en urettet graf med vekter:
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 og urettede grafer har en felles egenskap. Det vil si
- Vanligvis kan den urettede grafen ha én kant mellom to toppunkter.
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:
Å reise fra A til D vil koste oss 17, men å reise fra D til A vil koste oss 12. Så vi kan ikke tilordne 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 den også er en tilkoblet graf, vil den også inneholde et uendelig antall kanter. Her betyr de utvidede kantene at flere kanter kan kobles til disse nodene via kanter.
Her er et eksempel på den uendelige grafen:
Null graf
Null Graph inneholder bare noder eller hjørner, men uten kanter. Hvis gitt en graf G = (V, E), der V er hjørner og E er kanter, vil den være null hvis antall kanter E er null.
Her er et eksempel på en null-graf:
Triviell graf
En grafdatastruktur anses som triviell hvis bare ett toppunkt eller node er til stede uten kanter.
Her er et eksempel på en trivial graf:
Multi Graph
En graf kalles en multigraf når flere kanter er tilstede mellom to toppunkter, eller toppunktet har en løkke. Begrepet "løkke" i Graph Data Structure betyr en kant som peker til samme node eller toppunkt. Multigraf kan være rettet eller urettet.
Her er et eksempel på en multigraf:
Det er to kanter fra B til A. I tillegg har toppunktet E en selvløkke. Grafen ovenfor er en rettet graf uten vekter på kantene.
Komplett graf
En graf er komplett hvis hvert toppunkt har rettede eller urettede kanter med alle andre toppunkter.
Anta at det er et totalt V-antall toppunkter og hvert toppunkt har nøyaktig V-1-kanter. Da vil denne grafen bli kalt en komplett graf. I denne typen grafer er hvert toppunkt koblet til alle andre toppunkter via kanter.
Her er et eksempel på en komplett graf med fem hjørner:
Du kan se på bildet det totale antallet noder er fem, og alle nodene har nøyaktig fire kanter.
Tilkoblet graf
En graf kalles en tilkoblet graf hvis vi starter fra en node eller toppunkt og reiser 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 tilkoblet graf:
Her er noen forklaringer på grafen ovenfor "komplett grafeksempel":
- Forutsatt at det ikke er noen kant mellom C og F, kan vi ikke reise fra A til G. Imidlertid gjør kanten C til F oss i stand til å 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 en eller flere sykluser til stede i grafen.
Her er et eksempel på en syklisk graf:
Her danner toppunkt A, B og C en syklus.
En graf kan ha flere sykluser inni seg.
Regissert syklisk graf (DAG)
En graf kalles Directed Acyclic Graph eller DAG hvis det ikke er noen sykluser inne i en graf. DAG er viktig mens du gjør Topologisk sortering eller finne henrettelsesordren. DAG er også viktig for å lage planleggingssystemer eller skanningsavhengighet av ressurser osv. Imidlertid inneholder grafen ovenfor ikke noen syklus inne.
Her er et enkelt eksempel på en rettet asyklisk graf (DAG):
Syklusgraf
Cycle Graph er ikke det samme som den sykliske grafen. I Cycle Graph vil hver node ha nøyaktig to kanter koblet sammen, 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 toppunktene er tilordnet to sett.
Bipartite Graph må følge regelen:
- To sett med toppunkter bør være forskjellige, noe som betyr at alle toppunktene må deles inn i to grupper eller sett.
- Samme sett Vertices skal ikke danne noen kanter.
Euler graf
Grafdatastrukturer betraktes som en Euler-graf hvis alle toppunktene har en partallsgrad. Begrepet grad av toppunkter betyr antall kanter som peker til eller peker ut fra et bestemt toppunkt.
Her er et eksempel på en Euler-graf:
Alle toppunktene har jevne grader. Toppunkt A, D, E og H har to grader. Her har node C fire grader, som er partall.
Hamilton-graf
Hamilton Graph er en Connect Graph, der du kan besøke alle toppunktene fra et gitt toppunkt uten å gå tilbake til samme node eller bruke samme kant. Denne typen Connected Graph er kjent som "Hamilton Graph". Banen du besøker for å bekrefte om den gitte grafen er Hamilton-graf eller ikke, er kjent som Hamiltonsk bane.
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 ADCHBE. Det er også mulig å finne en Hamilton Cycle. Hamilton-syklusen starter og slutter ved samme toppunkt. Så Hamilton-syklusen blir det ADCHBEA.