Učinkovit programer treba solidno razumijevanje struktura podataka i algoritama. Tehnički intervjui često će testirati vaše vještine rješavanja problema i kritičkog razmišljanja.
Grafovi su jedna od mnogih važnih struktura podataka u programiranju. U većini slučajeva razumijevanje grafova i rješavanje problema temeljenih na grafovima nije lako.
Što je graf i što trebate znati o njemu?
Što je grafikon?
Graf je nelinearna podatkovna struktura koja ima čvorove (ili vrhove) s rubovima koji ih povezuju. Sva stabla su podvrste grafova, ali nisu svi grafovi stabla, a graf je struktura podataka iz koje stabla potječu.
Iako možete izgraditi strukture podataka u JavaScriptu i drugim jezicima, možete implementirati graf na razne načine. Najpopularniji pristupi su rubne liste, liste susjedstva, i matrice susjedstva.
The Khan Academy vodič za predstavljanje grafova odličan je izvor za učenje o tome kako prikazati graf.
Postoji mnogo različitih vrsta grafikona. Jedna uobičajena razlika je između usmjerena i neusmjeren grafovi; oni se često pojavljuju u izazovima kodiranja iu stvarnom životu.
Vrste grafova
- Usmjereni graf: Graf u kojem svi rubovi imaju smjer, također se naziva digraf.
- Neusmjereni graf: Neusmjereni graf je također poznat kao dvosmjerni graf. U neusmjerenim grafovima, smjer rubova nije bitan, a obilazak može ići u bilo kojem smjeru.
- Ponderirani grafikon: Ponderirani graf je graf čiji čvorovi i rubovi imaju pridruženu vrijednost. U većini slučajeva ova vrijednost predstavlja trošak istraživanja tog čvora ili ruba.
- Konačni graf: Graf koji ima konačan broj čvorova i rubova.
- Beskonačni graf: Graf koji ima beskonačnu količinu čvorova i rubova.
- Trivijalni graf: Graf koji ima samo jedan čvor i nema ruba.
- Jednostavan grafikon: Kada samo jedan rub povezuje svaki par čvorova grafa, naziva se jednostavnim grafom.
- Nulti graf: Nulti graf je graf koji nema rubove koji povezuju njegove čvorove.
- Multigraf: U multigrafu, barem par čvorova ima više od jednog ruba koji ih povezuje. U multigrafima nema samopetlji.
- Potpuni grafikon: Potpuni graf je graf u kojem se svaki čvor povezuje sa svakim drugim čvorom u grafu. Također je poznat kao a puni graf.
- Pseudo graf: Graf koji ima samopetlju osim ostalih rubova grafa naziva se pseudograf.
- Uobičajeni grafikon: Regularni graf je graf u kojem svi čvorovi imaju jednake stupnjeve; tj. svaki čvor ima isti broj susjeda.
- Povezani graf: Povezani graf je jednostavno bilo koji graf u kojem se spajaju bilo koja dva čvora; tj. graf s najmanje jednom stazom između svaka dva čvora grafa.
- Isključeni grafikon: Nepovezani graf je izravna suprotnost povezanom grafu. U nepovezanom grafu, nema rubova koji povezuju čvorove grafa, kao što je u a ništavan graf.
- Ciklični grafikon: Ciklički graf je graf koji sadrži najmanje jedan ciklus grafa (put koji završava tamo gdje je započeo).
- Aciklički graf: Aciklički graf je graf bez ikakvih ciklusa. Može biti usmjeren ili neusmjeren.
- Podgraf: Podgraf je izvedeni graf. To je graf formiran od čvorova i rubova koji su podskupovi drugog grafa.
A petlja u grafu je rub koji počinje od čvora i završava u istom čvoru. Stoga, a samopetlja je petlja preko samo jednog čvora grafa, kao što se vidi u pseudo grafu.
Algoritmi za obilazak grafa
Budući da je to vrsta nelinearne podatkovne strukture, prelaženje grafa prilično je nezgodno. Kretanje grafom znači prolaženje i istraživanje svakog čvora s obzirom da postoji valjan put kroz rubove. Algoritmi za obilazak grafa uglavnom su dva tipa.
- Pretraživanje u širinu (BFS): Pretraživanje u širinu je algoritam za obilazak grafa koji posjećuje čvor grafa i istražuje njegove susjede prije nego što ode na bilo koji od njegovih čvorova djeteta. Iako možete početi obilaziti graf iz bilo kojeg odabranog čvora, korijenski čvor je obično poželjna početna točka.
- Pretraživanje prvo u dubinu (DFS): Ovo je drugi glavni algoritam za obilazak grafa. Posjećuje čvor grafa i istražuje njegove podređene čvorove ili grane prije nego što nastavi do sljedećeg čvora—to jest, ide prvo duboko prije nego što ide široko.
Pretraživanje u širinu preporučeni je algoritam za pronalaženje staza između dva čvora što je brže moguće, posebno najkraće staze.
Pretraživanje najprije u dubinu uglavnom se preporučuje kada želite posjetiti svaki čvor na grafikonu. Oba algoritma za prolazak rade dobro u svakom slučaju, ali bi jedan mogao biti jednostavniji i optimiziraniji od drugog u odabranim scenarijima.
Jednostavna ilustracija može pomoći u boljem razumijevanju oba algoritma. Zamislite države neke zemlje kao grafikon i pokušajte provjeriti jesu li dvije države, x i Y, povezani su. Pretraživanje najprije u dubinu moglo bi krenuti gotovo cijelom zemljom, a da to ne shvatite dovoljno rano Y udaljen je samo 2 države x.
Prednost pretraživanja u širinu je u tome što održava blizinu trenutnog čvora što je više moguće prije odlaska na sljedeći. Pronaći će vezu između x i Y u kratkom vremenu bez potrebe da istražujete cijelu zemlju.
Druga velika razlika između ova dva algoritma je način na koji su implementirani u kodu. Pretraživanje u širinu je iterativni algoritam i koristi a red, dok se dubinsko pretraživanje obično implementira kao a rekurzivni algoritam koji iskorištava stog.
Ispod je neki pseudokod koji demonstrira implementaciju oba algoritma.
Pretraživanje u širinu
bfs (Grafikon G, korijen GraphNode) {
neka q biti novi Red// označi korijen kao posjećen
korijen.posjećeno = pravi// dodaj root u red čekanja
q.staviti u red(korijen)
dok (q nije prazan) {
neka tekući biti q.dequeue() // uklanjanje prednjeg elementa u redu
za (susjedi n struje u G) {
ako (n jene još posjećeno) {
// dodaj u red čekanja - tako da možeš istraživati i njegove susjede
q.staviti u red(n)
n.posjetio = pravi
}
}
}
}
Pretraživanje najprije u dubinu
dfs (Grafikon G, korijen GraphNode) {
// osnovni slučaj
ako (korijen je ništavan) povratak// označi korijen kao posjećen
korijen.posjećeno = pravi
za (susjedi n korijena u G)
ako (n jene još posjećeno)
dfs (G, n) // rekurzivni poziv
}
Nekoliko drugih algoritama za obilazak grafa proizlazi iz pretraživanja prvo u širinu i prvo u dubinu. Najpopularniji su:
- Dvosmjerno pretraživanje: Ovaj je algoritam optimizirani način pronalaženja najkraćeg puta između dva čvora. Koristi dva pretraživanja u širinu koja se sudaraju ako postoji put.
- Topološko sortiranje: Ovo se koristi u usmjereni grafovi sortirati čvorove željenim redoslijedom. Ne možete primijeniti topološko sortiranje na neusmjerene grafove ili grafove s ciklusima.
- Dijkstrin algoritam: Ovo je također vrsta BFS-a. Također se koristi za pronalaženje najkraćeg puta između dva čvora u a težinski usmjereni graf, koji može imati cikluse ili ne.
Uobičajena pitanja za intervju temeljena na grafikonima
Grafikoni su među važnima strukture podataka koje svaki programer treba poznavati. Često se pojavljuju pitanja o ovoj temi u tehničkim intervjuima, a možete se susresti i s nekim klasičnim problemima vezanim uz tu temu. To uključuje probleme poput "gradskog suca", "broja otoka" i "trgovačkog putnika".
Ovo su samo neki od mnogih popularnih problema intervjua temeljenih na grafikonima. Možete ih isprobati LeetCode, HackerRank, ili GeeksforGeeks.
Razumijevanje struktura podataka grafikona i algoritama
Grafikoni nisu korisni samo za tehničke intervjue. Imaju i slučajeve upotrebe u stvarnom svijetu, kao što je u umrežavanje, karte, i zračni sustavi za pronalaženje ruta. Također se koriste u temeljnoj logici računalnih sustava.
Grafikoni su izvrsni za organiziranje podataka i za pomoć u vizualizaciji složenih problema. Međutim, grafikone treba koristiti samo kada je to apsolutno neophodno kako bi se spriječila složenost prostora ili problemi s memorijom.
