Grafikon adatszerkezet és Algorithms (Példa)

Mi az a grafikon az adatstruktúrában?

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

Valós problémák megoldására használják, például a célállomáshoz vezető legjobb útvonal, valamint a telekommunikációs és közösségi hálózatok útvonalának megtalálására. A felhasználókat a gráfban csomópontnak tekintik, a vezetékek pedig a felhasználókat összekötő élek.

Ha az éleket E-vel, a csúcsokat pedig V-vel ábrázoljuk, akkor a G gráf csúcsok és élek halmazaként írható fel, mint pl. G (V, E).

Példa grafikonra az adatszerkezetben

Íme egy egyszerű példa egy gráf adatszerkezetre:

Ez egy egyszerű irányítatlan gráf (egyfajta gráf). Itt a csúcsok halmaza: {A, B, C, D, E, F}. Két csúcs egy élt alkot. Például A és B egy éllel vannak összekötve. Azonban A és F nincsenek összekötve egyetlen éllel sem.

Grafikonok terminológiái az adatstruktúrában

Az alábbiakban néhány fontos kifejezést találunk, amelyeket a gráf adatszerkezetében használunk:

kifejezés	Leírás
Csúcs	Minden adatelemet csúcsnak vagy csomópontnak nevezünk. A fenti képen A, B, C, D és E a csúcspontok.
Él (ív)	Két csomópont vagy csúcspont közötti összekötő elemeket élnek (ívnek) nevezzük. Két vége van, és a következőképpen ábrázoljuk: (kezdőCsúcs, záróCsúcs).
Irányítatlan él	Ez egy kétirányú él.
Rendezte Edge	Ez egy egyirányú él.
Súlyozott él	Egy értékkel rendelkező él.
Fok	Egy gráfban a csúcshoz kapcsolódó élek számát fokszámnak nevezzük.
Indegree	Egy csúcshoz kapcsolódó bejövő élek száma.
Fokozaton kívüli	Egy csúcshoz kapcsolódó kimenő élek száma.
Önhurok	Egy élt önhuroknak nevezünk, ha két végpontja egybeesik.
Szomszédosság	A csúcsokat szomszédosnak nevezzük, ha egy él összeköti őket.

Grafikonok típusai az adatstruktúrában

Íme a leggyakoribbak listája grafikonok típusai az adatstruktúrában:

• Irányított grafikon
• Irányítatlan gráf
• Súlyozott grafikon
• Kétirányú grafikon
• Végtelen grafikon
• Null Graph
• Triviális grafikon
• Multi Graph
• Teljes grafikon
• Összekapcsolt grafikon
• Ciklikus grafikon
• Irányított aciklikus gráf (DAG)
• Ciklusgrafikon
• Bipartite Graph
• Euler gráf
• Hamilton grafikon

Hogyan ábrázoljunk egy gráfot az adatszerkezetben?

Egy gráfot általában kétféle reprezentáció egyikével tárolunk a memóriában. A választás befolyásolja, hogy a gráf mennyi memóriát használ, és milyen gyorsan futnak a gyakori műveletek.

• Szomszédsági mátrix: Egy kétdimenziós V × V tömb, ahol az [i][j] cella értéke 1 (vagy az él súlya), ha az i és a j csúcs között él van, egyébként pedig 0. Lehetővé teszi az O(1) élkeresést, de O(V²) teret használ, így sűrű gráfokhoz a legalkalmasabb.
• Szomszédsági lista: Listákból álló tömb, ahol minden csúcs a szomszédos csúcsainak listáját tárolja. O(V + E) teret használ, és hatékony ritka gráfok esetén, ezért a legtöbb valós gráf ezt használja.

Ezekről bővebben olvashatsz a egy gráf szomszédsági listája és mátrixreprezentációja tutorial.

A gráf adatstruktúra alkalmazásai

Egy gráfnak számos felhasználási esete van. Sok algoritmus használ gráfokat. Íme a gráf néhány alkalmazása:

• Google A Térképek grafikonokat használ két út kereszteződésének megtalálásához és két hely közötti távolság kiszámításához. Például dijkstra, a forrás- és célhely közötti legrövidebb távolság megtalálásához.
• A Facebook gráfokat használ a felhasználók közös ismerőseinek megkereséséhez. Az algoritmus minden felhasználót egy gráf csomópontjának tekint.
• Az erőforrás-elosztáshoz DAG-ot (Directed Acyclic Graph) használnak. Ez ellenőrzi az erőforrások függőségét.
• Az Google A keresőmotorok grafikonokat használnak a weboldalak rangsorolásához.
• Egy térképping Az eszköz gráf adatstruktúrát használ.
• A router és a protokollja a Graph segítségével tanulja meg a célállomáshoz vezető utat.

GYIK