A hatékony programozónak alaposan ismernie kell az adatstruktúrákat és az algoritmusokat. A technikai interjúk gyakran próbára teszik problémamegoldó és kritikus gondolkodási készségeit.
A grafikonok a programozás számos fontos adatszerkezetének egyike. A legtöbb esetben a grafikonok megértése és a gráf alapú problémák megoldása nem megy könnyen.
Mi az a grafikon, és mit kell tudni róla?
Mi az a grafikon?
A gráf egy nemlineáris adatstruktúra, amelynek csomópontjai (vagy csúcsai) vannak és élek, amelyek összekötik őket. Minden fa a gráfok altípusa, de nem minden gráf fa, és a gráf az az adatstruktúra, amelyből a fák származnak.
Bár lehet adatstruktúrákat készítsen JavaScriptben és más nyelveken, különféle módokon valósíthat meg egy grafikont. A legnépszerűbb megközelítések a él listák, szomszédsági listák, és szomszédsági mátrixok.
Az Khan Academy útmutató a grafikonok ábrázolásához nagyszerű forrás a grafikonok ábrázolásának megismeréséhez.
Sokféle grafikon létezik. Egy közös megkülönböztetés van a között
irányította és irányítatlan grafikonok; ezek nagyon gyakran felmerülnek a kódolási kihívásokban és a valós életben.Grafikonok típusai
- Irányított grafikon: Egy gráf, amelyben minden élnek van iránya, más néven kétjegyű mássalhangzó.
- Irányítatlan grafikon: Az irányítatlan gráfot kétirányú gráfnak is nevezik. Irányítatlan gráfokban az élek iránya nem számít, és a bejárás bármely irányba mehet.
- Súlyozott grafikon: A súlyozott gráf olyan gráf, amelynek csomópontjai és élei hozzárendelt értékkel rendelkeznek. A legtöbb esetben ez az érték az adott csomópont vagy él feltárásának költségét jelenti.
- Véges gráf: Egy gráf, amelynek véges számú csomópontja és éle van.
- Végtelen gráf: Egy gráf, amelynek végtelen számú csomópontja és éle van.
- Triviális grafikon: Egy gráf, amelynek csak egy csomópontja van, és nincs él.
- Egyszerű grafikon: Ha egy gráf minden csomópontpárját csak egy él köti össze, azt egyszerű gráfnak nevezzük.
- Null grafikon: A nullgráf olyan gráf, amelynek a csomópontjait nem köti össze él.
- Multigráf: Egy multigráfban legalább egy csomópontpárt egynél több él köti össze. A multigráfokban nincsenek önhurkok.
- Teljes grafikon: A teljes gráf olyan gráf, amelyben minden csomópont a gráf minden másik csomópontjához kapcsolódik. Más néven a teljes grafikon.
- Pszeudo grafikon: Az olyan gráfot, amely a gráf többi élétől eltekintve rendelkezik önhurokkal, pszeudográfnak nevezzük.
- Normál grafikon: A szabályos gráf olyan gráf, ahol minden csomópont azonos fokszámú; azaz minden csomópontnak ugyanannyi szomszédja van.
- Összekapcsolt grafikon: Egy összefüggő gráf egyszerűen bármely gráf, amelyben bármely két csomópont kapcsolódik; azaz egy gráf, amelynek legalább egy útja van a gráf minden két csomópontja között.
- Leválasztott grafikon: A szétkapcsolt gráf az összekapcsolt gráf közvetlen ellentéte. Egy szétválasztott gráfban nincsenek élek, amelyek összekötik a gráf csomópontjait, például a-ban nulla grafikon.
- Ciklikus grafikon: A ciklikus gráf egy olyan gráf, amely legalább egy gráfciklust tartalmaz (egy útvonal, amely ott végződik, ahol elkezdődött).
- Aciklikus grafikon: Az aciklikus gráf olyan gráf, amelyben nincsenek ciklusok. Ez lehet irányított vagy nem irányított.
- Algrafikon: A részgráf egy származtatott gráf. Ez egy olyan csomópontokból és élekből kialakított gráf, amelyek egy másik gráf részhalmazai.
A hurok a gráfban egy él, amely egy csomópontból indul ki és ugyanabban a csomópontban ér véget. Ezért a önhurok egy hurok csak egy gráfcsomóponton, amint az egy pszeudográfon látható.
Grafikon bejárási algoritmusok
Egyfajta nemlineáris adatstruktúra lévén a gráf bejárása meglehetősen körülményes. A gráf bejárása azt jelenti, hogy minden egyes csomóponton áthaladunk és feltárunk egy érvényes útvonalat az éleken. A gráfbejárási algoritmusok főként két típusból állnak.
- Breadth-First Search (BFS): A Breadth-first keresés egy gráfbejárási algoritmus, amely felkeresi a gráfcsomópontot, és feltérképezi annak szomszédait, mielőtt a gyermek csomópontjaira lépne. Bár bármelyik kiválasztott csomópontból elkezdheti a grafikon bejárását, a gyökércsomópont általában az előnyben részesített kiindulási pont.
- Mélységi keresés (DFS): Ez a második fő gráfbejárási algoritmus. Meglátogat egy gráfcsomópontot, és megvizsgálja annak gyermekcsomópontjait vagy ágait, mielőtt a következő csomópontra lépne – vagyis először mélyre megy, mielőtt szélesre lép.
A széleskörű keresés az ajánlott algoritmus, hogy a lehető leggyorsabban megtalálja a két csomópont közötti útvonalat, különösen a legrövidebb utat.
A mélységben történő keresés leginkább akkor javasolt, ha a grafikon minden csomópontját meg szeretné látogatni. Mindkét bejárási algoritmus minden esetben jól működik, de egyes esetekben az egyik egyszerűbb és optimalizáltabb lehet, mint a másik.
Egy egyszerű illusztráció segíthet mindkét algoritmus jobb megértésében. Képzelje el egy ország államait grafikonként, és próbálja meg ellenőrizni, hogy két állam, x és Y, csatlakoztatva vannak. A mélységi kutatás szinte az országot bejárhatja anélkül, hogy ezt elég korán észrevenné Y mindössze 2 államra van tőle x.
A szélességi keresés előnye, hogy a lehető legnagyobb mértékben megőrzi az aktuális csomópont közelségét, mielőtt a következőre lépne. Meg fogja találni a kapcsolatot közöttük x és Y rövid idő alatt anélkül, hogy az egész országot be kellene fedezni.
Egy másik jelentős különbség a két algoritmus között a kódban való megvalósításuk módja. A szélesség-első keresés egy iteratív algoritmus és használja a sorban, míg a mélységi keresés általában úgy valósul meg, mint a rekurzív algoritmus amely kihasználja a Kazal.
Az alábbiakban néhány pszeudokód látható, amely bemutatja mindkét algoritmus megvalósítását.
Breadth-First Search
bfs (G grafikon, GraphNode gyökér) {
hagyja q legyen új Sor// gyökér megjelölése látogatottként
gyökér.látogatott = igaz// root hozzáadása a sorhoz
q.sorba(gyökér)
míg (q nem üres) {
hagyja aktuális legyen q.dequeue() // elülső elem eltávolítása a sorból
for (a G-beli áram n szomszédai) {
ha (n vannem még meglátogatott) {
// hozzáadása a sorhoz – így a szomszédait is felfedezheti
q.sorba(n)
n.látogatott = igaz
}
}
}
}
Mélység-első keresés
dfs (G grafikon, GraphNode gyökér) {
// alap helyzet
ha (a gyökér az nulla) Visszatérés// gyökér megjelölése látogatottként
gyökér.látogatott = igaz
for (G gyökér n szomszédai)
ha (n vannem még meglátogatott)
dfs (G, n) // rekurzív hívás
}
Néhány másik gráfbejárási algoritmus a szélesség-első és mélység-első keresésből származik. A legnépszerűbbek a következők:
- Kétirányú keresés: Ez az algoritmus a két csomópont közötti legrövidebb út megtalálásának optimalizált módja. Két szélességi keresést használ, amelyek ütköznek, ha van útvonal.
- Topológiai rendezés: Ezt használják irányított grafikonok hogy a csomópontokat a kívánt sorrendbe rendezze. Nem alkalmazhat topológiai rendezést irányítatlan vagy ciklusos gráfokra.
- Dijkstra algoritmusa: Ez is egyfajta BFS. Arra is használják, hogy megtalálják a legrövidebb utat a két csomópont között súlyozott irányított gráf, amelyeknek lehetnek ciklusai vagy nincsenek.
Gyakori interjúkérdések grafikonok alapján
A grafikonok a legfontosabbak közé tartoznak adatstruktúrákat minden programozónak ismernie kell. A technikai interjúk során gyakran felmerülnek kérdések ebben a témában, és a témával kapcsolatos klasszikus problémákkal találkozhat. Ilyenek például a „városbíró”, „a szigetek száma” és az „utazó eladó” problémák.
Ez csak néhány a sok népszerű grafikon alapú interjúprobléma közül. Kipróbálhatod őket LeetCode, HackerRank, vagy GeeksforGeeks.
A gráf adatstruktúrák és algoritmusok megértése
A grafikonok nem csak a technikai interjúkhoz hasznosak. Valós felhasználási eseteik is vannak, mint pl hálózatépítés, térképek, és légitársasági rendszerek útvonalak megtalálásához. A számítógépes rendszerek mögöttes logikájában is használják őket.
A grafikonok kiválóan alkalmasak az adatok rendszerezésére és az összetett problémák megjelenítésére. A grafikonokat azonban csak akkor szabad használni, ha feltétlenül szükséges, hogy elkerüljük a hely bonyolultságát vagy a memóriaproblémákat.
