Efektyviam programuotojui reikia gerai išmanyti duomenų struktūras ir algoritmus. Techniniai pokalbiai dažnai patikrins jūsų problemų sprendimo ir kritinio mąstymo įgūdžius.

Grafikai yra viena iš daugelio svarbių duomenų struktūrų programuojant. Daugeliu atvejų suprasti grafikus ir išspręsti grafikais pagrįstas problemas nėra lengva.

Kas yra grafikas ir ką apie jį reikia žinoti?

Kas yra Grafas?

Grafas yra nelinijinė duomenų struktūra, turinti mazgus (arba viršūnes) su juos jungiančiomis briaunomis. Visi medžiai yra grafikų potipiai, bet ne visi grafikai yra medžiai, o grafikas yra duomenų struktūra, iš kurios atsirado medžiai.

Nors tu gali kurti duomenų struktūras JavaScript ir kitomis kalbomis, grafiką galite įgyvendinti įvairiais būdais. Populiariausi metodai yra krašto sąrašai, gretimybių sąrašus, ir gretimybių matricos.

The „Khan Academy“ grafikų vaizdavimo vadovas yra puikus šaltinis norint sužinoti, kaip pavaizduoti grafiką.

Yra daug skirtingų grafikų tipų. Vienas bendras skirtumas yra tarp

instagram viewer
nukreiptas ir nerežisuotas Grafikai; tai dažnai kyla koduojant ir naudojant realiame gyvenime.

Grafų tipai

  1. Nukreiptas grafikas: Grafas, kuriame visos briaunos turi kryptį, dar vadinamas dvikalbis.
  2. Nenukreiptas grafikas: Nenukreiptas grafikas taip pat žinomas kaip dvipusis grafikas. Nenukreiptuose grafikuose briaunų kryptis nesvarbi, o perėjimas gali vykti bet kuria kryptimi.
  3. Svertinis grafikas: Svertinis grafikas yra grafikas, kurio mazgai ir briaunos turi susietą reikšmę. Daugeliu atvejų ši vertė parodo šio mazgo ar krašto tyrinėjimo išlaidas.
  4. Baigtinis grafikas: Grafas, turintis baigtinį mazgų ir briaunų skaičių.
  5. Begalinis grafikas: Grafas, turintis begalinį mazgų ir briaunų skaičių.
  6. Trivialus grafikas: Grafas, kuriame yra tik vienas mazgas ir nėra krašto.
  7. Paprastas grafikas: Kai tik viena briauna jungia kiekvieną grafo mazgų porą, tai vadinama paprastu grafiku.
  8. Nulinis grafikas: Nulinis grafikas yra grafikas, neturintis kraštinių, jungiančių jo mazgus.
  9. Multigrafas: Multigrafe bent pora mazgų turi daugiau nei vieną kraštą, jungiantį juos. Multigrafuose savaiminių kilpų nėra.
  10. Pilnas grafikas: Pilnas grafikas yra grafikas, kuriame kiekvienas mazgas jungiasi su kiekvienu kitu grafiko mazgu. Jis taip pat žinomas kaip a pilnas grafikas.
  11. Pseudo grafikas: Grafas, turintis saviciklą, išskyrus kitas grafo briaunas, vadinamas pseudografu.
  12. Įprastas grafikas: Įprastas grafikas yra grafikas, kuriame visi mazgai turi vienodus laipsnius; y., kiekvienas mazgas turi tiek pat kaimynų.
  13. Susietas grafikas: Sujungtas grafikas yra tiesiog bet koks grafikas, kuriame jungiasi bet kurie du mazgai; y., grafikas su bent vienu keliu tarp kiekvienų dviejų grafo mazgų.
  14. Atjungtas grafikas: Atjungtas grafikas yra tiesioginė sujungto grafo priešingybė. Atjungtame grafe nėra briaunų, jungiančių grafo mazgus, pavyzdžiui, a nulinis grafiką.
  15. Ciklinis grafikas: Ciklinis grafikas yra grafikas, turintis bent vieną grafiko ciklą (kelias, kuris baigiasi ten, kur jis prasidėjo).
  16. Aciklinis grafikas: Aciklinis grafikas yra grafikas be ciklų. Jis gali būti nukreiptas arba nerežisuotas.
  17. Subgrafas: Pografas yra išvestinis grafikas. Tai grafikas, sudarytas iš mazgų ir briaunų, kurie yra kito grafo poaibiai.

A kilpa grafe yra briauna, kuri prasideda nuo mazgo ir baigiasi tame pačiame mazge. Todėl a savęs kilpa yra kilpa tik per vieną grafo mazgą, kaip matyti pseudografike.

Grafiko apėjimo algoritmai

Kadangi tai yra netiesinės duomenų struktūros tipas, grafiką eiti yra gana sudėtinga. Pereiti grafiką reiškia pereiti ir ištirti kiekvieną mazgą, nes yra tinkamas kelias per kraštus. Grafikų perėjimo algoritmai daugiausia yra dviejų tipų.

  1. Pirmoji paieška (BFS): Pirmoji paieška yra grafiko perėjimo algoritmas, kuris aplanko grafiko mazgą ir tyrinėja jo kaimynus, prieš pereidamas prie bet kurio antrinio mazgo. Nors galite pradėti eiti grafiką iš bet kurio pasirinkto mazgo, šaknies mazgas dažniausiai yra pageidaujamas atskaitos taškas.
  2. Giluminė paieška (DFS): Tai antrasis pagrindinis grafiko perėjimo algoritmas. Jis aplanko grafiko mazgą ir ištiria antrinius mazgus arba šakas, prieš pereidamas prie kito mazgo, ty pirmiausia gilinasi, o tada platina.

