Structura datelor grafice

Cuprins

Terminologie grafică
Reprezentarea graficului
Operații grafice

În acest tutorial, veți afla ce este o structură de date grafice. De asemenea, veți găsi reprezentări ale unui grafic.

O structură de date grafice este o colecție de noduri care au date și sunt conectate la alte noduri.

Să încercăm să înțelegem acest lucru printr-un exemplu. Pe facebook, totul este un nod. Aceasta include Utilizator, Fotografie, Album, Eveniment, Grup, Pagină, Comentariu, Poveste, Video, Link, Notă … orice are date este un nod.

Fiecare relație este o margine de la un nod la altul. Indiferent dacă postați o fotografie, vă alăturați unui grup, cum ar fi o pagină etc., se creează o nouă margine pentru relația respectivă.

Exemplu de structură a datelor grafice

Tot Facebook este apoi o colecție de aceste noduri și margini. Acest lucru se datorează faptului că Facebook folosește o structură de date grafice pentru a stoca datele sale.

Mai precis, un grafic este o structură de date (V, E) care constă din

O colecție de vârfuri V
O colecție de margini E, reprezentate ca perechi ordonate de vârfuri (u, v)

Vârfuri și margini

În grafic,

 V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)

Terminologie grafică

Adiacență : se spune că un vârf este adiacent unui alt vârf dacă există o margine care le conectează. Vârfurile 2 și 3 nu sunt adiacente, deoarece nu există margine între ele.
Calea : o secvență de margini care vă permite să mergeți de la vârful A la vârful B se numește cale. 0-1, 1-2 și 0-2 sunt căi de la vârful 0 la vârful 2.
Grafic direcționat : un grafic în care o margine (u, v) nu înseamnă neapărat că există și o margine (v, u). Marginile dintr-un astfel de grafic sunt reprezentate de săgeți pentru a arăta direcția marginii.

Reprezentarea graficului

Graficele sunt reprezentate în mod obișnuit în două moduri:

1. Matricea de adiacență

O matrice de adiacență este o matrice 2D de vârfuri V x V. Fiecare rând și coloană reprezintă un vârf.

Dacă valoarea oricărui element a(i)(j)este 1, înseamnă că există o margine care leagă vârful i și vârful j.

Matricea de adiacență pentru graficul pe care l-am creat mai sus este

Matricea de adiacență a graficului

Deoarece este un grafic nedirecționat, pentru muchia (0,2), trebuie să marcăm și muchia (2,0); făcând matricea de adiacență simetrică față de diagonală.

Căutarea muchiilor (verificarea dacă există o margine între vârful A și vârful B) este extrem de rapidă în reprezentarea matricei de adiacență, dar trebuie să rezervăm spațiu pentru fiecare legătură posibilă între toate vârfurile (V x V), deci necesită mai mult spațiu.

2. Lista adiacenței

O listă de adiacență reprezintă un grafic ca o serie de liste legate.

Indexul matricei reprezintă un vârf și fiecare element din lista sa legată reprezintă celelalte vârfuri care formează o margine cu vârful.

Lista adiacenței pentru graficul pe care l-am făcut în primul exemplu este după cum urmează:

Reprezentarea listei de adiacență

O listă de adiacență este eficientă în ceea ce privește stocarea, deoarece trebuie să stocăm doar valorile pentru margini. Pentru un grafic cu milioane de vârfuri, acest lucru poate însemna mult spațiu salvat.