Grafikonok típusai az adatszerkezetben példákkal

A gráf egy nemlineáris adatstruktúra, amely csúcsokból és élekből áll. A csúcsok tartalmazzák az információkat vagy adatokat, az élek pedig összekötőként működnek a csúcspárok között.

A grafikonok többféle típusúak lehetnek, a csomópontok és az élek helyzetétől függően. Íme néhány fontos grafikontípus:

Irányított grafikon

Az Irányított grafikon élei nyilakat tartalmaznak, amelyek az irányt jelentik. A nyíl határozza meg, hogy az él hova mutat, vagy hol ér véget.

Íme egy példa az irányított grafikonra.

• Mehetünk A csomópontból D-be.
• Nem mehetünk azonban D csomópontból A csomópontba, mivel az él A-ból D-be mutat.
• Mivel a grafikonnak nincsenek súlyai, az A csúcsból D-be utazás ugyanannyiba kerül, mint a D-ből F-be utazás.

Irányítatlan gráf

Az irányítatlan gráf éleket tartalmaz mutatók nélkül. Ez azt jelenti, hogy fordítva is utazhatunk két csúcs között.

Íme egy egyszerű példa az irányítatlan grafikonra.

A fenti grafikonon

• A-ból B-be léphetünk
• B-ből A-ba is léphetünk
• Az élek nem tartalmaznak irányokat.

Ez egy példa egy irányítatlan gráfra, amelynek véges számú csúcsa és éle van súlyok nélkül.

Súlyozott grafikon

Az éleken súlyokat vagy költségeket tartalmazó grafikont súlyozott gráfnak nevezzük. A számérték általában az egyik csúcsból a másik csúcsba való áthelyezés költségét jelenti. Mind az irányított, mind az irányítatlan gráfnak súlya lehet az éleken.

Íme egy példa egy súlyozott gráfra (irányított).

• A-ból B-be, van egy él, és a súlya 5, ami azt jelenti, hogy A-ból B-be 5-be kerülünk.
• Egy pont B-be, de ebben a grafikonban B-nek nincs közvetlen éle A-val szemben. Tehát nem tudunk B-ből A-ba utazni.
• Ha azonban A-ból F-be akarunk lépni, több út is létezik. Az útvonalak ADF, ABF. Az ADF költsége (10+11) vagy 21.
• Itt az ABF útvonal kerül (5+15) vagy 20-ba. Itt hozzáadjuk az útvonal minden élének súlyát.

Íme egy példa egy irányítatlan grafikonra súlyokkal:

Itt az élnek van súlya, de nincs iránya. Tehát ez azt jelenti, hogy az A csúcsból D-be utazás 10-be fog kerülni és fordítva.

Kétirányú grafikon

A kétirányú és az irányítatlan gráfok közös tulajdonsággal rendelkeznek. Azaz

• Általában az irányítatlan gráfnak lehet egy éle két csúcs között.

Például:

• Itt az A-ból D-be vagy D-ből A-ba költözés 10-be kerül.
• Egy kétirányú gráfban két élünk lehet két csúcs között.

Íme egy példa:

Az utazás A-ból D-be 17-be fog kerülni, míg a D-ből A-ba utazás 12-be fog kerülni. Tehát nem rendelhetünk két különböző súlyt, ha egy irányítatlan gráfról van szó.

Végtelen grafikon

A grafikon végtelen számú élt és csomópontot tartalmaz majd. Ha egy gráf végtelen és egyben összefüggő gráf is, akkor végtelen számú élt is tartalmaz. Itt a kiterjesztett élek azt jelentik, hogy több él kapcsolódhat ezekhez a csomópontokhoz éleken keresztül.

Íme egy példa a végtelen gráfra:

Null Graph

A Null Graph csak csomópontokat vagy csúcsokat tartalmaz, élek nélkül. Ha adott egy G = (V, E) gráf, ahol V csúcsok és E élek, akkor nulla lesz, ha az E élek száma nulla.

Íme egy példa nullgrafikonra:

Triviális grafikon

Egy gráf adatszerkezetet triviálisnak tekintünk, ha csak egy csúcs vagy csomópont van jelen élek nélkül.

Íme egy példa egy triviális grafikonra:

Multi Graph

A gráfot multigráfnak nevezzük, ha két csúcs között több él van, vagy a csúcsnak van egy hurokja. A „Loop” kifejezés a Graph Data Structure-ban olyan élt jelent, amely ugyanarra a csomópontra vagy csúcsra mutat. A multigráf lehet irányított vagy irányítatlan.

Íme egy példa több grafikonra:

