Bevezetés az adatszerkezet grafikonjába
A grafikonok nemlineáris adatstruktúrák, amelyek véges csomópontok és élek halmazát tartalmazzák. A csomópontok az elemek, és az élek összekötött párkapcsolatban vannak a csomópontok között.
Vegye figyelembe a nemlineáris szót. A nemlineáris adatstruktúra az, amelyben az elemeket nem sorrendben rendezzük el. Például egy tömb egy lineáris adatszerkezet, mivel az elemek egymás után vannak elrendezve. A tömb összes elemét egyetlen lépésben át lehet mozgatni. A nemlineáris adatszerkezetek esetében ez nem igaz. A nemlineáris adatszerkezet elemei többszintűen vannak elrendezve, gyakran hierarchikus mintát követve. A grafikonok nemlineárisak.
A következő szó, amelyre figyelni kell, véges. A gráfot úgy definiáljuk, hogy véges és megszámolható csomópontok száma legyen. Ez egy meglehetősen nem elfogadható kifejezés. Alapvetõen egy gráf végtelen számú csomópontot tartalmazhat, és még mindig véges. Például egy családfa, Ádám és Éva felé kezdve. Ez egy viszonylag végtelen gráf, de még mindig számolható, és ezért végesnek tekinthető.
Valós példa
A grafikonok legjobb példája a való világban a Facebook. A Facebook minden tagja egy csomópont, és élekkel van összekötve. A A barátja B. B a barátja C és így tovább.
terminológia
Az alábbiakban bemutatjuk az adatszerkezet grafikonjának terminológiáit
1. Grafikon ábrázolása: A grafikon általában halmazpár (V, E). V a csúcsok vagy csomópontok halmaza. E az élek halmaza. A fenti példában
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)
2. Csomópont vagy Vertex: A gráf elemei élekkel vannak összekötve.
3. Élek: A görbe két csúcsa közötti út vagy egy vonal.
4. Szomszédos csomópontok: Két csomópontot szomszédosnak hívunk, ha egy szélen keresztül kapcsolódnak. A fenti példában az A csomópont a B, C és D csomópontokkal szomszédos, de nem az E csomóponttal.
5. Út: Az út két csomópont közötti élek sorozata. Ez lényegében egy keresztezés, amely az egyik csomóponttól kezdődik és egy másikig ér véget. A fenti példában több útvonal van az A csomóponttól az E csomópontig.
(A, E) út = (AB, BE)
VAGY
Út (A, E) = (AC, CD, DE)
VAGY
(A, E) út = (AD, DE)
6. Nem irányított gráf : A nem irányított gráf az, amelyben az élek nem adnak meg egy adott irányt. Az élek kétirányúak.
Példa
Tehát ebben a példában az AC él áthaladhat A-tól C-ig és C-től A-ig. Hasonlóan az összes élhez. A B csomóponttól a C csomópontig vezető út (BA, AC) vagy (BD, DC) lenne.
7. Irányított gráf: Az irányított gráf az, amelyben az élek csak meghatározott irányban haladhatnak át.
Példa
Így ugyanabban a példában a szélek most irányban vannak. A szél csak annak irányában haladhat át. Jelenleg nincs út a B csomóponttól a C csomóponthoz.
8. Súlyozott gráf: A súlyozott gráf az, amelynél az élek a súlyhoz vannak társítva. Ez általában a perem átlépésének költsége.
Példa
Így ugyanabban a példában a széleknek most egy bizonyos súlya van velük társítva. Az A csomópont és az E csomópont között kétféle út lehetséges.
1. út = (AB, BD, DE), 1. súly = 3 + 2 + 5 = 10
2. út = (AC, CD, DE), 2. súly = 1 + 3 + 5 = 9
Nyilvánvaló, hogy az 1. útvonal lenne a jobb, ha a cél az E csomópont elérése az A csomópontról a minimális költséggel.
Alapvető műveletek a grafikonon
Az alábbiakban bemutatjuk a Grafikon alapvető műveleteit
1. Adja hozzá / távolítsa el a Vertex-et
Ez a grafikon legegyszerűbb művelete. Egyszerűen hozzáad egy csúcsot a grafikonhoz. Nem kell egy élen keresztül más csúcshoz csatlakoztatni. A csúcs eltávolításakor el kell távolítania az összes élt, amely a törölt csúcsból származik és azzal végződik.
2. Add / Remove Edge
Ez a művelet hozzáad egy szélt két csúcs között. Ha egy csúcsból származó és egy végén végződő összes szélt törölnek, akkor a csúcs izolált csúcsgá válik.
3. Szélesség-első keresés (BFS)
Ez egy grafikonon keresztüli művelet. A BFS vízszintesen halad a grafikonon. Ez azt jelenti, hogy az összes csomópontot egyetlen szinten halad át, mielőtt tovább lépne a következő szintre.
A BFS algoritmus a grafikon első csomópontjának tetején kezdődik, majd az összes szomszédos csomópont felé halad. Miután az összes szomszédos csomópont átkerült, az algoritmus ugyanazt az eljárást megismétli a gyermek csomópontokra.
Példa
A fenti gráf BFS-módon történő áthaladása A -> B -> C -> D -> E -> F -> G. eredményekből származik. Az algoritmus az A csomóponttól indul, és áthalad minden szomszédos B, C és D csomóponton. mind a négy csomópont meglátogatottként. Miután az A szomszédos összes csomópontja átkerült, az algoritmus az A első szomszédos csomópontjára mozog, és megismétli ugyanezt az eljárást. Ebben az esetben a csomópont B és a szomszédos B csomópontok E és F. Ezután a szomszédos C csomópontok áthaladnak. Az összes csomópont megkeresése után a művelet befejeződik.
4. Mélység első keresése (DFS)
A Depth First Search vagy a DFS függőlegesen halad a grafikonon. A gyökér csomóponttal vagy a gráf első csomópontjával kezdődik, és áthalad az összes gyermek csomóponton, mielőtt a szomszédos csomópontokhoz lép.
Példa
A fenti gráf BFS-módon történő áthaladása az A -> B -> E -> F -> C -> G -> D. eredményeképpen alakul ki. Az algoritmus az A csomóponttól indul, és áthalad minden gyermek csomópontján. Amint a B-vel találkozik, úgy tűnik, hogy további gyermekcsomópontjai vannak. Tehát a B gyermekcsomópontjai átkerülnek, mielőtt tovább lépnének az A következő gyermekcsomópontjához.
Grafikonok valós megvalósítása
- Villamos áramkörök tervezése az energiaátvitelhez.
- Összekapcsolt számítógépek hálózatának tervezése.
- Bármely anyag, például humán DNS molekuláris, kémiai és sejtszerkezetének tanulmányozása.
- Városok és városok közötti közlekedési útvonalak tervezése.
Következtetés - ábra az adatszerkezetben
A grafikonok nagyon hasznos fogalom az adatszerkezetekben. Szinte minden területen gyakorlati megvalósításokkal rendelkezik. Nagyon fontos megérteni a grafikonelmélet alapjait, fejleszteni a grafikonszerkezet algoritmusait.
Ez a cikk csupán bevezetés volt a grafikonokba. Ez csak egy lépcső. Ajánlott tovább mélyedni a grafikonelmélet témájában.
Ajánlott cikkek
Ez az útmutató az adatszerkezet grafikonjára. Itt tárgyaljuk a grafikon terminológiáit és alapvető műveleteit az adatszerkezetben. A következő cikkben további információkat is megnézhet -
- Az adatszerkezet interjúval kapcsolatos kérdései
- Adatmodell Cassandra-ban
- Mi az Data Mart?
- Mi az adattudós?