Typer af grafer i datastruktur med eksempler
Sarah Chen
En graf er en ikke-lineær datastruktur, der består af hjørner og kanter. Toppunkterne indeholder informationen eller dataene, og kanterne fungerer som et bindeled mellem par af hjørner.
Grafer kan være af flere typer, afhængigt af positionen af noderne og kanterne. Her er nogle vigtige typer grafer:
Instrueret graf
Kanterne på den rettede graf indeholder pile, der betyder retningen. Pilen bestemmer, hvor kanten peger på eller ender.
Her er et eksempel på den rettede graf.
- Vi kan gå fra Node A til D.
- Vi kan dog ikke gå fra node D til node A, da kanten peger fra A til D.
- Da grafen ikke har vægte, vil det at rejse fra toppunkt A til D koste det samme som at rejse fra D til F.
Udirigeret graf
Udirigeret graf indeholder kanter uden pegepinde. Det betyder, at vi kan rejse omvendt mellem to hjørner.
Her er et simpelt eksempel på den urettede graf.
I ovenstående graf,
- Vi kan flytte fra A til B
- Vi kan også flytte fra B til A
- Kanter indeholder ingen retninger.
Det er et eksempel på en urettet graf med et begrænset antal hjørner og kanter uden vægt.
Vægtet graf
Graf, der indeholder vægte eller omkostninger på kanterne, kaldes en vægtet graf. Den numeriske værdi repræsenterer generelt de flytteomkostninger fra et toppunkt til et andet toppunkt. Både Directed og Undirected Graph kan have vægte på deres kanter.
Her er et eksempel på en vægtet graf (rettet).
- A til B, der er en kant, og vægten er 5, hvilket betyder, at flytning fra A til B vil koste os 5.
- Et punkt til B, men i denne graf har B ingen direkte kant over A. Så vi kan ikke rejse fra B til A.
- Men hvis vi ønsker at flytte fra A til F, er der flere veje. Stierne er ADF, ABF. ADF vil koste (10+11) eller 21.
- Her vil stien ABF koste (5+15) eller 20. Her tilføjer vi vægten af hver kant i stien.
Her er et eksempel på en udirigeret graf med vægte:
Her har kanten vægt, men ingen retning. Så det betyder at rejse fra toppunkt A til D vil koste 10 og omvendt.
Tovejs graf
Tovejs- og urettede grafer har en fælles egenskab. Det er
- Generelt kan den urettede graf have en kant mellem to toppunkter.
For eksempel:
- Her vil det koste 10,- at flytte fra A til D eller D til A.
- I en tovejsgraf kan vi have to kanter mellem to hjørner.
Her er et eksempel:
At rejse fra A til D vil koste os 17, men at rejse fra D til A vil koste os 12. Så vi kan ikke tildele to forskellige vægte, hvis det er en urettet graf.
Uendelig graf
Grafen vil indeholde et uendeligt antal kanter og noder. Hvis en graf er uendelig, og den også er en forbundet graf, vil den også indeholde et uendeligt antal kanter. Her betyder de forlængede kanter, at flere kanter kan forbindes til disse noder via kanter.
Her er et eksempel på den uendelige graf:
Nul graf
Null Graph indeholder kun noder eller hjørner, men uden kanter. Hvis der gives en graf G = (V, E), hvor V er hjørner og E er kanter, vil den være nul, hvis antallet af kanter E er nul.
Her er et eksempel på en null-graf:
Triviel graf
En grafdatastruktur betragtes som triviel, hvis kun et toppunkt eller en knude er til stede uden kanter.
Her er et eksempel på en trivial graf:
Multi graf
En graf kaldes en multigraf, når der er flere kanter mellem to spidser, eller spidsen har en løkke. Udtrykket "løkke" i Graph Data Structure betyder en kant, der peger på den samme knude eller vertex. Multigraf kan være instrueret eller urettet.
Her er et eksempel på en multigraf:
Der er to kanter fra B til A. Desuden har toppunktet E en selvløkke. Ovenstående graf er en rettet graf uden vægt på kanter.
Komplet graf
En graf er komplet, hvis hvert toppunkt har rettede eller urettede kanter med alle andre toppunkter.
Antag, at der er et samlet V-antal af hjørner, og hvert hjørne har nøjagtig V-1 kanter. Så vil denne graf blive kaldt en komplet graf. I denne graftype er hvert hjørne forbundet med alle andre hjørner via kanter.
Her er et eksempel på en komplet graf med fem hjørner:
Du kan se på billedet, at det samlede antal noder er fem, og alle noder har præcis fire kanter.
Forbundet graf
En graf kaldes en forbundet graf, hvis vi starter fra en knude eller et toppunkt og rejser alle knudepunkter fra startknuden. Til dette skal der være mindst én kant mellem hvert par knudepunkter eller knudepunkter.
Her er et eksempel på en Connected Graph:
Her er en forklaring på ovenstående "komplet grafeksempel"-graf:
- Hvis vi antager, at der ikke er nogen kant mellem C og F, kan vi ikke rejse fra A til G. Men kanten C til F gør os i stand til at rejse til en hvilken som helst knude fra en given knude.
- En komplet graf er en forbundet graf, fordi vi kan flytte fra en node til en hvilken som helst anden node i den givne graf.
Cyklisk graf
En graf siges at være cyklisk, hvis der er en eller flere cyklusser til stede i grafen.
Her er et eksempel på en cyklisk graf:
Her danner toppunkt A, B og C en cyklus.
En graf kan have flere cyklusser inde i den.
Instrueret acyklisk graf (DAG)
En graf kaldes Directed Acyclic Graph eller DAG, hvis der ikke er nogen cyklusser inde i en graf. DAG er vigtig, mens du gør Topologisk sortering eller finde fuldbyrdelsesordren. DAG er også vigtig for at skabe planlægningssystemer eller scanningsafhængighed af ressourcer osv. Ovenstående graf indeholder dog ingen cyklus inde.
Her er et simpelt eksempel på en rettet acyklisk graf (DAG):
Cyklus graf
Cyklusgraf er ikke det samme som den cykliske graf. I Cycle Graph vil hver node have nøjagtigt to kanter forbundet, hvilket betyder, at hver node vil have præcis to grader.
Her er et eksempel på en cyklusgraf:
Bipartitegraf
Disse slags Grafer er specielle slags grafer, hvor toppunkter er tildelt to sæt.
Bipartite Graph skal følge reglen:
- To sæt knudepunkter skal være adskilte, hvilket betyder, at alle knudepunkter skal opdeles i to grupper eller sæt.
- Samme sæt Hjørner bør ikke danne nogen kanter.
Euler graf
Grafdatastrukturer betragtes som en Euler-graf, hvis alle hjørnerne har en lige-nummereret grad. Udtrykket grad af toppunkter betyder antallet af kanter, der peger på eller peger ud fra et bestemt toppunkt.
Her er et eksempel på en Euler-graf:
Alle hjørner har lige grader. Toppunkt A, D, E og H har to grader. Her har node C fire grader, hvilket er lige.
Hamilton graf
Hamilton Graph er en Connect Graph, hvor du kan besøge alle toppunkter fra et givet toppunkt uden at gå tilbage til den samme node eller bruge den samme kant. Denne form for forbundet graf er kendt som "Hamilton-grafen". Stien, du besøger for at kontrollere, om den givne graf er Hamilton-graf eller ej, er kendt som Hamilton-sti.
Her er et simpelt grafeksempel på en Hamilton:
På dette billede kan vi besøge alle hjørnerne fra enhver knude i ovenstående graf. En af stierne kan være ADCHBE. Det er også muligt at finde en Hamilton Cycle. Hamilton-cyklus starter og slutter ved samme toppunkt. Så Hamilton Cycle vil være ADCHBEA.
