Structura datelor grafice și Algorithms (Exemplu)
Sarah Chen
⚡ Rezumat inteligent
Structura de date a unui graf este o colecție neliniară de vârfuri și muchii, unde fiecare muchie leagă o pereche de vârfuri. Grafurile modelează rețele din lumea reală, cum ar fi hărți, conexiuni sociale și pagini web, și suportă mulți algoritmi puternici.
Ce este un grafic în structura datelor?
Un graf este o structură de date neliniară constă din vârfuri și muchii, unde vârfurile conțin informațiile sau datele, iar muchiile funcționează ca o legătură între o pereche de vârfuri.
Este folosit pentru a rezolva probleme din lumea reală, cum ar fi găsirea celei mai bune rute către locația de destinație și a rutei pentru telecomunicații și rețele sociale. Utilizatorii sunt considerați un nod în Graf, iar firele sunt muchiile care conectează utilizatorii.
Dacă muchiile sunt reprezentate ca E și vârfurile sunt reprezentate ca V, atunci graficul G poate fi scris ca mulțime de vârfuri și muchii, cum ar fi G (V, E).
Exemplu de grafic în structura datelor
Iată un exemplu simplu de structură de date de tip graf:
Este un graf simplu neorientat (un tip de graf). Aici, mulțimea vârfurilor este: {A, B, C, D, E, F}. Două vârfuri creează o muchie. De exemplu, A și B sunt legate printr-o muchie. Cu toate acestea, A și F nu sunt legate de nicio muchie.
Terminologii grafice în structura datelor
Următorii sunt câțiva termeni importanți utilizați în structura de date a grafului:
| Termen | Descriere |
|---|---|
| Culme | Fiecare element de date se numește vârf sau nod. În imaginea de mai sus, A, B, C, D și E sunt vârfurile. |
| Marginea (Arc) | Legăturile dintre două noduri sau vârfuri se numesc muchie (arc). Aceasta are două capete și este reprezentată ca (vârfDeÎnceput, VârfDeFinal). |
| Marginea nedirecționată | Este o margine bidirecțională. |
| Marginea Dirijată | Este o margine unidirecțională. |
| Marginea ponderată | O margine cu valoare pe ea. |
| Grad | Într-un graf, numărul de muchii conectate la un vârf se numește grad. |
| Indegree | Numărul total de muchii de intrare conectate la un vârf. |
| Outdegree | Numărul total de muchii de ieșire conectate la un vârf. |
| Auto-buclă | O muchie se numește auto-buclă dacă cele două puncte finale coincid. |
| Adiacenta | Vârfurile se spun adiacente dacă între ele există o muchie conectată. |
Tipuri de grafice în structura datelor
Iată lista celor mai comune tipuri de grafice din structura datelor:
- Graficul Dirijat
- Grafic nedirecționat
- Graficul ponderat
- Grafic bidirecțional
- Grafic infinit
- Grafic nul
- Grafic trivial
- Grafic multiplu
- Graficul complet
- Graficul conectat
- Graficul ciclic
- Grafic aciclic direcționat (DAG)
- Graficul ciclului
- Graficul bipartit
- Graficul Euler
- Graficul Hamilton
Cum se reprezintă un graf în structura datelor?
Un grafic este de obicei stocat în memorie folosind una dintre cele două reprezentări. Alegerea afectează câtă memorie utilizează graficul și cât de repede se execută operațiile comune.
- Matricea adiacentei: Un tablou bidimensional V × V unde celula [i][j] este 1 (sau ponderea muchiei) dacă există o muchie între vârful i și vârful j și 0 în caz contrar. Permite căutarea muchiilor O(1), dar folosește spațiul O(V²), fiind ideal pentru grafuri dense.
- Listă de adiacență: O matrice de liste în care fiecare vârf stochează o listă cu vârfurile sale vecine. Folosește spațiul O(V + E) și este eficient pentru grafurile rare, motiv pentru care majoritatea grafurilor din lumea reală o utilizează.
Puteți citi mai multe despre acestea în lista de adiacență și reprezentarea matricială a unui graf tutorial.
Aplicații ale structurii de date grafice
Un graf are multe cazuri de utilizare. Există mulți algoritmi care utilizează grafuri. Iată câteva dintre aplicațiile grafurilor:
- Google Hărțile folosesc grafice pentru a găsi intersecția a două drumuri și a calcula distanța dintre două locații. De exemplu, dijkstra, pentru a găsi cea mai scurtă distanță dintre locația sursă și cea de destinație.
- Facebook folosește grafuri pentru a găsi prietenii comuni ai utilizatorilor. Algoritmul său consideră fiecare utilizator ca un nod al unui graf.
- Pentru alocarea resurselor, se utilizează un DAG (Directed Acyclic Graph - Grafic Aciclic Direcționat). Acesta verifică dependența resurselor.
- Google Motoarele de căutare folosesc grafice pentru a crea clasamentul site-urilor web.
- O hartăping Dispozitivul utilizează structura de date grafică.
- A Router iar protocolul său folosește Graful pentru a învăța calea către destinație.
