Tipuri de grafice în structura datelor și aplicații

Introducere

Un grafic este o structură neliniară care cuprinde noduri și muchii. Poate include un set finit sau infinit de noduri ținute de o margine care conectează o pereche de noduri. Structurile de date sunt o parte esențială a oricărui concept de codare; astfel, o înțelegere fermă a diferitelor tipuri de grafice în structurile de date vă poate ajuta să rezolvați probleme complexe din lumea reală.

În lumea de astăzi, datele sunt putere. Astfel, organizarea eficientă a datelor pentru un acces ușor este esențială pentru orice programator. Cunoașterea structurilor de date și varietatea sa de grafice împuternicește abilitățile de codare pentru a viza problemele din lumea reală și pentru a oferi soluții în mod eficient.

Învață știința datelor pentru a câștiga avantaj în fața concurenților tăi

Să aruncăm o privire la diferitele tipuri de grafice utilizate în mod obișnuit în structurile de date și la modul în care sunt aplicate în viața reală.

Tipuri de grafice în structurile de date

O structură de date este un standard practic de stocare a datelor pentru toate limbile, cum ar fi structura de date graph python sau structura de date graph java. Stăpânirea tuturor tipurilor de grafice ar trebui să fie o prioritate pentru oricine aspiră să studieze structurile de date. Deoarece teoria grafurilor are multe aplicații în viața reală, acestea devin vitale în structurile de date.

Diferitele tipuri de grafice din structurile de date pot fi enumerate mai jos:

1. Graficul nul

După cum sugerează și numele, graficul nul este gol; cu alte cuvinte, este un grafic fără muchii. Constă numai din vârfuri izolate din grafic cu un set de muchii liber.

2. Grafic finit

Dacă numărul de muchii și noduri constă dintr-un număr finit dintr-un grafic, atunci graficul este cunoscut ca un grafic finit.

3. Graficul infinit

Dacă nu se poate pune un număr finit numărului de noduri și numărului de muchii dintr-un grafic, acesta este cunoscut ca un grafic infinit. Graficele infinite sunt de nenumărat, ceea ce înseamnă că nu puteți număra numărul de noduri sau muchii din acest tip de grafic.

4. Grafic simplu

Se spune că un grafic este simplu atunci când există o singură muchie între o pereche de vârfuri. Astfel, două noduri sunt conectate printr-o muchie într-un grafic, care poate identifica o relație definită între ele.

5. Grafic multiplu

Dacă o pereche de noduri este conectată cu mai multe muchii într-un grafic, atunci graficul este cunoscut ca multi-graf. Un grafic multiplu nu constă din bucle proprii. Există două tipuri de muchii care pot exista într-un multi-graf. Sunt:

• Margini paralele

Marginile care rulează paralel, cum ar fi două drumuri paralele care merg de la o sursă la aceeași destinație, sunt cunoscute ca margini paralele.

• Buclă

Aceasta este o muchie ale cărei vârfuri sursă și destinație sunt aceleași.

Verificați programele noastre din SUA - Data Science

6. Graficul Dirijat

Se spune că un grafic este direcționat dacă toate muchiile prezente între două noduri sau vârfuri au o direcție definită. Un graf direcționat este cunoscut și sub denumirea de digraf. Putem determina nodul de început și de sfârșit privind un grafic direcționat. Amintiți-vă, toate muchiile dintr-un graf direcționat trebuie să fie direcționate pentru a fi numite graf direcționat.

7. Graficul nedirecționat

Se spune că un graf este un graf nedirecționat dacă este greu de identificat nodul de început și de sfârșit privind marginile acestuia. La fel ca un graf direcționat, muchiile trebuie să fie nedirecționate pentru ca acesta să fie numit graf nedirecționat.

8. Grafic conectat

Un graf conectat este un graf în care există cel puțin o cale între toate nodurile. În termeni mai simpli, dacă porniți de la un nod dintr-un graf conectat, ar trebui să puteți vizita fiecare nod prezent în graf. Prin urmare, ar trebui să existe cel puțin o cale pentru fiecare nod.

9. Grafic deconectat

În acest tip de graf, nu există muchie între o pereche de noduri sau vârfuri. Astfel, spre deosebire de graficele conectate, atingerea tuturor nodurilor de la orice vârf nu este posibilă. Dacă vreo pereche de vârfuri nu are o cale între ele, se numește graf deconectat.

10. Graficul complet

Un grafic este considerat complet numai atunci când există o muchie între fiecare nod, ceea ce înseamnă că o muchie va conecta toate vârfurile din grafic. Un grafic complet pe n vârfuri este notat cu Kn , iar numărul de muchii din grafic este nC2 .

11. Graficul ciclic

Un grafic ar trebui să aibă cel puțin o componentă ciclică pentru a fi considerat un grafic ciclic. Dimpotrivă, dacă graficul nu conține niciun ciclu, este considerat un grafic aciclic.

12. Graficul obișnuit

