Grafikonok típusai az adatszerkezetben példákkal
Sarah Chen
⚡ Okos összefoglaló
Az adatszerkezeti gráfok csúcsok és élek nemlineáris gyűjteményei, amelyeket a szerkezet alapján családokba sorolunk, például irányított, irányítatlan, súlyozott, ciklikus, aciklikus, teljes, összefüggő, kétoldalas, Euler- és Hamilton-gráfok.
A gráf egy nemlineáris adatstruktúra, amely csúcsokból és élekből áll. A csúcsok tartalmazzák az információt vagy adatot, az élek pedig összekötő kapocsként működnek a csúcspárok között.
A gráfok többféle típusúak lehetnek, a csomópontok és élek helyzetétől függően. Íme néhány fontos gráftípus:
Irányított grafikon
Az irányított gráf élei nyilakat tartalmaznak, amelyek az irányt jelzik. A nyíl határozza meg, hogy hová mutat az él, vagy hová végződik. Íme egy példa az irányított gráfra.
Irányított grafikon
- Mehetünk A csomópontból D-be.
- Azonban nem tudunk a D csomópontból az A csomópontba menni, 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
Egy irányítatlan gráf mutatók nélküli éleket tartalmaz. Ez azt jelenti, hogy két csúcs között fordítva is utazhatunk. Íme egy egyszerű példa az irányítatlan gráfra.
Irányítatlan gráf
A fenti grafikonon
- El tudunk jutni A-ból B-be.
- B-ből A-ba is el tudunk jutni.
- 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
Egy olyan gráfot, amelynek élein súlyok vagy költségek vannak, súlyozott gráfnak nevezünk. A numerikus érték általában az egyik csúcsból a másik csúcsba való mozgatás költségét jelöli. Mind az irányított, mind az irányítatlan gráfok élein lehetnek súlyok. Íme egy példa egy súlyozott gráfra (irányított).
Irányított grafikon súllyal
- A-ból B-be haladva van egy előny, és a súly 5, ami azt jelenti, hogy az A-ból B-be való átállás 5-be fog kerülni.
- A pont B-re mutat, de ebben a gráfban B-nek nincs közvetlen éle A felett. Tehát nem tudunk B-ből A-ba utazni.
- Ha azonban A-ból F-be szeretnénk lépni, több útvonal is létezik. Ezek az ADF és az ABF útvonalak. Az ADF ára (10+11), azaz 21.
- Itt az ABF út (5+15) vagyis 20-ba fog kerülni. Itt összeadjuk az út minden élének súlyát.
Íme egy példa egy súlyokkal ellátott irányítatlan gráfra:
Irányítatlan grafikon súllyal
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áfoknak van egy közös tulajdonságuk. Ez a következő:
- Általában egy 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:
Kétirányú grafikon
Az A-ból D-be való utazás 17-be, de a D-ből A-ba való utazás 12-be kerül. Tehát nem rendelhetünk két különböző súlyt, ha irányítatlan gráfról van szó.
Végtelen grafikon
A gráf végtelen számú élt és csomópontot tartalmaz. 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 további élek is kapcsolódhatnak ezekhez a csomópontokhoz éleken keresztül. Íme egy példa a végtelen gráfra:
Végtelen grafikon
Null Graph
Egy nullgráf csak csomópontokat vagy csúcsokat tartalmaz, élek nélkül. Ha adott egy G = (V, E) gráf, ahol V a csúcsokat, E pedig az éleket jelöli, akkor null gráf lesz, ha az élek száma E nulla. Íme egy példa egy nullgráfra:
Null Graph
Triviális grafikon
Egy gráf adatszerkezet triviálisnak tekinthető, ha csak egy csúcs vagy csomópont van jelen élek nélkül. Íme egy példa egy triviális gráfra:
Multi Graph
Egy gráfot multigráfnak nevezünk, ha két csúcs között több él van, vagy a csúcs hurokkal rendelkezik. A „hurok” kifejezés a gráf adatstruktúrában olyan élt jelent, amely ugyanarra a csomópontra vagy csúcsra mutat. Egy multigráf lehet irányított vagy irányítatlan. Íme egy példa egy multigráfra:
B-ből A-ba két él vezet. Továbbá az E csúcsnak van egy önhurka. A fenti gráf egy irányított gráf, amelynek nincsenek súlyai az éleken.
Teljes grafikon
Egy gráf teljes, ha minden csúcsnak vannak irányított vagy irányítatlan élei az összes többi csúccsal. Tegyük fel, hogy összesen V számú csúcs van, és minden csúcsnak pontosan V-1 éle van. Ekkor ezt a gráfot teljes gráfnak nevezzük. Az ilyen típusú gráfban minden csúcs éleken keresztül kapcsolódik az összes többi csúccsal. Íme egy példa egy öt csúccsal rendelkező teljes gráfra:
A képen látható, hogy a csomópontok teljes száma öt, és mindegyik csomópontnak pontosan négy éle van.
Összekapcsolt grafikon
Egy gráfot összefüggő gráfnak nevezünk, ha egy csomópontból vagy csúcsból indulunk ki, és onnan el tudunk jutni az összes csomópontba. Ehhez minden csomópont- vagy csúcspár között legalább egy élnek kell lennie. Íme egy példa egy összefüggő gráfra:
Íme a fenti Összefüggő Gráf néhány magyarázata:
- Feltételezve, hogy nincs él C és F között, nem tudunk eljutni A-ból G-be. A C-ből F-be vezető él azonban lehetővé teszi számunkra, hogy egy adott csomópontból bármelyik csomópontba 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 benne. Íme egy példa egy ciklikus gráfra:
Itt az A, B és C csúcsok egy kört alkotnak. Egy gráfban több kör 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 gráfban nincsenek körök. A DAG fontos a következő műveletek végrehajtása során: Topológiai rendezés vagy a végrehajtási sorrend megtalálásához. A DAG fontos az ütemező rendszerek létrehozásához vagy az erőforrások függőségének szkenneléséhez stb. A fenti gráf azonban nem tartalmaz ciklust. Íme egy egyszerű példa egy irányított aciklikus gráfra (DAG):
Ciklusgrafikon
A ciklusgráf nem ugyanaz, mint a ciklikus gráf. Egy ciklusgráfban minden csomópontnak pontosan két összekötött éle van, ami azt jelenti, hogy minden csomópontnak pontosan két fokszáma van. Íme egy példa egy ciklusgráfra:
Bipartite Graph
Ilyen grafikonok olyan speciális gráffajták, ahol a csúcsok két halmazhoz vannak rendelve. Egy páros gráfnak a következő szabályt kell követnie:
- A két csúcshalmaznak különbözőnek kell lennie, ami azt jelenti, hogy az összes csúcsot két csoportra vagy halmazra kell osztani.
- Az azonos halmazú csúcsok nem alkothatnak éleket.
Euler gráf
Egy gráf adatszerkezetet Euler-gráfnak tekintünk, ha minden csúcs fokszáma páros. A csúcsok fokszáma kifejezés egy adott csúcsra mutató vagy onnan kifelé mutató élek számát jelenti. Íme egy példa egy Euler-gráfra:
Minden csúcs páros fokszámú. Az A, D, E és H csúcsoknak két fokszámuk van. Itt a C csomópontnak négy fokszáma van, ami páros.
Hamilton grafikon
A Hamilton-gráf egy összefüggő gráf, ahol egy adott csúcsból származó összes csúcsot meglátogathatjuk anélkül, hogy ugyanazt a csomópontot újra elérnénk, vagy ugyanazt az élt használnánk. Az ilyen típusú összefüggő gráfot „Hamilton-gráfnak” nevezik. Az utat, amelyet annak ellenőrzésére használunk, hogy az adott gráf Hamilton-gráf-e vagy sem, Hamilton-útnak nevezzük. Íme egy egyszerű Hamilton-gráf példa:
Ezen a képen a fenti grafikon bármely csomópontjáról meglátogathatjuk az összes csúcsot. Az egyik út lehet ADCHBEAz is lehetséges, hogy találunk egy Hamilton-ciklust. Egy Hamilton-ciklus ugyanabban a csúcsban kezdődik és végződik. Tehát a Hamilton-ciklus a következő lesz: ADCHBEA.