Két él van B-től A-ig. Ezenkívül az E csúcsnak van egy önhurokja. A fenti gráf egy irányított gráf, az éleken nincs súlyozás.

Teljes grafikon

A gráf akkor teljes, ha minden csúcsnak vannak irányított vagy irányítatlan élei az összes többi csúcstal.

Tegyük fel, hogy összesen V számú csúcs van, és minden csúcsnak pontosan V-1 éle van. Ezután ezt a grafikont teljes gráfnak nevezzük. Az ilyen típusú gráfokban minden csúcs éleken keresztül kapcsolódik az összes többi csúcshoz.

Íme egy példa egy öt csúcsból álló teljes gráfra:

A képen látható, hogy a csomópontok száma összesen öt, és mindegyik csomópontnak pontosan négy éle van.

Összekapcsolt grafikon

Egy gráfot összekapcsolt gráfnak nevezünk, ha egy csomópontból vagy csúcsból indulunk ki, és az összes csomópontot a kezdő csomóponttól utazzuk. Ehhez legalább egy élnek kell lennie minden csomópont- vagy csúcspár között.

Íme egy példa egy összekapcsolt grafikonra:

Íme néhány magyarázat a fenti „teljes grafikonpélda” grafikonhoz:

• Feltételezve, hogy nincs él C és F között, nem tudunk A-ból G-be utazni. A C-F él azonban lehetővé teszi, hogy egy adott csomópontból bármely csomópontra utazzunk.
• A teljes gráf egy Connected Graph, mert az adott gráf egyik csomópontjáról bármely másik csomópontra át tudunk lépni.

Ciklikus grafikon

Egy gráfot ciklikusnak nevezünk, ha egy vagy több ciklus van jelen a grafikonon.

Íme egy példa a ciklikus grafikonra:

Itt az A, B és C csúcsok ciklust alkotnak.

Egy gráfban több ciklus is lehet.

Irányított aciklikus gráf (DAG)

Egy gráfot irányított aciklikus gráfnak vagy DAG-nak nevezünk, ha a grafikonon belül nincsenek ciklusok. A DAG fontos a Topológiai rendezés vagy a végrehajtási parancs megtalálása. A DAG az ütemezési rendszerek létrehozásához vagy az erőforrások függőségének vizsgálatához stb. is fontos. A fenti grafikon azonban nem tartalmaz ciklust.

Íme egy egyszerű példa egy irányított aciklikus gráfra (DAG):

Ciklusgrafikon

A Cycle Graph nem ugyanaz, mint a ciklikus gráf. A Cycle Graph-ban minden csomópontnak pontosan két éle lesz összekapcsolva, ami azt jelenti, hogy minden csomópontnak pontosan két foka lesz.

Íme egy példa a ciklusdiagramra:

Bipartite Graph

Ilyen grafikonok A gráfok speciális fajtái, ahol a csúcsok két halmazhoz vannak hozzárendelve.

A kétoldalú gráfnak követnie kell a következő szabályt:

• A csúcsok két halmazának külön kell lennie, ami azt jelenti, hogy az összes csúcsot két csoportra vagy halmazra kell osztani.
• Ugyanaz a halmaz A csúcsok nem alkothatnak éleket.

Euler gráf

A gráf adatstruktúrákat akkor tekintjük Euler gráfnak, ha minden csúcsnak páros fokozata van. A csúcsok foka kifejezés egy adott csúcsra mutató vagy onnan mutató élek számát jelenti.

Íme egy példa egy Euler-gráfra:

Minden csúcsnak páros foka van. Az A, D, E és H csúcsnak két foka van. Itt a C csomópont négy fokos, ami páros.

Hamilton grafikon

A Hamilton Graph egy Connect Graph, ahol egy adott csúcs összes csúcsát meglátogathatja anélkül, hogy újra meg kellene látogatnia ugyanazt a csomópontot vagy ugyanazt az élt. Ez a fajta összekapcsolt gráf a „Hamilton-gráf” néven ismert. Az az útvonal, amelyet meglátogat annak ellenőrzésére, hogy az adott gráf Hamilton-gráf-e vagy sem, Hamilton-görbe néven ismert.

Íme egy egyszerű grafikonpélda Hamiltonról:

Ezen a képen a fenti grafikon bármely csomópontjáról meglátogathatjuk az összes csúcsot. Az egyik út lehet ADCHBE. Lehet találni egy Hamilton-ciklust is. A Hamilton-ciklus ugyanabban a csúcsban kezdődik és végződik. Tehát a Hamilton-ciklus lesz ADCHBEA.