Într-un grafic obișnuit, toate vârfurile ar trebui să aibă același grad. Gradul unui nod poate fi definit ca numărul de noduri conectate cu acesta. Astfel, într-un grafic obișnuit, toate nodurile ar trebui să fie conectate la același număr de noduri.

13. Grafic bipartit

Pentru ca un grafic să fie bipartit, ar trebui să îndeplinească următoarele criterii.

• Graficul trebuie împărțit în seturi de vârfuri.
• Marginile ar trebui să se formeze numai între un grup de noduri pe cealaltă parte. Această regulă împiedică legătura dintre două vârfuri ale aceluiași set de noduri.
• Cele două grupuri nu ar trebui să aibă vârfuri comune între ele.

Un grafic care urmează toate regulile de mai sus ar trebui considerat un graf bipartit.

14. Grafic etichetat

Muchiile din grafice pot fi ponderate. O greutate asociată cu o margine poate fi înțeleasă ca costul călătoriei prin acea margine. Aceste valori se pot baza pe un parametru fix și se pot schimba între grafice. Acum, dacă toate muchiile dețin o greutate asociată cu ele, atunci acel grafic poate fi numit un grafic etichetat.

15. Graficul Aciclic Dirijat

Un graf aciclic direcționat este o combinație de grafuri direcționate și aciclice în care marginile direcționate ale grafului nu fac nicio formă de ciclu. Dimpotrivă, un grafic ciclic direcționat este un grafic cu muchii direcționate care formează un ciclu.

Aplicarea graficului în structura datelor

Cea mai proeminentă aplicație a unui grafic în informatică este reprezentarea fluxului de calcul. Alte cazuri celebre folosite de grafice sunt:

1. Google Maps

În Google Maps, structurile de date grafice definesc și calculează sistemul de transport. Când un drum se întâlnește cu un alt drum și formează o trecere, acesta este considerat un nod, iar drumul dintre două astfel de noduri este tratat ca o margine. Prin urmare, Google Maps vă găsește cea mai scurtă și mai rapidă cale către destinație folosind structura de date grafică.

2. Facebook

Facebook folosește grafice nedirecționate pentru a identifica un utilizator și prietenii acestuia. Fiecare utilizator este tratat ca vârfuri, iar conexiunile care le unesc ca prieteni sunt marginile rețelei. Cu algoritmi bazați pe structura datelor grafice, Facebook sugerează „oameni pe care s-ar putea să-i cunoști” și arată „prieteni comuni”.

3. World wide web

World Wide Web este un exemplu de grafic direcționat. Este, de asemenea, ideea de bază din spatele sistemului de clasare Google. În sistemul World Wide Web, fiecare site web și aplicație web este tratată ca un nod sau vârfuri, iar linkurile de la un site la altul sunt considerate margine.

4. Sistem de operare

Sistemul de operare este un caz popular de grafice de alocare a resurselor care utilizează fiecare proces și resursă ca noduri sau vârfuri. Apar margini între resurse la procesul alocat sau de la procesul de solicitare la resursele solicitate. Uneori, acest ciclu poate forma o buclă infinită, inițialând blocajul.

5. Sistemul de cartografiere

GPS-ul dvs. este un caz popular de grafice pentru a localiza restaurantele, magazinele și locurile în care alegeți să căutați cu ajutorul acestei tehnologii.

6. Microsoft Excel

Graficele aciclice direcționate sau DAG sunt utilizate în Microsoft Excel.

7. Algoritmul Dijkstra

Algoritmul Dijkstra utilizează structura de date grafică pentru a identifica calea cea mai scurtă între două sau, în unele cazuri, mai mult de două noduri.

8. Rețele de zbor:

Calcularea rețelelor de zbor optimizate este o altă aplicație reală a structurii de date grafice. Dacă considerați aeroporturile ca noduri și rutele ca margini, datele se potrivesc perfect criteriilor graficelor. De aceea, cu ajutorul diverșilor algoritmi îmbunătățiți, se determină cele mai bune rute între două aeroporturi sau noduri.

Acestea sunt diferitele aplicații ale graficelor în structura datelor , utilizate pe tot globul în diverse aplicații și sisteme pentru a organiza și menține buna funcționare a acestora,

Începeți călătoria dvs. ca cercetător de date

Dacă doriți să deveniți un om de știință a datelor și să gestionați datele cu tact folosind diferitele grafice pe care le-am învățat, consultați o gamă largă de cursuri de știință a datelor pe upGrad. Unul dintre cele mai populare cursuri este cursul PG-IIITB despre Data Science , un curs excelent pentru aspiranții și cercetătorii în devenire a datelor pentru a începe!

Iată ce oferă cursul.

• Suport de carieră la 360 de grade din partea experților din industrie și a mentorilor
• Experiență practică cu proiecte industriale și studii de caz detaliate pentru a măsura progresul regulat
• Crearea de rețele cu experți în știința datelor din toate sectoarele, la nivel global

De asemenea, puteți verifica toate celelalte cursuri de upGrad despre Data Science .