Cunoașteți structurile de date pe care le utilizați în fiecare zi

👋 Bine ai venit! Să începem cu un context vital. Lasa-ma sa te intreb ceva:
✅ Folosiți Căutarea Google?
✅ Folosiți Google Maps?
✅ Folosiți site-uri de socializare?

Dacă răspunsul dvs. este „da” la oricare dintre aceste întrebări, atunci cu siguranță ați folosit grafice și nici nu le știați! Uimit? 😲 Si eu am fost! Acest articol vă va oferi o introducere vizuală în lumea graficelor, scopul, elementele și tipurile acestora.

Aceste structuri de date mi-au atras într-adevăr atenția datorită capacităților lor uimitoare. Sunt atât de puternici încât nici nu vă veți imagina cât de diverse pot fi aplicațiile lor din lumea reală. Sa incepem! 😁

🌐 Aplicații din lumea reală – începe magia!

Structuri de date 101 Grafice O introducere vizuala pentru

Graficele sunt utilizate în diverse industrii și domenii:

  • Sisteme GPS și Google Maps utilizați grafice pentru a găsi cea mai scurtă cale de la o destinație la alta.
  • Retele sociale utilizați grafice pentru a reprezenta conexiunile dintre utilizatori.
  • Căutarea Google algoritmul utilizează grafice pentru a determina relevanța rezultatelor căutării.
  • Cercetări operaționale este un câmp care utilizează grafice pentru a găsi calea optimă pentru a reduce costurile de transport și livrare a bunurilor și serviciilor.
  • Chiar și chimie folosește grafice sa reprezinte molecule !!! ❤️

Aplicațiile lor sunt uimitoare, nu?
Să începem călătoria noastră prin această lume! 😄

🔵 Întâlnește grafice!

Acum, că aveți un anumit context, să începem prin a vorbi despre scopul și elementele lor principale.

Graficele sunt folosite pentru a reprezenta, găsi, analiza și optimiza conexiunile dintre elemente (case, aeroporturi, locații, utilizatori, articole etc.).

Acesta este un exemplu de cum arată un grafic:

1611329949 178 Structuri de date 101 Grafice O introducere vizuala pentru
Grafic.

💠 Blocuri de construcție

Sunt sigur că ați observat două elemente principale în diagrama de mai sus: cercuri și linii groase care le leagă. Ele sunt numite, respectiv, Noduri și Margini.

1611329950 972 Structuri de date 101 Grafice O introducere vizuala pentru

Să le vedem mai detaliat! 👍

  • Noduri: ei sunt elemente care creează rețeaua. Ei ar putea reprezenta case, locații, aeroporturi, porturi, stații de autobuz, clădiri, utilizatori, practic orice ai putea reprezenta ca fiind conectat la alte elemente similare dintr-o rețea.
  • Margini: sunt conexiuni între noduri. Ei ar putea reprezenta străzi, zboruri, rute de autobuz, o conexiune între doi utilizatori într-o rețea socială, sau orice altceva care ar putea reprezenta o conexiune între noduri în contextul cu care lucrați.

😱 Ce se întâmplă dacă nu există conexiune?

Dacă două noduri nu sunt conectate printr-o margine, asta înseamnă că există nicio legătură directă între ele. Dar nu intra în panică! 😩 S-ar putea să puteți merge în continuare de la un nod la altul până la furmând o succesiune de margini, similar cu conducerea pe mai multe străzi pentru a ajunge la destinația finală. 🚛️ 🚛 🚛

De exemplu, în diagrama de mai jos, chiar dacă nu există direct conexiune (margine) între nod violet (stânga) și nod galben (dreapta), puteți merge de la nodul purpuriu la nodul portocaliu, la nodul roz, la nodul verde și, în cele din urmă, ajungeți la nodul galben. 🏁

1611329950 33 Structuri de date 101 Grafice O introducere vizuala pentru
Nu există conexiune directă între nodul violet și galben.

Acesta este un aspect cheie al graficelor, pe care îl puteți căutați elementul pe care îl căutați urmând căile disponibile.

🌟 Notare și terminologie

Este foarte important să învățați „limbajul” formal pentru a lucra cu grafice:

  • |V| = Total numărul de vârfuri (noduri) în grafic.
  • |E| = Total numărul de conexiuni (margini) în grafic.

În exemplul de mai jos, |V| = 6 deoarece există șase noduri (cercuri) și
|E| = 7 deoarece există șapte margini (linii).

1611329950 903 Structuri de date 101 Grafice O introducere vizuala pentru
Grafic.

📚 Tipuri de grafice

Graficele sunt clasificate pe baza caracteristicilor marginilor (conexiunilor) lor. Să le aruncăm o privire în detaliu! 😃

