Typer af grafer i datastruktur med eksempler
Redaktionelle team
⚡ Smart opsummering
Grafer i datastrukturer er ikke-lineære samlinger af hjørner og kanter klassificeret i familier såsom rettede, urettede, vægtede, cykliske, acykliske, komplette, sammenhængende, todelte, Euler- og Hamilton-grafer baseret på struktur.
En graf er en ikke-lineær datastruktur, der består af hjørner og kanter. Hjørnpunkterne indeholder informationen eller dataene, og kanterne fungerer som et forbindelsesled mellem et par hjørner.
Grafer kan være af flere typer, afhængigt af placeringen af knuder og kanter. Her er nogle vigtige typer grafer:
Instrueret graf
Kanterne af den rettede graf indeholder pile, der angiver retningen. Pilen bestemmer, hvor kanten peger på eller slutter. Her er et eksempel på den rettede graf.
Instrueret 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
En urettet graf indeholder kanter uden pointere. Det betyder, at vi kan bevæge os omvendt mellem to hjørner. Her er et simpelt eksempel på en urettet graf.
Udirigeret graf
I ovenstående graf,
- Vi kan bevæge os fra A til B.
- Vi kan også bevæge os fra B til A.
- Kanter indeholder ingen retninger.
Det er et eksempel på en urettet graf med et endeligt antal hjørner og kanter uden vægte.
Vægtet graf
En graf, der indeholder vægte eller omkostninger på kanterne, kaldes en vægtet graf. Den numeriske værdi repræsenterer generelt de bevægelige omkostninger fra et hjørne til et andet. Både rettede og ikke-rettede grafer kan have vægte på deres kanter. Her er et eksempel på en vægtet graf (rettet).
Instrueret graf med vægt
- A til B, der er en kant, og vægten er 5, hvilket betyder, at det vil koste os 5 at flytte fra A til B.
- A peger på B, men i denne graf har B ingen direkte kant over A. Så vi kan ikke rejse fra B til A.
- Men hvis vi vil gå fra A til F, er der flere veje. Vejene er ADF og ABF. ADF koster (10+11) eller 21.
- Her vil stien ABF koste (5+15) eller 20. Her lægger vi vægten af hver kant i stien sammen.
Her er et eksempel på en urettet graf med vægte:
Udirigeret graf med vægt
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
Tovejsgrafer og ikke-vejsgrafer har en fælles egenskab. Det er:
- Generelt kan en urettet graf have én kant mellem to hjørner.
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:
Tovejs graf
Det koster os 17 at rejse fra A til D, men 12 at rejse fra D til A. 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 knuder. Hvis en graf er uendelig og også er en sammenhængende graf, vil den også indeholde et uendeligt antal kanter. Her betyder de udvidede kanter, at flere kanter kan være forbundet til disse knuder via kanter. Her er et eksempel på den uendelige graf:
Uendelig graf
Nul graf
En nulgraf indeholder kun noder eller hjørner, men uden kanter. Hvis grafen 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 nulgraf:
Nul graf
Triviel graf
En grafdatastruktur betragtes som triviel, hvis kun ét hjørne eller én node er til stede uden kanter. Her er et eksempel på en triviel graf:
Multi graf
En graf kaldes en multigraf, når der er flere kanter mellem to hjørner, eller når hjørnet har en løkke. Udtrykket "løkke" i grafdatastruktur betyder en kant, der peger på den samme node eller hjørne. En multigraf kan være rettet eller urettet. Her er et eksempel på en multigraf:
Der er to kanter fra B til A. Desuden har hjørne E en selvløkke. Ovenstående graf er en rettet graf uden vægte på kanterne.
Komplet graf
En graf er komplet, hvis hvert hjørne har rettede eller ikke-rettede kanter med alle andre hjørner. Antag, at der er et samlet antal hjørner på V, og hvert hjørne har præcis V-1 kanter. Så vil denne graf blive kaldt en komplet graf. I denne type graf 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 sammenhængende graf, hvis vi starter fra en node eller et hjørne og kan bevæge os til alle noderne fra startnoden. For at opnå dette skal der være mindst én kant mellem hvert par af noder eller hjørner. Her er et eksempel på en sammenhængende graf:
Her er en forklaring af ovenstående sammenhængende graf:
- Hvis der ikke er nogen kant mellem C og F, kan vi ikke rejse fra A til G. Kanten C til F gør det dog muligt for os at rejse til enhver node fra en given node.
- 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 punkterne A, B og C en cyklus. En graf kan have flere cyklusser indeni.
Instrueret acyklisk graf (DAG)
En graf kaldes en rettet acyklisk graf eller DAG, hvis der ikke er nogen cyklusser i grafen. DAG er vigtig, når man udfører Topologisk sortering eller finde udførelsesrækkefølgen. DAG er også vigtig for at oprette planlægningssystemer eller scanne afhængigheder af ressourcer osv. Grafen ovenfor indeholder dog ingen cyklus. Her er et simpelt eksempel på en rettet acyklisk graf (DAG):
Cyklus graf
En cyklusgraf er ikke det samme som en cyklisk graf. I en cyklusgraf vil hver knude have præcis to forbundet kanter, hvilket betyder, at hver knude vil have præcis to grader. Her er et eksempel på en cyklusgraf:
Bipartitegraf
Disse slags Grafer er særlige typer grafer, hvor hjørner er tildelt to sæt. En todelt graf skal følge reglen:
- De to sæt af hjørner skal være forskellige, hvilket betyder, at alle hjørner skal opdeles i to grupper eller sæt.
- Samme mængde hjørner bør ikke danne nogen kanter.
Euler graf
En grafdatastruktur betragtes som en Euler-graf, hvis alle hjørner har en lige grad. Udtrykket grad af hjørner betyder antallet af kanter, der peger på eller ud fra et bestemt hjørne. Her er et eksempel på en Euler-graf:
Alle hjørnerne har lige grader. Hjørner A, D, E og H har to grader. Her har knudepunkt C fire grader, hvilket er lige.
Hamilton graf
En Hamilton-graf er en sammenhængende graf, hvor du kan besøge alle hjørnerne fra et givet hjørne uden at besøge den samme node eller bruge den samme kant igen. Denne type sammenhængende graf er kendt som "Hamilton-grafen". Den sti, du besøger for at verificere, om den givne graf er en Hamilton-graf eller ej, er kendt som Hamilton-stien. 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 ADCHBEDet er også muligt at finde en Hamilton-cyklus. En Hamilton-cyklus starter og slutter ved samme hjørne. Så Hamilton-cyklussen vil være ADCHBEA.
