Tehokas ohjelmoija tarvitsee vankan ymmärryksen tietorakenteista ja algoritmeista. Tekniset haastattelut testaavat usein ongelmanratkaisukykyäsi ja kriittistä ajattelua.
Graafit ovat yksi monista ohjelmoinnin tärkeistä tietorakenteista. Useimmissa tapauksissa graafien ymmärtäminen ja graafipohjaisten ongelmien ratkaiseminen ei ole helppoa.
Mikä on kaavio ja mitä sinun tulee tietää siitä?
Mikä on graafi?
Graafi on epälineaarinen tietorakenne, jossa on solmuja (tai kärkipisteitä), joiden reunat yhdistävät ne. Kaikki puut ovat graafien alatyyppejä, mutta kaikki graafit eivät ole puita, ja kaavio on tietorakenne, josta puut ovat peräisin.
Vaikka voit rakentaa tietorakenteita JavaScriptillä ja muilla kielillä, voit toteuttaa kaavion eri tavoilla. Suosituimmat lähestymistavat ovat reunalistat, naapuriluettelot, ja viereisyysmatriisit.
The Khan Academyn opas kuvaajien esittämiseen on loistava resurssi kaavion esittämisen oppimiseen.
Kaavioita on monenlaisia. Yksi yhteinen ero on ohjattu ja ohjaamaton kaaviot; Näitä tulee paljon esille koodaushaasteissa ja tosielämässä.
Graafisten tyypit
- Suunnattu kaavio: Kaavio, jossa kaikilla reunoilla on suunta, jota kutsutaan myös nimellä digrafi.
- Suuntaamaton kaavio: Suuntaamaton graafi tunnetaan myös kaksisuuntaisena graafina. Suuntaamattomissa grafiikoissa reunojen suunnalla ei ole väliä, ja läpikulku voi mennä mihin tahansa suuntaan.
- Painotettu kaavio: Painotettu graafi on graafi, jonka solmuilla ja reunoilla on arvo. Useimmissa tapauksissa tämä arvo edustaa kyseisen solmun tai reunan tutkimisen kustannuksia.
- Rajallinen graafi: Graafi, jossa on äärellinen määrä solmuja ja reunoja.
- Ääretön kaavio: Graafi, jossa on ääretön määrä solmuja ja reunoja.
- Triviaali kaavio: Graafi, jossa on vain yksi solmu eikä reunaa.
- Yksinkertainen kaavio: Kun vain yksi reuna yhdistää graafin jokaisen solmuparin, sitä kutsutaan yksinkertaiseksi graafiksi.
- Nollakaavio: Nollagraafi on graafi, jolla ei ole solmuja yhdistäviä reunoja.
- Monikuvaaja: Multigrafissa ainakin solmuparilla on useampi kuin yksi reuna, joka yhdistää niitä. Multigrafeissa ei ole itsesilmukoita.
- Täydellinen kaavio: Täydellinen graafi on graafi, jossa jokainen solmu muodostaa yhteyden jokaiseen toiseen graafin solmuun. Se tunnetaan myös nimellä a täysi kaavio.
- Pseudokaavio: Graafia, jolla on itsesilmukka muiden graafin reunojen lisäksi, kutsutaan pseudograafiksi.
- Tavallinen kaavio: Säännöllinen graafi on graafi, jossa kaikilla solmuilla on samat asteet; eli jokaisella solmulla on sama määrä naapureita.
- Yhdistetty kaavio: Yhdistetty graafi on yksinkertaisesti mikä tahansa graafi, jossa mitkä tahansa kaksi solmua yhdistyvät; eli graafi, jossa on vähintään yksi polku graafin kahden solmun välillä.
- Yhteys katkennut kaavio: Kytkemätön graafi on suora vastakohta yhdistetylle graafille. Kytkemättömässä graafissa ei ole graafin solmuja yhdistäviä reunoja, kuten kohdassa a tyhjä kaavio.
- Syklinen kaavio: Syklinen graafi on graafi, joka sisältää vähintään yhden graafisyklin (polku, joka päättyy siihen, mihin se alkoi).
- Asyklinen kaavio: Asyklinen graafi on graafi, jossa ei ole lainkaan syklejä. Se voi olla joko ohjattua tai ohjaamatonta.
- Alakaavio: Aligraafi on johdettu graafi. Se on graafi, joka on muodostettu solmuista ja reunoista, jotka ovat toisen graafin osajoukkoja.
A silmukka graafissa on reuna, joka alkaa solmusta ja päättyy samaan solmuun. Siksi a itsesilmukka on silmukka vain yhden graafisolmun yli, kuten pseudograafissa nähdään.
Graafisen läpikulkualgoritmit
Koska kyseessä on epälineaarisen tietorakenteen tyyppi, graafin läpikulku on melko hankalaa. Graafin läpi kulkeminen tarkoittaa jokaisen solmun läpikäymistä ja tutkimista, koska reunojen läpi on kelvollinen polku. Graafisten läpikulkualgoritmeja on pääasiassa kahdenlaisia.
- Breadth-First Search (BFS): Leveyshaku on graafin läpikulkualgoritmi, joka vierailee graafin solmussa ja tutkii sen naapureita ennen kuin se siirtyy mihinkään sen alisolmuihin. Vaikka voit aloittaa kaavion kulkemisen mistä tahansa valitusta solmusta, juurisolmu on yleensä suositeltu lähtökohta.
- Depth-First Search (DFS): Tämä on toinen suuri graafin läpikulkualgoritmi. Se vierailee graafin solmussa ja tutkii sen alisolmuja tai haaroja ennen kuin siirtyy seuraavaan solmuun – eli menee ensin syvälle ennen leveyttä.
Leveyshaku on suositeltava algoritmi löytääksesi polut kahden solmun välillä mahdollisimman nopeasti, erityisesti lyhimmän polun.
Syvyys-ensimmäinen haku on enimmäkseen suositeltavaa, kun haluat käydä jokaisessa kaavion solmussa. Molemmat läpikulkualgoritmit toimivat hyvin joka tapauksessa, mutta toinen voi olla yksinkertaisempi ja optimoitu kuin toinen valituissa skenaarioissa.
Yksinkertainen kuva voi auttaa ymmärtämään molempia algoritmeja paremmin. Ajattele maan osavaltioita kaaviona ja yritä tarkistaa, onko kaksi osavaltiota, X ja Y, on yhdistetty. Syvyysensimmäinen etsintä saattaa kulkea polulla melkein ympäri maata ymmärtämättä sitä riittävän aikaisin Y on vain 2 osavaltion päässä X.
Leveyshaun etuna on, että se säilyttää mahdollisimman lähellä nykyistä solmua ennen seuraavaan siirtymistä. Se löytää yhteyden välillä X ja Y lyhyessä ajassa joutumatta tutkimaan koko maata.
Toinen suuri ero näiden kahden algoritmin välillä on tavassa, jolla ne on toteutettu koodissa. Breadth-first-haku on iteratiivinen algoritmi ja käyttää a jonottaa, kun taas syvyyshaku toteutetaan yleensä a rekursiivinen algoritmi joka hyödyntää pino.
Alla on pseudokoodi, joka havainnollistaa molempien algoritmien toteutusta.
Breadth-First Search
bfs (kaavio G, GraphNode-juuri) {
päästää q olla Uusi Jonottaa// merkitse juuri käydyksi
root.visited = totta// lisää juuri jonoon
q.enqueue(juuri)
sillä aikaa (q ei ole tyhjä) {
päästää nykyinen be q.dequeue() // poista etuelementti jonosta
for (G: n virran naapurit n) {
jos (n Onei vielä käynyt) {
// lisää jonoon - jotta voit tutkia myös sen naapureita
q.enqueue(n)
n.vieraillut = totta
}
}
}
}
Syvyys-ensimmäinen haku
dfs (kaavio G, GraphNode-juuri) {
// perustapaus
jos (juuri on tyhjä) palata// merkitse juuri käydyksi
root.visited = totta
for (G: n juuren naapurit n)
jos (n Onei vielä vieraillut)
dfs (G, n) // rekursiivinen puhelu
}
Muutamat muut graafin läpikulkualgoritmit ovat peräisin leveys- ja syvyyshakuista. Suosituimmat ovat:
- Kaksisuuntainen haku: Tämä algoritmi on optimoitu tapa löytää lyhin polku kahden solmun välillä. Se käyttää kahta leveyshakua, jotka törmäävät, jos polku on olemassa.
- Topologinen lajittelu: Tätä käytetään mm suunnatut kaaviot järjestääksesi solmut haluttuun järjestykseen. Et voi käyttää topologista lajittelua suuntaamattomissa tai syklisissä kaavioissa.
- Dijkstran algoritmi: Tämä on myös eräänlainen BFS. Sitä käytetään myös lyhimmän polun löytämiseen a: n kahden solmun välillä painotettu suunnattu graafi, joilla voi olla kiertoja tai ei.
Yleiset haastattelukysymykset kaavioiden perusteella
Graafit ovat tärkeitä tietorakenteet jokaisen ohjelmoijan tulisi tietää. Tästä aiheesta herää usein kysymyksiä teknisissä haastatteluissa, ja saatat kohdata klassisia aiheeseen liittyviä ongelmia. Näitä ovat esimerkiksi "kaupungin tuomari", "saarten lukumäärä" ja "matkustava myyjä" -ongelmat.
Nämä ovat vain muutamia monista suosituista kaaviopohjaisista haastatteluongelmista. Voit kokeilla niitä LeetCode, HackerRank, tai GeeksforGeeks.
Graafisten tietorakenteiden ja algoritmien ymmärtäminen
Kaaviot eivät ole hyödyllisiä vain teknisissä haastatteluissa. Heillä on myös tosielämän käyttötapauksia, kuten in verkostoituminen, kartat, ja lentoyhtiöiden järjestelmät reittien etsimiseen. Niitä käytetään myös tietokonejärjestelmien taustalla olevassa logiikassa.
Kaaviot ovat erinomaisia tietojen järjestämiseen ja monimutkaisten ongelmien visualisointiin. Kaavioita tulee kuitenkin käyttää vain silloin, kun se on ehdottoman välttämätöntä tilan monimutkaisuuden tai muistiongelmien välttämiseksi.