1️⃣ Grafice regizate

În graficele direcționate, muchiile au o direcție. Ele merg de la un nod la altul și nu există nicio modalitate de a reveni la nodul inițial prin marginea respectivă.

După cum puteți vedea în diagrama de mai jos, marginile (conexiunile) au acum săgeți care indică o direcție specifică. Gândiți-vă la aceste margini ca la străzi cu sens unic. Puteți merge într-o singură direcție și ajunge la destinație, dar nu vă puteți întoarce pe aceeași stradă, deci trebuie să găsiți o cale alternativă.

1611329950 525 Structuri de date 101 Grafice O introducere vizuala pentru
Grafic regizat.

🍕 De exemplu, dacă creăm un grafic pentru un serviciu de livrare a pizza, reprezentând un oraș, pot fi două case (noduri) conectate printr-o stradă cu sens unic (margine). Puteți ajunge de la casa A la casa B prin această stradă, dar nu vă puteți întoarce, așa că ar trebui să luați o cale alternativă.

1611329951 377 Structuri de date 101 Grafice O introducere vizuala pentru

💡 Notă: Într-un grafic direcționat, yeste posibil să nu vă puteți întoarce deloc la locația dvs. inițială if nu există o cale cu direcțiile corespunzătoare. 😞 În diagrama de mai jos, puteți vedea că puteți trece cu succes de la nodul purpuriu la nodul verde, dar observați că nu există nicio modalitate de a reveni de la nodul verde la nodul purpuriu deoarece marginile sunt „străzi cu sens unic. ”

1611329951 304 Structuri de date 101 Grafice O introducere vizuala pentru
Punct fără întoarcere.

2️⃣ Grafice nedirecționate

În acest tip de grafic, muchiile sunt nedirecționate (nu au o direcție specifică). Gândiți-vă la marginile nedirecționate ca la străzi cu două sensuri. Puteți merge de la un nod la altul și reveniți prin aceeași „cale”.

💡 Notă: Când vedeți o diagramă a unui grafic în care marginile nu au săgeți îndreptate într-o anumită direcție, puteți presupune că graficul nu este direcționat.

1611329951 81 Structuri de date 101 Grafice O introducere vizuala pentru

🍕 Pentru serviciul nostru de livrare a pizza, acest lucru ar însemna că motocicleta de livrare poate merge de la sursă la destinație prin aceeași stradă sau cale (Spre ușurarea lor! 😇).

1611329951 828 Structuri de date 101 Grafice O introducere vizuala pentru

În graficul de mai jos, ați putea merge de la nodul purpuriu la nodul verde și înapoi prin aceeași cale, astfel încât să nu ajungeți la un punct fără întoarcere. 😌

1611329952 583 Structuri de date 101 Grafice O introducere vizuala pentru
Vă puteți întoarce!

🏋 Greutăți? – Da, greutăți!

1️⃣ Grafice ponderate

În graficele ponderate, fiecare margine are o valoare asociată (numită greutate). Această valoare este utilizată pentru a reprezenta o anumită relație cuantificabilă între nodurile pe care le conectează.

De exemplu, greutățile ar putea reprezenta distanța, timpul, numărul de conexiuni partajate între doi utilizatori într-o rețea socială, sau orice altceva care ar putea fi folosit pentru a descrie conexiunea dintre noduri în contextul cu care lucrați.

1611329952 447 Structuri de date 101 Grafice O introducere vizuala pentru
Grafic ponderat.

Aceste greutăți sunt folosite de Algoritmul lui Dijkstra pentru a optimiza traseele găsind cele mai scurte sau mai puțin costisitoare căi între noduri dintr-o rețea. (Rămâneți la curent cu un articol despre Algoritmul lui Dijkstra! 😃).

2️⃣ Grafice neponderate

În schimb, graficele neponderate nu au greutăți asociate cu marginile lor. Un exemplu al acestui tip de grafic poate fi găsit în rețelele de socializare, unde marginile reprezintă conexiunea dintre doi utilizatori. Conexiunea nu poate fi cuantificată. Prin urmare, marginea nu are greutate.

1611329952 717 Structuri de date 101 Grafice O introducere vizuala pentru
Grafic neponderat.

💡 Notă: Este posibil să fi observat că, până acum, graficele noastre au o singură margine care leagă fiecare pereche de noduri. Este firesc să ne întrebăm dacă ar putea exista mai multe margini între o pereche de noduri. Ade fapt, acest lucru este posibil cu Multigrafii! Thei, poate avea mai multe margini care conectează aceeași pereche de noduri.

1611329952 730 Structuri de date 101 Grafice O introducere vizuala pentru
Multigraf.

