Typer av grafer i datastruktur med exempel

En graf är en icke-linjär datastruktur som består av hörn och kanter. Topparna innehåller informationen eller data, och kanterna fungerar som en länk mellan par av hörn.

Grafer kan vara av flera typer, beroende på positionen för noderna och kanterna. Här är några viktiga typer av grafer:

Regisserad graf

Kanterna på den riktade grafen innehåller pilar som betyder riktningen. Pilen bestämmer var kanten pekar mot eller slutar.

Här är ett exempel på den riktade grafen.

• 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

Oriktad graf innehåller kanter utan pekare. Det betyder att vi kan resa vice versa mellan två hörn.

Här är ett enkelt exempel på den oriktade grafen.

I diagrammet ovan,

• Vi kan gå från A till B
• Vi kan också flytta från B till A
• Kanter innehåller inga anvisningar.

Det är ett exempel på en oriktad graf som har ett ändligt antal hörn och kanter utan vikter.

Viktad graf

Graf som innehåller vikter eller kostnader på kanterna kallas en viktad graf. Det numeriska värdet representerar i allmänhet förflyttningskostnaden från en vertex till en annan vertex. Både riktad och oriktad graf kan ha vikter på sina kanter.

Här är ett exempel på en viktad graf (riktad).

• A till B, det finns en kant, och vikten är 5, vilket betyder att flytta från A till B kommer att kosta oss 5.
• A punkt till 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 flytta från A till F finns det flera vägar. Banorna är ADF, ABF. ADF kommer att kosta (10+11) eller 21.
• Här kommer banan ABF att kosta (5+15) eller 20. Här lägger vi till vikten av varje kant i banan.

Här är ett exempel på en oriktad graf med vikter:

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

• I allmänhet kan den oriktade grafen ha en kant mellan två hörn.

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:

Att resa från A till D kommer att kosta oss 17, men att resa från D till A kommer att kosta 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 den också är en sammankopplad graf, kommer den också att innehålla ett oändligt antal kanter. Här innebär de förlängda kanterna att fler kanter kan vara anslutna till dessa noder via kanter.

Här är ett exempel på den oändliga grafen:

Null graf

Null Graph innehåller bara noder eller hörn men utan kanter. Om det ges en graf G = (V, E), där V är hörn och E är kanter, kommer den att vara noll om antalet kanter E är noll.

Här är ett exempel på en nollgraf:

Trivial graf

En grafdatastruktur anses trivial om endast en vertex eller nod finns utan kanter.

Här är ett exempel på en trivial graf:

Multi Graph

En graf kallas en multigraf när flera kanter finns mellan två hörn, eller när hörnet har en slinga. Termen "loop" i Graph Data Structure betyder en kant som pekar mot samma nod eller vertex. 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 vertex E en självslinga. Ovanstående graf är en riktad graf utan vikter på kanter.

Komplett graf

En graf är komplett om varje vertex har riktade eller oriktade kanter med alla andra hörn.

Anta att det finns ett totalt V antal hörn och varje vertex har exakt V-1 kanter. Då kommer denna graf att kallas en komplett graf. I denna typ av graf är varje vertex ansluten till alla andra hörn via kanter.

Här är ett exempel på en komplett graf med fem hörn:

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 sammankopplad graf om vi utgår från en nod eller vertex och reser 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 ansluten graf:

Här är en förklaring av ovanstående "fullständiga grafexempel"-graf:

• Om vi ​​antar att det inte finns någon kant mellan C och F, kan vi inte resa från A till G. Men kanten C till F gör att vi kan resa 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 hörn A, B och C en cykel.

En graf kan ha flera cykler inuti den.

Regisserad acyklisk graf (DAG)

En graf kallas riktad acyklisk graf eller DAG om det inte finns några cykler i en graf. DAG är viktigt när du gör Topologisk sortering eller hitta exekutionsordern. DAG är också viktigt för att skapa schemaläggningssystem eller skanningsberoende av resurser etc. Ovanstående graf innehåller dock ingen cykel inuti.

Här är ett enkelt exempel på en riktad acyklisk graf (DAG):

Cykeldiagram

Cycle Graph är inte detsamma som den cykliska grafen. I Cycle Graph kommer varje nod att ha exakt två kanter anslutna, vilket betyder att varje nod har exakt två grader.

Här är ett exempel på en cykeldiagram:

Bipartitgraf

Dessa typer av Grafer är speciella typer av grafer där hörn tilldelas två uppsättningar.

Bipartite Graph måste följa regeln:

• Två uppsättningar av hörn bör vara distinkta, vilket innebär att alla hörn måste delas upp i två grupper eller uppsättningar.
• Samma uppsättning Vertices bör inte bilda några kanter.

Euler graf

Grafdatastrukturer anses vara en Euler-graf om alla hörn har en jämnt numrerad grad. Termen grad av hörn betyder antalet kanter som pekar mot eller pekar ut från en viss vertex.

Här är ett exempel på en Euler-graf:

Alla hörn har jämna grader. Vertex A, D, E och H har två grader. Här har nod C fyra grader, vilket är jämnt.

Hamilton graf

Hamilton Graph är en Connect Graph, där du kan besöka alla hörn från en given vertex utan att gå tillbaka till samma nod eller använda samma kant. Denna typ av ansluten graf är känd som "Hamilton-grafen". Sökvägen du besöker för att verifiera om den givna grafen är Hamilton-graf eller inte är känd som Hamiltonsk väg.

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 ADCHBE. Det är också möjligt att hitta en Hamilton Cycle. Hamilton-cykeln börjar och slutar vid samma vertex. Så kommer Hamilton-cykeln att vara ADCHBEA.