Adatszerkezetek 101: Grafikonok - vizuális bevezetés kezdőknek

Ismerje meg a mindennap használt adatstruktúrákat

? Üdvözlünk! Kezdjük néhány létfontosságú kontextussal. Hadd kérdezzek valamit:

✅ Használja a Google keresést?

✅ Használja a Google Maps szolgáltatást?

✅ Használsz közösségi oldalakat?

Ha ezekre a kérdésekre igen a válaszod, akkor feltétlenül használtál grafikonokat, és nem is tudtad! Meglepődött? ? én is voltam! Ez a cikk vizuális bevezetést nyújt a grafikonok világához, azok céljához, elemeihez és típusaihoz.

Ezek az adatstruktúrák csodálatos képességeik miatt igazán felkeltették a figyelmemet. Olyan nagy teljesítményűek, hogy el sem tudja képzelni, mennyire változatosak lehetnek a valós alkalmazások. Kezdjük! ?

? Valós alkalmazások - a varázslat megkezdődik!

A grafikonokat különböző iparágakban és területeken használják:

  • A GPS-rendszerek és a Google Maps grafikonok segítségével találják meg a legrövidebb utat az egyik úti céltól a másikig.
  • A közösségi hálózatok grafikonok segítségével ábrázolják a felhasználók közötti kapcsolatokat.
  • A Google Search algoritmus grafikonok segítségével határozza meg a keresési eredmények relevanciáját.
  • Az Operations Research olyan terület, amely grafikonok segítségével megtalálja az optimális utat az áruk és szolgáltatások szállításának, szállításának költségeinek csökkentésére.
  • Még a Kémia is használ grafikonokatmolekulák képviseletére !!! ❤️

Alkalmazásaik csodálatosak, igaz?

Kezdjük utazásunkat ezen a világon! ?

? Ismerje meg a grafikonokat!

Most, hogy van valamilyen kontextusod, kezdjük azzal, hogy beszéljünk azok fő céljáról és elemeiről.

A grafikonok az elemek (házak, repülőterek, helyszínek, felhasználók, cikkek stb.) Közötti kapcsolatok ábrázolására, megkeresésére, elemzésére és optimalizálására szolgálnak.

Ez egy példa a grafikon megjelenésére:

? Építőelemek

Biztos vagyok benne, hogy a fenti ábrán két fő elemre figyelt fel: körök és vastag vonalak összekötik őket. Csomópontoknak és éleknek hívják őket .

Lássuk őket részletesebben! ?

  • Csomópontok: ők a elemet , hogy hozzon létre a hálózaton. Képviselhetik a házakat, helyszíneket, repülőtereket, kikötőket, buszmegállókat, épületeket, felhasználókat, alapvetően bármit, amelyet képviselhet, mint a hálózat más hasonló elemeivel.
  • Élek: ezek a csomópontok közötti kapcsolatok . Ezek képviselhetik az utcákat, járatokat, autóbusz útvonalakat, a közösségi háló két felhasználó közötti kapcsolatot, vagy bármit, ami esetleg kapcsolatot jelenthet a csomópontok között abban az összefüggésben, amellyel Ön dolgozik.

? Mi történik, ha nincs kapcsolat?

Ha két csomópontot nem köt össze egy él, ez azt jelenti, hogy nincs közvetlen kapcsolat közöttük. De ne ess pánikba! ? Előfordulhat, hogy továbbra is képes az egyik csomópontról a másikra haladni egy sor él megadásával , hasonlóan ahhoz, mintha több utcán haladna végső úti céljához. ?️ ? ?

Például az alábbi ábrán annak ellenére, hogy nincs közvetlen kapcsolat ( él ) a lila csomópont (bal oldalon) és a sárga csomóponton (jobb oldalon), a lila csomóponttól a narancssárga csomópontig, a rózsaszínű csomópontig lehet menni, a zöld csomópontig, és végül eléri a sárga csomópontot. ?

Ez a grafikonok egyik kulcsfontosságú eleme, amelyet a rendelkezésre álló utak követésével kereshet a keresett elemre.

? Jelölés és terminológia

Nagyon fontos megtanulni a hivatalos „nyelvet” a grafikonok használatához:

  • |V|= A csúcsok ( csomópontok ) teljes száma a grafikonon.
  • |E|= A kapcsolatok ( élek ) teljes száma a grafikonon.

