Soorten grafieken in gegevensstructuur met voorbeelden

Een grafiek is een niet-lineaire gegevensstructuur die bestaat uit hoekpunten en randen. De hoekpunten bevatten de informatie of gegevens, en de randen werken als een link tussen een paar hoekpunten.

Grafieken kunnen van meerdere typen zijn, afhankelijk van de positie van de knooppunten en randen. Hier volgen enkele belangrijke typen grafieken:

Gerichte grafiek

De randen van de gerichte grafiek bevatten pijlen die de richting aangeven. De pijl bepaalt waar de rand naartoe wijst of eindigt.

Hier is een voorbeeld van de gerichte grafiek.

We kunnen van knooppunt A naar D gaan.
We kunnen echter niet van knooppunt D naar knooppunt A gaan, omdat de rand van A naar D wijst.
Omdat de grafiek geen gewichten heeft, kost het reizen van hoekpunt A naar D hetzelfde als reizen van D naar F.

Ongerichte grafiek

Ongerichte grafiek bevat randen zonder wijzers. Het betekent dat we omgekeerd tussen twee hoekpunten kunnen reizen.

Hier is een eenvoudig voorbeeld van de ongerichte grafiek.

In de bovenstaande grafiek,

Wij kunnen ons van A naar B verplaatsen
We kunnen ook van B naar A gaan
Randen bevatten geen richtingen.

Het is een voorbeeld van een ongerichte grafiek met een eindig aantal hoekpunten en randen zonder gewichten.

Gewogen grafiek

Een grafiek met gewichten of kosten aan de randen wordt een gewogen grafiek genoemd. De numerieke waarde vertegenwoordigt doorgaans de verplaatsingskosten van het ene hoekpunt naar het andere hoekpunt. Zowel de gerichte als de ongerichte grafiek kunnen gewichten aan de randen hebben.

Hier is een voorbeeld van een gewogen grafiek (gericht).

Van A naar B is er een voorsprong en het gewicht is 5, wat betekent dat het verplaatsen van A naar B ons 5 kost.
Een punt naar B, maar in deze grafiek heeft B geen directe voorsprong op A. We kunnen dus niet van B naar A reizen.
Als we echter van A naar F willen gaan, zijn er meerdere paden. De paden zijn ADF, ABF. ADF kost (10+11) of 21.
Hier kost het pad ABF (5+15) of 20. Hier tellen we het gewicht van elke rand in het pad op.

Hier is een voorbeeld van een ongerichte grafiek met gewichten:

Hier heeft de rand gewicht maar geen richting. Het betekent dus dat reizen van hoekpunt A naar D 10 euro kost en omgekeerd.

Bidirectionele grafiek

Bidirectionele en ongerichte grafieken hebben een gemeenschappelijke eigenschap. Dat is

Over het algemeen kan de ongerichte grafiek één rand tussen twee hoekpunten hebben.

Bijvoorbeeld:

Hier kost het verplaatsen van A naar D of D naar A 10.
In een bidirectionele grafiek kunnen we twee randen tussen twee hoekpunten hebben.

Hier is een voorbeeld:

Reizen van A naar D kost ons 17, maar reizen van D naar A kost ons 12. We kunnen dus geen twee verschillende gewichten toekennen als het een ongerichte grafiek is.

Oneindige grafiek

De grafiek bevat een oneindig aantal randen en knooppunten. Als een grafiek oneindig is en het is ook een samenhangende grafiek, dan zal deze ook een oneindig aantal randen bevatten. Hier betekenen de verlengde randen dat meer randen via randen met deze knooppunten kunnen worden verbonden.

Hier is een voorbeeld van de oneindige grafiek:

Nulgrafiek

Null Graph bevat alleen knooppunten of hoekpunten, maar zonder randen. Als er een grafiek G = (V, E) wordt gegeven, waarbij V hoekpunten is en E randen, zal deze nul zijn als het aantal randen E nul is.

Hier is een voorbeeld van een nulgrafiek:

Triviale grafiek

Een grafiekgegevensstructuur wordt als triviaal beschouwd als er slechts één hoekpunt of knooppunt aanwezig is zonder randen.

Hier is een voorbeeld van een triviale grafiek:

Multigrafiek

Een grafiek wordt een multigraaf genoemd als er meerdere randen aanwezig zijn tussen twee hoekpunten, of als het hoekpunt een lus heeft. De term 'lus' in de grafiekgegevensstructuur betekent een rand die naar hetzelfde knooppunt of hoekpunt wijst. Multigraph kan gericht of ongericht zijn.

Hier is een voorbeeld van een multigrafiek:

