Grafikon adatszerkezet és Algorithms (Példa)
Sarah Chen
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ókat vagy adatokat, az élek pedig összekötőként működnek a csúcspárok között.
Valódi szöveges problémák megoldására szolgál, mint például a célhelyhez vezető legjobb útvonal, valamint a távközlési és közösségi hálózatok útvonalának megtalálása. A felhasználók csomópontnak számítanak a grafikonon, és a vezetékek 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 a grafikon adatszerkezetére:
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 élt hoz létre. Például A és B egy éllel van összekötve. Az A és F azonban egyetlen élhez sem kapcsolódik.
Grafikonok terminológiái az adatstruktúrában
Íme néhány fontos kifejezés, amelyet a grafikon adatszerkezetében használnak:
| kifejezés | Description |
|---|---|
| Csúcs | Minden adatelemet csúcsnak vagy csomópontnak nevezünk. A fenti képen A, B, C, D és E a csúcsok. |
| Él (ív) | A két csomópont vagy csúcs közötti összekötő kapcsolatokat élnek (Arc) nevezzük. Két vége van, és mint (kezdőcsúcs, befejezőcsúcs) ábrázolják. |
| Irányítatlan él | Ez egy kétirányú él. |
| Rendezte Edge | Ez egy egyirányú él. |
| Súlyozott él | Egy él, amelyen érték van. |
| Fok | A Graphban egy csúcshoz kapcsolódó élek számát foknak 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 össze van kötve. |
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
A gráf adatstruktúra alkalmazásai
Egy grafikonnak számos felhasználási esete van. Sok olyan algoritmus létezik, amely sokat használ a grafikonokon. Íme a Graph néhány alkalmazása:
- A Google Térkép grafikonok segítségével keresi meg két út metszéspontját, és kiszámítja a két hely közötti távolságot.
Például, dijkstra, a forrás és a célhely közötti legrövidebb távolság megtalálásához. - A Facebook a Graphs segítségével keresi meg a felhasználók közös barátját. Algoritmusa minden felhasználót egy gráf csomópontjának tekint.
- Az erőforrás-allokációhoz a DAG (Direct Acyclic Graph) használatos. Ellenőrzi az erőforrások függőségét.
- A Google Keresőmotor grafikonokat használ a webhelyek rangsorának létrehozásához.
- A leképezési eszköz a grafikon adatszerkezetét használja.
- router és t protokollja a Graph segítségével tanulja meg a cél útvonal elérési útját.
