Učinkovit programer potrebuje dobro razumevanje podatkovnih struktur in algoritmov. Tehnični razgovori bodo pogosto preizkusili vaše sposobnosti reševanja problemov in kritičnega mišljenja.
Grafi so ena izmed mnogih pomembnih podatkovnih struktur v programiranju. V večini primerov razumevanje grafov in reševanje problemov, ki temeljijo na grafih, ni enostavno.
Kaj je graf in kaj morate vedeti o njem?
Kaj je graf?
Graf je nelinearna podatkovna struktura, ki ima vozlišča (ali oglišča) z robovi, ki jih povezujejo. Vsa drevesa so podvrste grafov, vendar niso vsi grafi drevesa, graf pa je podatkovna struktura, iz katere izvirajo drevesa.
Čeprav lahko graditi podatkovne strukture v JavaScriptu in drugih jezikih, lahko graf implementirate na različne načine. Najbolj priljubljeni pristopi so robni seznami, sosednji seznami, in matrike sosednosti.
The Priročnik Akademije Khan za predstavljanje grafov je odličen vir za učenje o tem, kako predstaviti graf.
Obstaja veliko različnih vrst grafov. Ena pogosta razlika je med
usmeril in neusmerjen grafi; ti se pogosto pojavljajo pri izzivih kodiranja in uporabi v resničnem življenju.Vrste grafov
- Usmerjeni graf: Graf, v katerem imajo vsi robovi smer, imenovan tudi digraf.
- Neusmerjeni graf: Neusmerjeni graf je znan tudi kot dvosmerni graf. V neusmerjenih grafih smer robov ni pomembna, prečkanje pa lahko poteka v katero koli smer.
- Uteženi graf: Uteženi graf je graf, katerega vozlišča in robovi imajo povezano vrednost. V večini primerov ta vrednost predstavlja stroške raziskovanja tega vozlišča ali roba.
- Končni graf: Graf, ki ima končno število vozlišč in robov.
- Neskončni graf: Graf, ki ima neskončno število vozlišč in robov.
- Trivialni graf: Graf, ki ima samo eno vozlišče in nima roba.
- Preprost graf: Če samo en rob povezuje vsak par vozlišč grafa, se imenuje preprost graf.
- Ničelni graf: Ničelni graf je graf, ki nima robov, ki povezujejo njegova vozlišča.
- Multigraf: V multigrafu ima vsaj par vozlišč več kot en rob, ki ju povezuje. V multigrafih ni samozank.
- Celoten graf: Popolni graf je graf, v katerem se vsako vozlišče povezuje z vsakim drugim vozliščem v grafu. Znan je tudi kot a celoten graf.
- Psevdo graf: Graf, ki ima poleg drugih robov grafa samozanko, se imenuje psevdograf.
- Običajni graf: Pravilni graf je graf, kjer imajo vsa vozlišča enake stopnje; t.j. vsako vozlišče ima enako število sosedov.
- Povezani graf: Povezani graf je preprosto vsak graf, v katerem se kateri koli dve vozlišči povežeta; tj. graf z vsaj eno potjo med vsakima dvema vozliščema grafa.
- Odklopljen graf: Nepovezan graf je neposredno nasprotje povezanega grafa. V nepovezanem grafu ni robov, ki bi povezovali vozlišča grafa, kot na primer v a nič graf.
- Ciklični graf: Ciklični graf je graf, ki vsebuje vsaj en cikel grafa (pot, ki se konča tam, kjer se je začela).
- Aciklični graf: Aciklični graf je graf brez ciklov. Lahko je usmerjen ali neusmerjen.
- Podgraf: Podgraf je izpeljan graf. Je graf, sestavljen iz vozlišč in robov, ki so podmnožice drugega grafa.
A zanka v grafu je rob, ki se začne iz vozlišča in konča na istem vozlišču. Zato je a samozanka je zanka čez samo eno vozlišče grafa, kot je razvidno iz psevdo grafa.
Algoritmi prečkanja grafov
Ker gre za vrsto nelinearne podatkovne strukture, je prečkanje grafa precej težavno. Prečkanje grafa pomeni iti skozi in raziskovati vsako vozlišče, če obstaja veljavna pot skozi robove. Algoritmi za prečkanje grafov so večinoma dveh vrst.
- Iskanje v širino (BFS): Iskanje v širino je algoritem za prečkanje grafa, ki obišče vozlišče grafa in raziskuje njegove sosede, preden gre do katerega koli od njegovih podrejenih vozlišč. Čeprav lahko začnete prečkati graf iz katerega koli izbranega vozlišča, je korensko vozlišče običajno najprimernejše izhodišče.
- Iskanje najprej v globino (DFS): To je drugi večji algoritem za prečkanje grafa. Obišče vozlišče grafa in razišče njegova podrejena vozlišča ali veje, preden nadaljuje do naslednjega vozlišča – to pomeni, da gre najprej globoko, preden gre široko.
Iskanje v širino je priporočen algoritem za čim hitrejše iskanje poti med dvema vozliščema, zlasti najkrajše poti.
Iskanje najprej v globino je večinoma priporočljivo, ko želite obiskati vsako vozlišče v grafu. Oba algoritma prečkanja v vsakem primeru dobro delujeta, vendar je lahko eden enostavnejši in bolj optimiziran kot drugi v izbranih scenarijih.
Preprosta ilustracija lahko pomaga bolje razumeti oba algoritma. Zamislite si države države kot graf in poskusite preveriti, ali dve državi, X in Y, so povezani. Iskanje najprej v globino lahko poteka skoraj po vsej državi, ne da bi se tega zavedali dovolj zgodaj Y je le 2 državi stran X.
Prednost iskanja v širino je, da ohrani čim večjo bližino trenutnega vozlišča, preden preide na naslednjega. Našel bo povezavo med X in Y v kratkem času, ne da bi morali raziskati celotno državo.
Druga velika razlika med tema dvema algoritmoma je v načinu implementacije v kodo. Iskanje v širino je iterativni algoritem in uporablja a čakalna vrsta, medtem ko je iskanje najprej v globino običajno izvedeno kot a rekurzivni algoritem ki izkorišča kup.
Spodaj je nekaj psevdokod, ki prikazujejo izvajanje obeh algoritmov.
Iskanje v širino
bfs (Graph G, koren GraphNode) {
pustiti q bodi novo Čakalna vrsta// označi koren kot obiskan
root.visited = prav// dodaj koren v čakalno vrsto
q.v čakalni vrsti(korenina)
medtem (q ni prazno) {
pustiti trenutno je q.dequeue() // odstrani sprednji element v čakalni vrsti
za (sosede n toka v G) {
če (n jene še obiskan) {
// dodaj v čakalno vrsto - da lahko raziščeš tudi njegove sosede
q.v čakalni vrsti(n)
n.obiskano = prav
}
}
}
}
Iskanje najprej v globino
dfs (Graf G, koren GraphNode) {
// osnovni primer
če (koren je nič) vrnitev// označi koren kot obiskan
root.visited = prav
za (sosede n korena v G)
če (n jene še obiskan)
dfs (G, n) // rekurzivni klic
}
Nekaj drugih algoritmov za prečkanje grafov izhaja iz iskanja najprej v širino in globino. Najbolj priljubljeni so:
- Dvosmerno iskanje: Ta algoritem je optimiziran način iskanja najkrajše poti med dvema vozliščema. Uporablja dve iskanji v širino, ki trčita, če obstaja pot.
- Topološka vrsta: To se uporablja v usmerjeni grafi da razvrstite vozlišča v želenem vrstnem redu. Topološkega razvrščanja ne morete uporabiti za neusmerjene grafe ali grafe s cikli.
- Dijkstrajev algoritem: To je tudi vrsta BFS. Uporablja se tudi za iskanje najkrajše poti med dvema vozliščema v a uteženi usmerjeni graf, ki ima lahko cikle ali ne.
Pogosta vprašanja za intervju, ki temeljijo na grafih
Grafi so med pomembnimi podatkovne strukture, ki bi jih moral poznati vsak programer. V tehničnih razgovorih se pogosto pojavljajo vprašanja o tej temi in morda boste naleteli na nekaj klasičnih težav, povezanih s temo. Sem spadajo stvari, kot so "mestni sodnik", "število otokov" in "prodajni potujoči" problemi.
To je le nekaj izmed mnogih priljubljenih problemov intervjujev, ki temeljijo na grafih. Lahko jih preizkusite LeetCode, HackerRank, oz GeeksforGeeks.
Razumevanje podatkovnih struktur in algoritmov grafov
Grafi niso uporabni le za tehnične razgovore. Imajo tudi primere uporabe v resničnem svetu, na primer v mreženje, zemljevidi, in letalski sistemi za iskanje poti. Uporabljajo se tudi v osnovni logiki računalniških sistemov.
Grafi so odlični za organiziranje podatkov in za pomoč pri vizualizaciji kompleksnih problemov. Grafe je treba uporabljati le, kadar je to nujno potrebno, da preprečite zapletenost prostora ali težave s pomnilnikom.