Paieška pagal plotį yra rekomenduojamas algoritmas, siekiant kuo greičiau rasti kelius tarp dviejų mazgų, ypač trumpiausią kelią.

Ieškoti pagal gylį dažniausiai rekomenduojama, kai norite aplankyti kiekvieną grafiko mazgą. Abu važiavimo algoritmai bet kuriuo atveju veikia gerai, tačiau pasirinktais scenarijais vienas gali būti paprastesnis ir labiau optimizuotas nei kitas.

Paprasta iliustracija gali padėti geriau suprasti abu algoritmus. Pagalvokite apie šalies valstybes kaip grafiką ir pabandykite patikrinti, ar dvi valstybės, X ir Y, yra prijungti. Išsamios paieškos gali apeiti beveik visą šalį, to nesuvokiant pakankamai anksti Y yra vos už 2 valstijų X.

Paieškos pagal plotį pranašumas yra tas, kad prieš pereinant prie kito mazgo ji kuo labiau išlaiko artumą dabartiniam mazgui. Jis suras ryšį tarp X ir Y per trumpą laiką, nereikia apžiūrėti visos šalies.

Kitas svarbus skirtumas tarp šių dviejų algoritmų yra jų įgyvendinimas kode. Pirmoji paieška yra iteracinis algoritmas ir naudojasi a eilė, o paieška pagal gylį paprastai įgyvendinama kaip a rekursinis algoritmas kuri išnaudoja krūva.

Žemiau yra pseudokodas, rodantis abiejų algoritmų įgyvendinimą.

Breadth-First Search

bfs (G grafikas, GraphNode šaknis) {
leisti q būti naujas Eilė
// pažymėti šaknį kaip aplankytą
 šaknis.aplankė = tiesa


// pridėti šaknį į eilę
q.eilę(šaknis)
kol (q nėra tuščia) {
leisti current be q.dequeue() // pašalinti priekinį elementą iš eilės
 for (kaimynai n srovės G) {
jeigu (n yrane dar aplankytas) {
// įtraukti į eilę – kad galėtumėte tyrinėti ir jos kaimynus
q.eilę(n)
 n.lankė = tiesa
 }
 }
 }
}

Gylis – pirmoji paieška

dfs (G grafikas, grafinio mazgo šaknis) {
// bazinis atvejis
jeigu (šaknis yra nulinis) grąžinti
// pažymėti šaknį kaip aplankytą
 šaknis.aplankė = tiesa
už (kaimynai n iš šaknies G)
jeigu (n yrane dar lankėsi)
 dfs (G, n) // rekursinis skambutis
}

Keletas kitų grafiko apėjimo algoritmų gaunami iš paieškų pagal plotį ir gylį. Populiariausi yra šie:

  • Dviejų krypčių paieška: Šis algoritmas yra optimizuotas būdas rasti trumpiausią kelią tarp dviejų mazgų. Jis naudoja dvi paieškas pagal plotį, kurios susiduria, jei yra kelias.
  • Topologinis rūšiavimas: Tai naudojama nukreipti grafikai rūšiuoti mazgus norima tvarka. Negalite taikyti topologinio rūšiavimo nenukreiptiems grafikams arba grafikams su ciklais.
  • Dijkstra algoritmas: Tai taip pat yra BFS tipas. Jis taip pat naudojamas norint rasti trumpiausią kelią tarp dviejų a mazgų svertinis nukreiptas grafikas, kurie gali turėti ciklų arba ne.

Įprasti interviu klausimai, pagrįsti grafikais

Grafikai yra vieni iš svarbiausių duomenų struktūras, kurias turėtų žinoti kiekvienas programuotojas. Techniniuose pokalbiuose dažnai kyla klausimų šia tema ir galite susidurti su klasikinėmis su tema susijusiomis problemomis. Tai apima tokius dalykus kaip „miesto teisėjas“, „salų skaičius“ ir „keliaujančio pardavėjo“ problemos.

Tai tik kelios iš daugelio populiarių grafikais pagrįstų interviu problemų. Galite juos išbandyti LeetCode, HackerRank, arba GeeksforGeeks.

Grafinių duomenų struktūrų ir algoritmų supratimas

Grafikai naudingi ne tik atliekant techninius pokalbius. Jie taip pat turi realių naudojimo atvejų, pvz., in tinklai, žemėlapiai, ir oro linijų sistemos maršrutams rasti. Jie taip pat naudojami pagrindinėje kompiuterinių sistemų logikoje.

Grafikai puikiai tinka duomenims tvarkyti ir padėti mums vizualizuoti sudėtingas problemas. Tačiau diagramos turėtų būti naudojamos tik tada, kai tai absoliučiai būtina, kad būtų išvengta vietos sudėtingumo ar atminties problemų.