Typer av grafer i datastruktur med exempel
Redaktionellt team
⚡ Smart sammanfattning
Grafer i datastrukturer är icke-linjära samlingar av noder och kanter klassificerade i familjer såsom riktade, oriktade, viktade, cykliska, acykliska, fullständiga, sammanhängande, tvådelade, Euler- och Hamilton-grafer baserat på struktur.
En graf är en icke-linjär datastruktur som består av noder och kanter. Noderna innehåller informationen eller data, och kanterna fungerar som en länk mellan ett par noder.
Grafer kan vara av flera typer, beroende på nodernas och kanternas position. Här är några viktiga typer av grafer:
Regisserad graf
Kanterna på den riktade grafen innehåller pilar som anger riktningen. Pilen anger var kanten pekar mot eller slutar. Här är ett exempel på den riktade grafen.
Regisserad graf
- Vi kan gå från nod A till D.
- Vi kan dock inte gå från nod D till nod A, eftersom kanten pekar från A till D.
- Eftersom grafen inte har vikter kommer det att kosta samma sak att resa från vertex A till D som att resa från D till F.
Oriktad graf
En oriktad graf innehåller kanter utan pekare. Det betyder att vi kan röra oss tvärtom mellan två noder. Här är ett enkelt exempel på en oriktad graf.
Oriktad graf
I diagrammet ovan,
- Vi kan förflytta oss från A till B.
- Vi kan också gå från B till A.
- Kanter innehåller inga anvisningar.
Det är ett exempel på en oriktad graf med ett ändligt antal noder och kanter utan vikter.
Viktad graf
En graf som innehåller vikter eller kostnader på kanterna kallas en viktad graf. Det numeriska värdet representerar generellt den förflyttande kostnaden från ett hörn till ett annat. Både riktade och oriktade grafer kan ha vikter på sina kanter. Här är ett exempel på en viktad graf (riktad).
Riktad graf med vikt
- A till B, det finns en kant, och vikten är 5, vilket innebär att att flytta från A till B kommer att kosta oss 5.
- A pekar mot B, men i den här grafen har B ingen direkt kant över A. Så vi kan inte resa från B till A.
- Men om vi vill gå från A till F finns det flera vägar. Vägarna är ADF och ABF. ADF kostar (10+11) eller 21.
- Här kommer vägen ABF att kosta (5+15) eller 20. Här adderar vi vikten för varje kant i vägen.
Här är ett exempel på en oriktad graf med vikter:
Oriktad graf med vikt
Här har kanten vikt men ingen riktning. Så det betyder att resa från vertex A till D kommer att kosta 10 och vice versa.
Dubbelriktad graf
Dubbelriktade och oriktade grafer har en gemensam egenskap. Det är:
- Generellt kan en oriktad graf ha en kant mellan två noder.
Till exempel:
- Här kommer det att kosta 10 att flytta från A till D eller D till A.
- I en dubbelriktad graf kan vi ha två kanter mellan två hörn.
Här är ett exempel:
Dubbelriktad graf
Att resa från A till D kostar oss 17, men att resa från D till A kostar oss 12. Så vi kan inte tilldela två olika vikter om det är en oriktad graf.
Oändlig graf
Grafen kommer att innehålla ett oändligt antal kanter och noder. Om en graf är oändlig och även är en sammanhängande graf, kommer den också att innehålla ett oändligt antal kanter. Här betyder de utökade kanterna att fler kanter kan vara sammankopplade med dessa noder via kanter. Här är ett exempel på den oändliga grafen:
Oändlig graf
Null graf
En nollgraf innehåller endast noder eller noder men utan kanter. Om grafen G = (V, E) ges, där V är noder och E är kanter, kommer den att vara noll om antalet kanter E är noll. Här är ett exempel på en nollgraf:
Null graf
Trivial graf
En grafdatastruktur anses trivial om endast en nod eller nod finns utan kanter. Här är ett exempel på en trivialgraf:
Multi Graph
En graf kallas en multigraf när flera kanter finns mellan två noder, eller när noden har en loop. Termen "loop" i grafdatastruktur betyder en kant som pekar mot samma nod eller nod. En multigraf kan vara riktad eller oriktad. Här är ett exempel på en multigraf:
Det finns två kanter från B till A. Dessutom har hörn E en självloop. Grafen ovan är en riktad graf utan vikter på kanterna.
Komplett graf
En graf är komplett om varje nodpunkt har riktade eller oriktade kanter med alla andra noder. Antag att det finns totalt V noder och varje nodpunkt har exakt V-1 kanter. Då kommer denna graf att kallas en komplett graf. I denna typ av graf är varje nodpunkt förbunden med alla andra noder via kanter. Här är ett exempel på en komplett graf med fem noder:
Du kan se på bilden att det totala antalet noder är fem, och alla noder har exakt fyra kanter.
Ansluten graf
En graf kallas en sammanhängande graf om vi börjar från en nod eller ett hörn och kan färdas till alla noder från startnoden. För detta bör det finnas minst en kant mellan varje par av noder eller hörn. Här är ett exempel på en sammanhängande graf:
Här är en förklaring av ovanstående sammanhängande graf:
- Om vi antar att det inte finns någon kant mellan C och F, kan vi inte färdas från A till G. Kanten C till F gör det dock möjligt för oss att färdas till vilken nod som helst från en given nod.
- En komplett graf är en sammankopplad graf eftersom vi kan flytta från en nod till vilken annan nod som helst i den givna grafen.
Cyklisk graf
En graf sägs vara cyklisk om det finns en eller flera cykler i grafen. Här är ett exempel på en cyklisk graf:
Här bildar punkterna A, B och C en cykel. En graf kan ha flera cykler inuti sig.
Regisserad acyklisk graf (DAG)
En graf kallas en riktad acyklisk graf eller DAG om det inte finns några cykler inuti grafen. DAG är viktig när man utför Topologisk sortering eller hitta exekveringsordningen. DAG är också viktigt för att skapa schemaläggningssystem eller skanna beroenden av resurser, etc. Grafen ovan innehåller dock ingen cykel inuti. Här är ett enkelt exempel på en riktad acyklisk graf (DAG):
Cykeldiagram
En cykelgraf är inte samma sak som en cyklisk graf. I en cykelgraf har varje nod exakt två sammankopplade kanter, vilket innebär att varje nod har exakt två grader. Här är ett exempel på en cykelgraf:
Bipartitgraf
Dessa typer av Grafer är speciella typer av grafer där noder tilldelas två mängder. En tvådelad graf måste följa regeln:
- De två uppsättningarna av noder ska vara distinkta, vilket innebär att alla noder måste delas in i två grupper eller uppsättningar.
- Samma mängd noder bör inte bilda några kanter.
Euler graf
En grafdatastruktur betraktas som en Eulergraf om alla noder har en jämn grad. Termen grad av noder avser antalet kanter som pekar mot eller ut från ett visst nodpunkt. Här är ett exempel på en Eulergraf:
Alla noder har jämna grader. Noderna A, D, E och H har två grader. Här har nod C fyra grader, vilket är jämnt.
Hamilton graf
En Hamiltongraf är en sammanhängande graf, där du kan besöka alla noder från ett givet nodpunkt utan att återvända till samma nod eller använda samma kant. Denna typ av sammanhängande graf kallas "Hamiltongrafen". Den väg du besöker för att verifiera om den givna grafen är en Hamiltongraf eller inte kallas Hamiltonbanan. Här är ett enkelt grafexempel på en Hamilton:
I den här bilden kan vi besöka alla hörn från vilken nod som helst i ovanstående graf. En av vägarna kan vara ADCHBEDet är också möjligt att hitta en Hamiltoncykel. En Hamiltoncykel börjar och slutar vid samma hörn. Så Hamiltoncykeln kommer att vara ADCHBEA.