Az alábbi példában, |V| = 6mert hat csomópont (kör) és

|E| = 7mert hét él (vonal) van.

? Grafikonok típusai

A grafikonokat éleik (kapcsolataik) jellemzői alapján osztályozzuk. Nézzük meg őket részletesen! ?

1️⃣ Irányított grafikonok

Az irányított gráfokban az éleknek van irányuk. Egyik csomópontról a másikra mennek, és ezen az élen keresztül nincs mód visszatérni a kezdeti csomópontra.

Amint az alábbi ábrán látható, az élek (csatlakozások) nyilakkal rendelkeznek, amelyek egy adott irányra mutatnak. Gondoljon ezekre az élekre, mint egyirányú utcákra. Mehet egy irányba, és elérheti célját, de nem térhet vissza ugyanazon az utcán, ezért alternatív utat kell találnia.

? Például, ha létrehozunk egy grafikont egy pizzafutárhoz, amely egy várost képvisel, két házat (csomópontot) összekapcsolhat egyirányú utca (perem). Ezen az utcán keresztül eljuthat az A házból a B házba, de nem mehet vissza, így alternatív utat kell választania.

? Megjegyzés: Egy irányított gráfban előfordulhat, hogy egyáltalán nem tud visszatérni a kezdeti helyre , ha nincs megfelelő irányú útvonal. ? Az alábbi ábrán láthatja, hogy sikeresen léphet a lila csomópontból a zöld csomópontba, de vegye észre, hogy a zöld csomópontból a lila csomópontba nincs lehetőség visszatérni, mert az élek „egyirányú utcák. ”

2️⃣ Irányítatlan grafikonok

Ebben a típusú gráfban az élek irányítatlanok (nincs külön irányuk). Gondoljon az irányítatlan élekre, mint kétirányú utcákra. Mehet egyik csomópontról a másikra, és visszatérhet ugyanazon az „ösvényen”.

? Megjegyzés: Ha egy grafikon diagramját látja, ahol az élek nem rendelkeznek egy adott irányba mutató nyilakkal, akkor feltételezhetjük, hogy a grafikon irányítatlan.

? A pizzafutárunk számára ez azt jelentené, hogy a motorkerékpár a forrástól a célig ugyanazon az utcán vagy ösvényen haladhat (megkönnyebbülésükre! ?).

Az alábbi grafikonon a lila csomópontból a zöld csomópontba léphet , és ugyanazon az úton haladhat vissza , így nem ér el olyan pontot, amely nem tér vissza. ?

? Súlyok? - Igen, Súlyok!

1️⃣ Súlyozott grafikonok

Súlyozott grafikonokban minden élhez tartozik egy érték (ezt nevezzük súlynak) . Ez az érték egy bizonyos számszerűsíthető kapcsolat képviseletére szolgál az általuk összekapcsolt csomópontok között.

Például a súlyok képviselhetik a távolságot, az időt, a közösségi hálózaton két felhasználó között megosztott kapcsolatok számát, vagy bármit, ami felhasználható a csomópontok közötti kapcsolat leírására abban az összefüggésben, amellyel Ön dolgozik.

Ezeket a súlyokat használja a Dijkstra algoritmusa az útvonalak optimalizálására a hálózat legrövidebb vagy legolcsóbb útvonalainak megtalálásával. (Figyeljen egy cikkre Dijkstra algoritmusáról! ?).

2️⃣ Súlyozatlan grafikonok

Ezzel szemben a súlyozatlan grafikonok éleihez nincs társítva súly. Az ilyen típusú grafikonokra példa található a közösségi hálózatokban, ahol az élek két felhasználó közötti kapcsolatot jelentenek. A kapcsolat nem számszerűsíthető. Ezért az élnek nincs súlya.

? Megjegyzés: Észrevehette, hogy eddig grafikonjainknak csak egy éle köti össze az egyes csomópárokat . Természetes megkérdezni, hogy lehet-e egynél több él egy pár csomópont között. A ctually, ez lehetséges M ultigraphs! T hé lehet több összekötő élek azonos pár csomópont.

? Élek száma! - Fontos tényező

Nagyon fontos tudni, hogy egy grafikonnak sok vagy kevés éle van-e, mert ez döntő tényező annak eldöntésében, hogy hogyan jeleníti meg ezt az adatszerkezetet a kódjában. Lássuk a különböző típusokat! ?

