Efektīvam programmētājam ir nepieciešama skaidra izpratne par datu struktūrām un algoritmiem. Tehniskās intervijas bieži pārbauda jūsu problēmu risināšanas un kritiskās domāšanas prasmes.

Grafiki ir viena no daudzajām programmēšanas svarīgajām datu struktūrām. Vairumā gadījumu grafiku izpratne un uz grafikiem balstītu problēmu risināšana nav vienkārša.

Kas ir grafiks, un kas jums par to jāzina?

Kas ir grafiks?

Grafiks ir nelineāra datu struktūra, kurai ir mezgli (vai virsotnes) ar malām, kas tos savieno. Visi koki ir grafiku apakštipi, bet ne visi grafiki ir koki, un grafiks ir datu struktūra, no kuras koki ir radušies.

Lai gan jūs varat veidot datu struktūras JavaScript un citās valodās, varat ieviest grafiku dažādos veidos. Populārākās pieejas ir malu saraksti, blakus esošo sarakstu, un blakus esošās matricas.

The Khan Academy ceļvedis grafiku attēlošanai ir lielisks resurss, lai uzzinātu, kā attēlot grafiku.

Ir daudz dažādu grafiku veidu. Viena kopīga atšķirība ir starp režisēts un nerežisēts grafiki; tie bieži rodas kodēšanas izaicinājumos un reālajā dzīvē.

Grafiku veidi

  1. Novirzīts grafiks: Grafiks, kurā visām malām ir virziens, ko dēvē arī par divdabis.
  2. Nevirzīts grafiks: Nevirzītu grafiku sauc arī par divvirzienu grafiku. Nevirzītos grafikos malu virzienam nav nozīmes, un šķērsošana var notikt jebkurā virzienā.
  3. Svērtais grafiks: Svērtais grafiks ir grafiks, kura mezgliem un malām ir saistīta vērtība. Vairumā gadījumu šī vērtība atspoguļo šī mezgla vai malas izpētes izmaksas.
  4. Galīgs grafiks: Grafs, kuram ir ierobežots mezglu un malu skaits.
  5. Bezgalīgs grafiks: Grafs, kurā ir bezgalīgs mezglu un malu skaits.
  6. Triviāls grafiks: Grafiks, kuram ir tikai viens mezgls un nav malas.
  7. Vienkāršs grafiks: Ja katru grafa mezglu pāri savieno tikai viena mala, to sauc par vienkāršu grafiku.
  8. Nulle diagramma: Nulles grafs ir grafs, kuram nav malu, kas savieno tā mezglus.
  9. Multigrāfs: Multigrāfā vismaz mezglu pārim ir vairāk nekā viena mala, kas tos savieno. Multigrāfos nav pašcilpu.
  10. Pilns grafiks: Pilns grafiks ir grafiks, kurā katrs mezgls savienojas ar katru otro grafa mezglu. Tas ir pazīstams arī kā a pilns grafiks.
  11. Pseidografiks: Grafu, kuram ir pašcilpa malā no citām grafa malām, sauc par pseidografu.
  12. Parasts grafiks: Regulārs grafiks ir grafiks, kurā visiem mezgliem ir vienādas pakāpes; i., katram mezglam ir vienāds skaits kaimiņu.
  13. Savienotais grafiks: Savienots grafs ir vienkārši jebkurš grafiks, kurā savienojas jebkuri divi mezgli; i., grafs ar vismaz vienu ceļu starp katriem diviem grafika mezgliem.
  14. Atvienots grafiks: Atvienots grafs ir tieši pretējs savienotam grafikam. Atvienotā grafikā nav malu, kas savienotu diagrammas mezglus, piemēram, a null grafikā.
  15. Cikliskais grafiks: Cikliskais grafiks ir grafiks, kas satur vismaz vienu grafika ciklu (ceļš, kas beidzas tur, kur tas sākās).
  16. Aciklisks grafiks: Aciklisks grafiks ir grafiks bez cikliem. Tas var būt gan virzīts, gan nevirzīts.
  17. Apakšgrafiks: Apakšgrafs ir atvasināts grafiks. Tas ir grafs, kas izveidots no mezgliem un malām, kas ir cita grafika apakškopas.

A cilpa grafikā ir mala, kas sākas no mezgla un beidzas tajā pašā mezglā. Tāpēc a pašcilpa ir cilpa tikai vienā grafa mezglā, kā redzams pseidografikā.

Grafiku šķērsošanas algoritmi

Tā kā ir nelineāras datu struktūras veids, diagrammas šķērsošana ir diezgan sarežģīta. Grafika šķērsošana nozīmē iziet cauri un izpētīt katru mezglu, ņemot vērā, ka caur malām ir derīgs ceļš. Grafu šķērsošanas algoritmi galvenokārt ir divu veidu.

  1. Pirmā meklēšana (BFS): Meklēšana pēc platuma ir grafika šķērsošanas algoritms, kas apmeklē grafika mezglu un izpēta tā kaimiņus, pirms pāriet uz kādu no tā pakārtotajiem mezgliem. Lai gan jūs varat sākt šķērsot grafiku no jebkura atlasītā mezgla, saknes mezgls parasti ir vēlamais sākumpunkts.
  2. Dziļuma pirmā meklēšana (DFS): Šis ir otrs galvenais grafu šķērsošanas algoritms. Tas apmeklē grafika mezglu un izpēta tā atvasinātos mezglus vai zarus, pirms pāriet uz nākamo mezglu, tas ir, vispirms iedziļinoties un pēc tam doties platumā.

