Un ghid pentru structura datelor grafice

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.

REALIZAREA VIDEOCLIPULUI ZILEI

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.