1️⃣ Sűrű grafikonok

A sűrű grafikonoknak sok élük van. De várj! ⚠️ Tudom, mire gondolsz, hogyan határozhatod meg, hogy mi minősül „sok élnek”? Ez egy kicsit túl szubjektív, igaz? ? Egyetértek veled, ezért számszerűsítsük egy kicsit:

? Keressük meg az élek maximális számát egy irányított gráfban. Ha vannak |V|irányított gráfban csomópontok (az alábbi példában hat csomópont), ez azt jelenti, hogy mindegyik csomópontnak legfeljebb |v|kapcsolatai lehetnek (az alábbi példában hat kapcsolat).

Miért? Mivel minden csomópont potenciálisan kapcsolódhat az összes többi csomóponthoz és önmagához (lásd alább a „hurok” részt) . Ezért, a maximális számát élek, hogy a gráf lehet az|V|*|V| , amely az összes csomópontok száma szorozva a kapcsolatok maximális számát, hogy minden csomópont lehet.

Amikor a grafikon éleinek száma közel van az élek maximális számához, a grafikon sűrű. ?

? Megjegyzés: A „hurkok” akkor fordulnak elő, amikor egy csomópontnak van egy éle, amely összeköti önmagával. Furcsa és érdekes, igaz? ?

2️⃣ Ritka grafikonok

A ritka grafikonoknak kevés élük van. Amint az alábbi ábrán látható, a csomópontok között nincs sok kapcsolat.

Ha a grafikon éleinek száma lényegesen kevesebb, mint a maximális élek száma, a grafikon ritka. ?

Meet️ Ismerje meg a ciklusokat!

Most nézzünk meg egy létfontosságú fogalmat a grafikonok, ciklusok megértéséhez.

Valószínűleg észrevette, hogy ha a kapcsolatok sorrendjét követi egy grafikonon, találhat egy olyan utat, amely visszavezet ugyanahhoz a csomóponthoz. Ez olyan, mint a „körben járás”, pontosan olyan, mintha a város körül autózna, és olyan utat választana, amely visszavezetne a kezdeti helyre.

A grafikonokban ezeket a „kör alakú” utakat „ciklusoknak” nevezzük. Ezek érvényesek utakat kezdődik és fejeződik be ugyanazon a csomóponton. Például az alábbi ábrán láthatja, hogy ha bármelyik csomópontnál kezdi, akkor az éleket követve visszatérhet ugyanahhoz a csomóponthoz.

A ciklusok nem mindig „elszigeteltek”, mert nagyobb grafikon részei lehetnek. Akkor fedezheti fel őket, ha a keresést egy adott csomóponton kezdi meg, és megtalálja azt az utat, amely visszavezet ugyanahhoz a csomóponthoz.

? Összefoglalva…

  • A grafikonok fantasztikus adatstruktúrák , amelyeket minden nap használ a Google Keresés, a Google Maps, a GPS és a közösségi média segítségével.
  • A kapcsolatokat megosztó elemek ábrázolására szolgálnak .
  • A grafikon elemeit Csomópontoknak , a köztük lévő kapcsolatokat Éleknek nevezzük .
  • A grafikonok akkor irányíthatók, ha széleik meghatározott irányúak, hasonlóak az egyirányú utcákhoz, vagy irányítatlanok, ha széleik nincsenek meghatározott tájolással, hasonlóan a kétirányú utcákhoz.
  • Az élek társíthatnak hozzájuk értéket, úgynevezett súlyt .
  • Ha egy gráfnak sok éle van, sűrű gráfnak nevezzük. Ellenkező esetben, ha kevés éllel rendelkezik, ritka gráfnak hívják .
  • A kapcsolatok sora ciklust alkothat, ha létrehoz egy olyan utat, amely lehetővé teszi, hogy visszatérjen ugyanahhoz a csomóponthoz.

Tanulja tovább ezeket a csodálatos adatszerkezeteket! Fejlesztőként a jövőd szempontjából teljesen megéri. Most ismerkedem meg az adatstruktúrákkal, és teljesen lenyűgözőnek találom őket. ? ? ❤️

A fontos az, hogy ne hagyjuk abba a kérdezősködést. A kíváncsiságnak megvan a maga oka a létezésre. - Albert Einstein

? Köszönöm!

Nagyon remélem, hogy tetszett a cikkem. ❤️

Kövess engemTwitter. ?