Tõhus programmeerija vajab andmestruktuuride ja algoritmide põhjalikku mõistmist. Tehnilised intervjuud panevad sageli proovile teie probleemide lahendamise ja kriitilise mõtlemise oskused.
Graafikud on programmeerimisel üks paljudest olulistest andmestruktuuridest. Enamasti ei tule graafikute mõistmine ja graafikupõhiste ülesannete lahendamine lihtsalt.
Mis on graafik ja mida peate selle kohta teadma?
Mis on graafik?
Graaf on mittelineaarne andmestruktuur, millel on sõlmed (või tipud) neid ühendavate servadega. Kõik puud on graafikute alamtüübid, kuid mitte kõik graafikud on puud ja graafik on andmestruktuur, millest puud pärinevad.
Kuigi saate luua andmestruktuure JavaScriptis ja teistes keeltes, saate graafiku rakendada mitmel viisil. Kõige populaarsemad lähenemisviisid on servaloendid, naabrusnimekirjadja naabrusmaatriksid.
The Khan Academy juhend graafikute esitamiseks on suurepärane ressurss graafiku esitamise õppimiseks.
Graafikuid on palju erinevaid. Üks ühine erinevus on suunatud ja suunamata graafikud; neid tuleb kodeerimise väljakutsetes ja reaalses elus palju ette.
Graafikute tüübid
- Suunatud graafik: Graafik, mille kõigil servadel on suund, mida nimetatakse ka kui digraaf.
- Suunamata graafik: Suunamata graafikut tuntakse ka kahesuunalise graafikuna. Suunamata graafikute puhul ei oma servade suund tähtsust ja läbimine võib toimuda igas suunas.
- Kaalutud graafik: Kaalutud graaf on graaf, mille sõlmedel ja servadel on seotud väärtus. Enamikul juhtudel tähistab see väärtus selle sõlme või serva uurimise kulusid.
- Lõplik graafik: Graaf, millel on lõplik arv sõlmi ja servi.
- Lõpmatu graafik: Graafik, millel on lõpmatu arv sõlmi ja servi.
- Triviaalne graafik: Graaf, millel on ainult üks sõlm ja millel pole serva.
- Lihtne graafik: Kui graafi iga sõlmede paari ühendab ainult üks serv, nimetatakse seda lihtsaks graafikuks.
- Nullgraafik: Nullgraaf on graaf, millel pole sõlmi ühendavaid servi.
- Multigraaf: Multigraafis on vähemalt paaril sõlmel rohkem kui üks serv, mis ühendab neid. Multigraafides pole enesesilmusi.
- Täielik graafik: Tervikgraafik on graafik, mille iga sõlm ühendub graafiku kõigi teiste sõlmedega. Seda tuntakse ka kui a täielik graafik.
- Pseudograafik: Graafi, millel on teistest graafi servadest kõrvalekalduv enesesilmus, nimetatakse pseudograafiks.
- Tavaline graafik: Tavaline graaf on graaf, kus kõigil sõlmedel on võrdsed kraadid; st igal sõlmel on sama arv naabreid.
- Ühendatud graafik: Ühendatud graaf on lihtsalt mis tahes graaf, milles mis tahes kaks sõlme ühenduvad; st graafik, millel on vähemalt üks tee graafiku iga kahe sõlme vahel.
- Katkestatud graafik: Lahtiühendatud graaf on ühendatud graafiku otsene vastand. Lahtiühendatud graafis ei ole graafiku sõlmi ühendavaid servi, näiteks punktis a null graafik.
- Tsükliline graafik: Tsükliline graaf on graafik, mis sisaldab vähemalt ühte graafikutsüklit (tee, mis lõpeb seal, kus see algas).
- Atsükliline graafik: Atsükliline graaf on graaf, millel pole üldse tsükleid. See võib olla kas suunatud või suunamata.
- Alamgraafik: Alamgraaf on tuletatud graaf. See on graafik, mis on moodustatud sõlmedest ja servadest, mis on teise graafi alamhulgad.
A silmus graafis on serv, mis algab sõlmest ja lõpeb samas sõlmes. Seetõttu a enesesilmus on silmus ainult ühe graafi sõlme kohal, nagu näha pseudograafil.
Graafiku läbimise algoritmid
Kuna tegemist on mittelineaarse andmestruktuuri tüübiga, on graafiku läbimine üsna keeruline. Graafi läbimine tähendab iga sõlme läbimist ja uurimist, kuna seal on kehtiv tee läbi servade. Graafiku läbimise algoritme on peamiselt kahte tüüpi.
- Breadth-First Search (BFS): Laiuseotsing on graafiku läbimise algoritm, mis külastab graafiku sõlme ja uurib selle naabreid, enne kui läheb selle mis tahes alamsõlme juurde. Kuigi saate alustada graafiku läbimist mis tahes valitud sõlmest, juursõlm on tavaliselt eelistatud lähtepunkt.
- Sügavuspõhine otsing (DFS): See on teine suurem graafiku läbimise algoritm. See külastab graafiku sõlme ja uurib selle alamsõlmi või harusid, enne kui liigub järgmise sõlme juurde, st läheb kõigepealt sügavale, enne kui läheb laiali.
Laiuseotsing on soovitatav algoritm, et leida võimalikult kiiresti kahe sõlme vahelised teed, eriti lühim tee.
Sügavuspõhine otsing on enamasti soovitatav, kui soovite külastada graafiku kõiki sõlme. Mõlemad läbimisalgoritmid töötavad igal juhul hästi, kuid valitud stsenaariumide korral võib üks neist olla lihtsam ja optimeeritud kui teine.
Lihtne illustratsioon võib aidata mõlemat algoritmi paremini mõista. Mõelge riigi osariikidele kui graafikule ja proovige kontrollida, kas kaks osariiki, X ja Y, on ühendatud. Sügavuse esimene otsing võib minna peaaegu mööda riiki, ilma et sellest piisavalt vara aru saaks Y on vaid 2 osariigi kaugusel X.
Laius-esimese otsingu eeliseks on see, et see säilitab võimalikult suure läheduse praegusele sõlmele enne järgmise sõlme minekut. See leiab seose X ja Y lühikese ajaga, ilma et peaks kogu riiki avastama.
Teine oluline erinevus nende kahe algoritmi vahel on nende koodis rakendamine. Laiuseotsing on an iteratiivne algoritm ja kasutab a järjekorda, samas kui sügavus-esimene otsing rakendatakse tavaliselt kui a rekursiivne algoritm mis võimendab virna.
Allpool on pseudokood, mis demonstreerib mõlema algoritmi rakendamist.
Breadth-First Search
bfs (Graaf G, GraphNode juur) {
lase q olema uus Järjekord// märgi juur külastatuks
juur.külastatud = tõsi// juure lisamine järjekorda
q.järjekorda(juur)
samal ajal (q ei ole tühi) {
lase current be q.dequeue() // eemaldab järjekorrast eesmise elemendi
for (naabrid n voolust G-s) {
kui (n onmitte veel külastatud) {
// lisage järjekorda – nii saate ka selle naabreid uurida
q.järjekorda(n)
n.külastatud = tõsi
}
}
}
}
Sügavus-Esimene otsing
dfs (Graaf G, GraphNode juur) {
// põhijuhtum
kui (juur on null) tagasi// märgi juur külastatuks
juur.külastatud = tõsi
jaoks (G juure naabrid n)
kui (n onmitte veel külastatud)
dfs (G, n) // rekursiivne kõne
}
Mõned teised graafiku läbimise algoritmid tulenevad laius- ja sügavuspõhistest otsingutest. Kõige populaarsemad on:
- Kahesuunaline otsing: See algoritm on optimeeritud viis lühima tee leidmiseks kahe sõlme vahel. See kasutab kahte laiuseotsingut, mis põrkuvad tee olemasolul.
- Topoloogiline sortimine: Seda kasutatakse aastal suunatud graafikud sõlmede sorteerimiseks soovitud järjekorras. Suunamata või tsüklitega graafikutele ei saa topoloogilist sortimist rakendada.
- Dijkstra algoritm: See on ka teatud tüüpi BFS. Seda kasutatakse ka lühima tee leidmiseks kahe sõlme vahel a-s kaalutud suunatud graafik, millel võivad olla tsüklid või mitte.
Levinud intervjuuküsimused graafikute põhjal
Graafikud on olulisemate hulgas andmestruktuurid, mida iga programmeerija peaks teadma. Tehnilistes intervjuudes kerkib sellel teemal sageli küsimusi ja võite kohata teemaga seotud klassikalisi probleeme. Nende hulka kuuluvad sellised asjad nagu "linnakohtunik", "saarte arv" ja "reisiva müügimehe" probleemid.
Need on vaid mõned paljudest populaarsetest graafikupõhistest intervjuuprobleemidest. Saate neid proovida LeetCode, HäckerRank, või GeeksforGeeks.
Graafiku andmestruktuuride ja algoritmide mõistmine
Graafikud pole kasulikud ainult tehniliste intervjuude jaoks. Neil on ka reaalseid kasutusjuhtumeid, näiteks sisse võrgud, kaardid, ja lennufirmade süsteemid marsruutide leidmiseks. Neid kasutatakse ka arvutisüsteemide aluseks olevas loogikas.
Graafikud on suurepärased andmete korrastamiseks ja keerukate probleemide visualiseerimiseks. Ruumi keerukuse või mäluprobleemide vältimiseks tuleks graafikuid kasutada ainult siis, kui see on hädavajalik.