Er zijn twee randen van B naar A. Bovendien heeft hoekpunt E een zelflus. De bovenstaande grafiek is een gerichte grafiek zonder gewichten op de randen.

Volledige grafiek

Een grafiek is compleet als elk hoekpunt gerichte of ongerichte randen heeft met alle andere hoekpunten.

Stel dat er een totaal V-aantal hoekpunten is en dat elk hoekpunt precies V-1-randen heeft. Deze grafiek wordt dan een volledige grafiek genoemd. In dit type grafiek is elk hoekpunt via randen verbonden met alle andere hoekpunten.

Hier is een voorbeeld van een volledige grafiek met vijf hoekpunten:

Je kunt in de afbeelding zien dat het totale aantal knooppunten vijf is, en alle knooppunten hebben precies vier randen.

Verbonden grafiek

Een grafiek wordt een verbonden grafiek genoemd als we beginnen vanaf een knooppunt of hoekpunt en alle knooppunten vanaf het startknooppunt doorlopen. Hiervoor moet er ten minste één rand zijn tussen elk paar knooppunten of hoekpunten.

Hier is een voorbeeld van een verbonden grafiek:

Hier is wat uitleg over de bovenstaande “volledige grafiekvoorbeeld”-grafiek:

Ervan uitgaande dat er geen grens is tussen C en F, kunnen we niet van A naar G reizen. De grens C naar F stelt ons echter in staat om vanaf een bepaald knooppunt naar elk knooppunt te reizen.
Een volledige grafiek is een verbonden grafiek omdat we van een knooppunt naar elk ander knooppunt in de gegeven grafiek kunnen gaan.

Cyclische grafiek

Er wordt gezegd dat een grafiek cyclisch is als er een of meer cycli in de grafiek aanwezig zijn.

Hier is een voorbeeld van een cyclische grafiek:

Hier vormen hoekpunten A, B en C een cyclus.

Een grafiek kan meerdere cycli bevatten.

Gerichte Acyclische Grafiek (DAG)

Een grafiek wordt Directed Acyclic Graph of DAG genoemd als er geen cycli in een grafiek voorkomen. DAG is belangrijk tijdens het doen van de Topologische sortering of het vinden van het executiebevel. DAG is ook belangrijk voor het maken van planningssystemen of het scannen van de afhankelijkheid van bronnen enz. De bovenstaande grafiek bevat echter geen enkele cyclus.

Hier is een eenvoudig voorbeeld van een gerichte acyclische grafiek (DAG):

Cyclusgrafiek

Cyclusgrafiek is niet hetzelfde als de cyclische grafiek. In Cycle Graph heeft elk knooppunt precies twee verbonden randen, wat betekent dat elk knooppunt precies twee graden heeft.

Hier is een voorbeeld van een cyclusgrafiek:

Bipartiete grafiek

Dit soort Grafieken zijn speciale soorten grafieken waarbij hoekpunten aan twee sets worden toegewezen.

Bipartiete grafiek moet de regel volgen:

Twee sets hoekpunten moeten verschillend zijn, wat betekent dat alle hoekpunten in twee groepen of sets moeten worden verdeeld.
Dezelfde reeks hoekpunten mogen geen randen vormen.

Euler-grafiek

Grafiekgegevensstructuren worden als een Euler-grafiek beschouwd als alle hoekpunten een even genummerde graad hebben. De term graad van hoekpunten betekent het aantal randen dat naar een bepaald hoekpunt wijst of eruit wijst.

Hier is een voorbeeld van een Euler-grafiek:

Alle hoekpunten hebben even graden. Hoekpunt A, D, E en H hebben twee graden. Hier heeft knooppunt C vier graden, wat even is.

Hamilton-grafiek

Hamilton Graph is een Connect Graph, waarmee u alle hoekpunten van een bepaald hoekpunt kunt bezoeken zonder hetzelfde knooppunt opnieuw te bezoeken of dezelfde rand te gebruiken. Dit soort verbonden grafieken staat bekend als de ‘Hamilton-grafiek’. Het pad dat u bezoekt om te verifiëren of de gegeven grafiek een Hamiltongrafiek is of niet, staat bekend als Hamiltoniaans pad.

Hier is een eenvoudig grafisch voorbeeld van een Hamilton:

In deze afbeelding kunnen we alle hoekpunten van elk knooppunt in de bovenstaande grafiek bezoeken. Een van de paden kan zijn ADCHBE. Het is ook mogelijk om een Hamilton Cycle te vinden. Hamiltoncyclus begint en eindigt op hetzelfde hoekpunt. Dus de Hamilton-cyclus zal dat zijn ADCHBEA.