🏆 Numărul de muchii! – Un factor important

Este foarte important să știți dacă un grafic are multe sau câteva margini, deoarece acesta este un factor crucial pentru a decide cum veți reprezenta această structură de date în codul dvs. Să vedem diferitele tipuri! 👍

1️⃣ Grafice dense

Graficele dense au multe muchii. Dar asteapta! ⚠️ Știu la ce trebuie să vă gândiți, cum puteți determina ce se califică drept „multe margini”? Este puțin subiectiv, nu? 😇 Sunt de acord cu tine, așa că hai să-l cuantificăm puțin:

👉 Să găsim numărul maxim de muchii într-un grafic direcționat. Dacă există |V| noduri într-un grafic direcționat (în exemplul de mai jos, șase noduri), ceea ce înseamnă că fiecare nod poate avea până la |v| conexiuni (în exemplul de mai jos, șase conexiuni).

De ce? pentru că fiecare nod s-ar putea conecta potențial cu toate celelalte noduri și cu el însuși (vezi „bucla” de mai jos). Prin urmare, numărul maxim de margini pe care le poate avea graficul este |V|*|V| , care este numărul total de noduri înmulțit cu numărul maxim de conexiuni pe care le poate avea fiecare nod.

Când numărul de muchii din grafic este aproape de numărul maxim de margini, graficul este dens. 😉

1611329953 798 Structuri de date 101 Grafice O introducere vizuala pentru
Grafic.

💡 Notă: „Buclele” apar atunci când un nod are o margine care îl conectează la el însuși. Ciudat și interesant, nu? 😄

1611329953 445 Structuri de date 101 Grafice O introducere vizuala pentru
Reprezentare „buclă”.

2️⃣ Grafice rare

Graficele rare au câteva margini. După cum puteți vedea în diagrama de mai jos, nu există multe conexiuni între noduri.

Când numărul de muchii din grafic este semnificativ mai mic decât numărul maxim de margini, graficul este rar. 😉

1611329953 954 Structuri de date 101 Grafice O introducere vizuala pentru
Grafic rar.

⭕️ Faceți cunoștință cu ciclurile!

Acum să vedem un concept vital pentru a înțelege grafice, cicluri.

Probabil ați observat că, dacă urmați o succesiune de conexiuni într-un grafic, este posibil să găsiți un cale care vă va duce înapoi la același nod. Este ca și cum ai „umbla în cercuri”, exact ca și cum ai fi condus în jurul orașului tău și ai fi luat o cale care te-ar putea duce înapoi la locația inițială.

În grafice, aceste căi „circulare” sunt numite „cicluri”. Sunt căi valide care încep și se termină la același nod. De exemplu, în diagrama de mai jos, puteți vedea că, dacă începeți de la orice nod, puteți reveni la același nod urmând marginile.

1611329953 935 Structuri de date 101 Grafice O introducere vizuala pentru
Ciclul probei.

Ciclurile nu sunt întotdeauna „izolate”, deoarece pot face parte dintr-un grafic mai mare. Le puteți detecta începând căutarea pe un anumit nod și găsind o cale care vă duce înapoi la același nod.

1611329954 953 Structuri de date 101 Grafice O introducere vizuala pentru
Ciclează într-un grafic.

👋 În rezumat …

  • Graficele sunt structuri de date minunate pe care îl utilizați în fiecare zi prin Căutarea Google, Google Maps, GPS și rețelele sociale.
  • Sunt obișnuiți reprezintă elemente care partajează conexiuni.
  • Elementele din grafic se numesc Noduri iar conexiunile dintre ele se numesc Margini.
  • Graficele pot fi regizat, atunci când marginile lor au o orientare specifică, similară cu străzile cu sens unic sau nedirectat, atunci când marginile lor nu au o orientare specifică, similară străzilor cu sens dublu.
  • Marginile pot avea o valoare asociată cu ele, numită greutate.
  • Dacă un grafic are multe muchii, se numește a dens grafic. În caz contrar, dacă are câteva margini, se numește a rar grafic.
  • O serie de conexiuni pot forma un ciclu dacă creează o cale care vă permite să reveniți la același nod.

Continuați să aflați despre aceste structuri de date uimitoare! Va merita total pentru viitorul dvs. ca dezvoltator. Învăț despre structurile de date chiar acum și le găsesc complet fascinante. 😃 🎆 ❤️

Important este să nu încetăm să punem întrebări. Curiozitatea are propriul motiv pentru care există. – Albert Einstein

👋 Mulțumesc!

Sper cu adevărat că ți-a plăcut articolul meu. ❤️
Urmărește-mă Stare de nervozitate. 😃