Un programator eficient are nevoie de o înțelegere solidă a structurilor de date și a algoritmilor. Interviurile tehnice vă vor testa adesea abilitățile de rezolvare a problemelor și de gândire critică.
Graficele sunt una dintre numeroasele structuri de date importante în programare. În cele mai multe cazuri, înțelegerea graficelor și rezolvarea problemelor bazate pe grafice nu sunt ușoare.
Ce este un grafic și ce trebuie să știi despre el?
Ce este un grafic?
Un graf este o structură de date neliniară care are noduri (sau vârfuri) cu muchii care le conectează. Toți arborii sunt subtipuri de grafice, dar nu toate graficele sunt arbori, iar graficul este structura de date din care au provenit arborii.
Deși poți construiți structuri de date în JavaScript și în alte limbi, puteți implementa un grafic în diferite moduri. Cele mai populare abordări sunt liste marginale, liste de vecinătate, și matrici de adiacenta.
The Ghidul Khan Academy pentru reprezentarea graficelor este o resursă excelentă pentru a afla cum să reprezinte un grafic.
Există multe tipuri diferite de grafice. O distincție comună este între regizat și nedirecţionată grafice; acestea apar foarte mult în provocările de codificare și utilizări din viața reală.
Tipuri de grafice
- Graficul direcționat: Un grafic în care toate muchiile au o direcție, denumită și digraf.
- Grafic nedirecționat: Un graf nedirecționat este cunoscut și ca graf cu două sensuri. În graficele nedirecționate, direcția muchiilor nu contează, iar traversarea poate merge în orice direcție.
- Grafic ponderat: Un grafic ponderat este un grafic ale cărui noduri și muchii au o valoare asociată. În cele mai multe cazuri, această valoare reprezintă costul explorării acelui nod sau margine.
- Grafic finit: Un grafic care are un număr finit de noduri și muchii.
- Grafic infinit: Un grafic care are o cantitate infinită de noduri și muchii.
- Grafic banal: Un grafic care are doar un nod și nicio margine.
- Grafic simplu: Când o singură muchie conectează fiecare pereche de noduri ale unui graf, se numește graf simplu.
- Grafic nul: Un graf nul este un graf care nu are muchii care să le conecteze nodurile.
- Multigraf: Într-un multigraf, cel puțin o pereche de noduri au mai mult de o margine care le conectează. În multigrafe, nu există auto-bucle.
- Graficul complet: Un grafic complet este un grafic în care fiecare nod se conectează la orice alt nod din grafic. Este cunoscut și ca a grafic complet.
- Pseudografic: Un grafic care are o buclă automată în afară de alte margini ale graficului se numește pseudograf.
- Graficul obișnuit: Un graf obișnuit este un graf în care toate nodurile au grade egale; adică fiecare nod are același număr de vecini.
- Graficul conectat: Un graf conectat este pur și simplu orice graf în care oricare două noduri se conectează; adică un grafic cu cel puțin o cale între fiecare două noduri ale graficului.
- Grafic deconectat: Un graf deconectat este direct opusul unui graf conectat. Într-un graf deconectat, nu există muchii care leagă nodurile grafului, cum ar fi într-un nul grafic.
- Grafic ciclic: Un grafic ciclic este un grafic care conține cel puțin un ciclu de grafic (o cale care se termină acolo unde a început).
- Graficul aciclic: Un grafic aciclic este un grafic fără cicluri deloc. Poate fi fie direcționat, fie nedirecționat.
- Subgraf: Un subgraf este un grafic derivat. Este un graf format din noduri și muchii care sunt subseturi ale altui graf.
A buclă într-un graf este o muchie care începe de la un nod și se termină la același nod. Prin urmare, a auto-buclă este o buclă peste un singur nod de grafic, așa cum se vede într-un pseudograf.
Algoritmi de traversare a graficelor
Fiind un tip de structură de date neliniară, parcurgerea unui grafic este destul de dificilă. A parcurge un grafic înseamnă a parcurge și a explora fiecare nod, având în vedere că există o cale validă prin margini. Algoritmii de traversare a graficelor sunt în principal de două tipuri.
- Căutare pe lățimea întâi (BFS): Căutarea pe lățime este un algoritm de traversare a graficului care vizitează un nod de grafic și îi explorează vecinii înainte de a trece la oricare dintre nodurile sale secundare. Deși puteți începe să traversați un grafic din orice nod selectat, nodul rădăcină este de obicei punctul de plecare preferat.
- Căutare în profunzime (DFS): Acesta este al doilea algoritm major de traversare a graficului. Vizitează un nod grafic și explorează nodurile sau ramurile sale secundare înainte de a trece la următorul nod - adică, mergând mai întâi adânc înainte de a merge lat.
Căutarea pe lățime este algoritmul recomandat pentru a găsi căi între două noduri cât mai repede posibil, în special calea cea mai scurtă.
Căutarea în profunzime este recomandată în mare parte atunci când doriți să vizitați fiecare nod din grafic. Ambii algoritmi de traversare funcționează bine în orice caz, dar unul ar putea fi mai simplu și mai optimizat decât celălalt în scenariile selectate.
O ilustrare simplă poate ajuta la înțelegerea mai bună a ambilor algoritmi. Gândiți-vă la statele unei țări ca pe un grafic și încercați să verificați dacă două state, X și Y, sunt conectati. O căutare în profunzime ar putea merge pe o cale aproape în jurul țării, fără să-și dea seama suficient de devreme Y este la doar 2 state de X.
Avantajul unei căutări pe lățimea întâi este că menține apropierea de nodul curent cât mai mult posibil înainte de a trece la următorul. Va găsi legătura între X și Y într-un timp scurt fără a fi nevoie să exploreze toată țara.
O altă diferență majoră între acești doi algoritmi este modul în care sunt implementați în cod. Căutarea pe lățimea întâi este o algoritm iterativ și folosește a coadă, în timp ce o căutare în profunzime este de obicei implementată ca a algoritm recursiv care valorifică grămadă.
Mai jos este un pseudocod care demonstrează implementarea ambilor algoritmi.
Căutare pe lățimea întâi
bfs (Graph G, rădăcină GraphNode) {
lăsa q fi nou Coadă// marchează rădăcina ca fiind vizitată
rădăcină.vizitat = Adevărat// adaugă rădăcină la coadă
q.în coadă(rădăcină)
in timp ce (q nu este gol) {
lăsa curent fi q.dequeue() // elimină elementul frontal din coadă
pentru (vecini n de curent în G) {
dacă (n estenu încă vizitat) {
// adaugă la coadă - astfel încât să îi poți explora și vecinii
q.în coadă(n)
n.vizitat = Adevărat
}
}
}
}
Căutare în profunzime
dfs (Graph G, rădăcină GraphNode) {
// caz de baza
dacă (rădăcina este nul) întoarcere// marchează rădăcina ca fiind vizitată
rădăcină.vizitat = Adevărat
pentru (vecini n de rădăcină în G)
dacă (n estenu încă vizitat)
dfs (G, n) // apel recursiv
}
Câțiva alți algoritmi de traversare a graficului derivă din căutări pe lățime și pe adâncime. Cele mai populare sunt:
- Căutare bidirecțională: Acest algoritm este o modalitate optimizată de a găsi calea cea mai scurtă între două noduri. Utilizează două căutări la lățime, care se ciocnesc dacă există o cale.
- Sortare topologică: Aceasta este folosită în grafice dirijate pentru a sorta nodurile în ordinea dorită. Nu puteți aplica o sortare topologică graficelor nedirecționate sau graficelor cu cicluri.
- Algoritmul lui Dijkstra: Acesta este, de asemenea, un tip de BFS. De asemenea, este folosit pentru a găsi calea cea mai scurtă între două noduri în a grafic orientat ponderat, care poate avea cicluri sau nu.
Întrebări frecvente de interviu bazate pe grafice
Graficele sunt printre cele mai importante structurile de date pe care fiecare programator ar trebui să le cunoască. Întrebări apar adesea pe această temă în interviurile tehnice și este posibil să întâmpinați unele probleme clasice legate de subiect. Acestea includ lucruri precum „judecătorul orașului”, „numărul de insule” și problemele „vânzătorului călător”.
Acestea sunt doar câteva dintre numeroasele probleme populare ale interviurilor bazate pe grafice. Puteți să le încercați LeetCode, HackerRank, sau GeeksforGeeks.
Înțelegerea structurilor și algoritmilor de date grafice
Graficele nu sunt utile doar pentru interviurile tehnice. Au și cazuri de utilizare din lumea reală, cum ar fi în rețele, hărți, și sistemele aeriene pentru găsirea rutelor. Ele sunt, de asemenea, utilizate în logica de bază a sistemelor informatice.
Graficele sunt excelente pentru organizarea datelor și pentru a ne ajuta să vizualizăm probleme complexe. Graficele ar trebui folosite numai atunci când este absolut necesar, totuși, pentru a preveni complexitatea spațiului sau problemele de memorie.