Meklēšana pēc platuma ir ieteicamais algoritms, lai pēc iespējas ātrāk atrastu ceļus starp diviem mezgliem, īpaši īsāko ceļu.

Meklēšana pēc dziļuma galvenokārt ir ieteicama, ja vēlaties apmeklēt katru diagrammas mezglu. Abi šķērsošanas algoritmi darbojas labi jebkurā gadījumā, taču atlasītajos scenārijos viens var būt vienkāršāks un optimizētāks nekā otrs.

Vienkārša ilustrācija var palīdzēt labāk izprast abus algoritmus. Padomājiet par valsts štatiem kā grafiku un mēģiniet pārbaudīt, vai divi štati, X un Y, ir savienoti. Padziļināta meklēšana var izvērsties gandrīz visā valstī, to neapzinoties pietiekami agri Y atrodas tikai 2 štatu attālumā no X.

Pirmās platuma meklēšanas priekšrocība ir tāda, ka tā saglabā tuvumu pašreizējam mezglam, cik vien iespējams, pirms došanās uz nākamo. Tas atradīs savienojumu starp X un Y īsā laikā, neizpētot visu valsti.

Vēl viena būtiska atšķirība starp šiem diviem algoritmiem ir veids, kā tie tiek ieviesti kodā. Meklēšana pēc platuma ir iteratīvais algoritms un izmanto a rindā, savukārt pirmā dziļuma meklēšana parasti tiek īstenota kā a rekursīvs algoritms kas piesaista kaudze.

Zemāk ir daži pseidokods, kas parāda abu algoritmu ieviešanu.

Breadth-First Search

bfs (G diagramma, GraphNode sakne) {
ļaut q būt jauns Rinda
// atzīmējiet sakni kā apmeklētu
 sakne.apmeklēts = taisnība


// pievienot rindai sakni
q.rindā(sakne)
kamēr (q nav tukšs) {
ļaut pašreizējais būt q.dequeue() // noņemt rindā priekšējo elementu
 for (strāvas kaimiņi n G) {
ja (n irnē vēl apmeklēts) {
// pievienot rindai - lai jūs varētu izpētīt arī tās kaimiņus
q.rindā(n)
 n.apmeklēja = taisnība
 }
 }
 }
}

Dziļuma pirmā meklēšana

dfs (G diagramma, GraphNode sakne) {
// bāzes gadījums
ja (sakne ir null) atgriezties
// atzīmējiet sakni kā apmeklētu
 sakne.apmeklēts = taisnība
priekš (kaimiņi n no saknes G)
ja (n irnē vēl apmeklēts)
 dfs (G, n) // rekursīvs zvans
}

Dažus citus grafikus apceļošanas algoritmus iegūst, meklējot pēc platuma un pēc dziļuma. Populārākie ir:

  • Divvirzienu meklēšana: Šis algoritms ir optimizēts veids, kā atrast īsāko ceļu starp diviem mezgliem. Tas izmanto divus meklējumus pēc platuma, kas saduras, ja ir ceļš.
  • Topoloģiskā šķirošana: Tas tiek izmantots virzīti grafiki lai sakārtotu mezglus vēlamajā secībā. Topoloģisko kārtošanu nevar lietot nevirzītiem grafikiem vai grafikiem ar cikliem.
  • Dijkstra algoritms: Tas ir arī BFS veids. To izmanto arī, lai atrastu īsāko ceļu starp diviem a mezgliem svērtais virzīts grafiks, kam var būt cikli vai bez tiem.

Bieži uzdotie interviju jautājumi, kuru pamatā ir grafiki

Grafiki ir viens no svarīgākajiem datu struktūras, kas jāzina katram programmētājam. Tehniskajās intervijās bieži rodas jautājumi par šo tēmu, un jūs varat saskarties ar klasiskām problēmām saistībā ar šo tēmu. Tie ietver tādas lietas kā "pilsētas tiesnesis", "salu skaits" un "ceļojošā pārdevēja" problēmas.

Šīs ir tikai dažas no daudzajām populārajām uz grafiku balstītajām interviju problēmām. Jūs varat tos izmēģināt LeetCode, HackerRank, vai GeeksforGeeks.

Grafu datu struktūru un algoritmu izpratne

Grafiki ir noderīgi ne tikai tehniskām intervijām. Viņiem ir arī reālās pasaules lietošanas gadījumi, piemēram, in tīklu veidošana, kartes, un aviokompāniju sistēmas maršrutu meklēšanai. Tos izmanto arī datorsistēmu pamatā esošajā loģikā.

Grafiki ir lieliski piemēroti datu kārtošanai un palīdz mums vizualizēt sarežģītas problēmas. Grafikus vajadzētu izmantot tikai tad, ja tas ir absolūti nepieciešams, lai novērstu vietas sarežģītību vai atmiņas problēmas.