Salutare tuturor.
În această notă, am decis să enumăr principalele structuri de date utilizate pentru stocarea grafurilor în informatică, precum și să discut despre câteva alte structuri care, într-un fel, au „cristalizat” în mintea mea.
Așadar, să începem. Dar nu de la început – cred că știm deja ce este un grafic și ce tipuri există (dirijate, nedirijate, cu greutate, fără greutate, cu arce multiple și bucle sau fără ele).
Așadar, să vedem. Ce opțiuni de structuri de date pentru „stocarea graficului” avem.
1. Structuri matriciale de date
1.1 Matricea de adiacență. Matricea de adiacență este o matrice în care anteturile rândurilor și coloanelor corespund numerelor vârfurilor graficului, iar valoarea fiecărui element a(i,j) se determină prin prezența sau absența arcelor între vârfurile i și j (este evident că pentru un grafic nedirijat această matrice va fi simetrică, sau putem conveni că toate valorile le stocăm doar deasupra diagonalei principale). Pentru grafurile nedirijate, a(i,j) poate fi definit ca numărul de arce din i în j (dacă nu există astfel de arc, atunci a(i,j)= 0), iar pentru grafurile cu greutate – prin greutatea (greutatea totală) arcelor menționate.
1.2 Matricea de incidență. În acest caz, graficul nostru este de asemenea stocat într-un tabel, în care, de obicei, numerelor rândurilor le corespund numerele vârfurilor, iar numerelor coloanelor – arcele numerotate anterior. Dacă un vârf și un arc sunt incidente unul altuia, atunci în celula corespunzătoare se înregistrează o valoare nenulă (pentru grafurile nedirijate se scrie 1 în caz de incidență a vârfului și arcului, pentru cele dirijate – „1” dacă arc „iese” din vârf și „-1” dacă acesta „intră” în vârf (e suficient de ușor de reținut, deoarece semnul „minus” pare să „înceapă” în numărul „-1”)). Pentru grafurile cu greutate, din nou, în loc de 1 și -1, putem indica greutatea totală a arcului.
2. Structuri de date enumerative
2.1 Lista de adiacență. Aici, aparent, totul este simplu. Fiecărei vârfului grafului i se poate, în linii mari, asocia orice structură enumerativă (listă, vector, tabel, …), în care vor fi stocate numerele tuturor vârfurilor adiacente acestuia. Pentru grafurile orientate, vom înregistra în această listă doar acele vârfuri pentru care există o arie «direcționată» din vârful-ființă. Pentru grafurile ponderate, implementarea va fi mai complexă.
2.2 Lista arcelor. O structură de date destul de populară. Lista arcelor, așa cum ne sugerează Căpitanul Evident, reprezintă, de fapt, lista arcelor grafului, fiecare dintre acestea fiind definită prin vârful de început, vârful de sfârșit (la grafurile neorientate, aici ordinea nu este importantă, deși pentru unificare se pot folosi diverse reguli, de exemplu, indicând vârfurile în ordine crescătoare) și greutatea (numai pentru grafurile ponderate).
O descriere mai detaliată despre listele-matrix enumerate mai sus poate fi găsită, de exemplu, .
2.3 Tabelul de adiacență. Nu este o structură întâlnită foarte des. În esență, ea reprezintă o formă de «împachetare» a listelor de adiacență într-o structură enumerativă (tabel, vector). Primele n (conform numărului de vârfuri ale grafului) elemente ale acestui tabel conțin indecșii de început ai aceluiași tabel, începând de la care sunt înregistrați în mod consecutiv toți vârfurile adiacente acestuia.
Aici am găsit cea mai clară (pentru mine) explicație:
3. Vectorul de adiacență și Tabelul asociativ de adiacență
A ieșit așa, încât autorul acestor rânduri, nefiind un programator profesionist, dar având ocazional de-a face cu grafurile, s-a ocupat cel mai des de listele arcelor. Este, cu adevărat, convenabil dacă în graf există bucle multiple și arce. Și astfel, în dezvoltarea listelor clasice de arce, propun să acordăm atenție și „dezvoltării/sărbătoririi/modificării/mutației” acestora, și anume: vectorului de adiacență și tabelului asociativ de adiacență.
3.1 Vectorul de adiacență
Caz (a1): graf neponderat
Vom numi vector de adiacență pentru un graf neponderat un set ordonat de un număr par de numere întregi (a[2i], a[2i+1],…, unde i este numerotat de la 0), în care fiecare pereche de numere a[2i], a[2i+1] definește un arc al grafului între vârfurile a[2i] și a[2i+1].
Acest format de înregistrare nu conține informații despre faptul că graful este orientat (sunt posibile ambele variante). Atunci când se folosește formatul pentru un graf orientat, se consideră că o muchie este direcționată din a[2i] în a[2i+1]. Aici și mai departe: pentru grafuri neorientate, se pot aplica cerințe privind ordinea înregistrării vârfurilor (de exemplu, pentru ca primul să fie vârful cu valoarea mai mică a numărului său atribuit).
În C++, vectorul de adiacență se recomandă a fi definit folosind std::vector, de aici și numele acestei structuri de date.
Cazul (a2): graf negreu, greutățile muchiilor sunt întregi.
În mod analog cu cazul (a1), vom numi vector de adiacență pentru un graf greu cu greutăți întregi un set ordonat (matrice dinamică) de numere (a[3i], a[3i+1], a[3i+2],…, unde i este numerotat de la 0), unde fiecare "triplet" de numere a[3i], a[3i+1], a[3i+2] definește o muchie a grafului între vârful cu numărul a[3i] și vârful cu numărul a[3i+1], iar valoarea a[3i+2] este greutatea acestei muchii. Acest graf poate fi, de asemenea, orientat sau nu.
Cazul (b): graf negreu, greutățile muchiilor nu sunt întregi.
Având în vedere că într-un singur tablou (vector) nu se pot stoca elemente heterogene, este posibil, de exemplu, următoarea implementare. Grafurile sunt stocate într-o pereche de vectori, în care primul vector este un vector de adiacență al grafului fără indicarea greutăților, iar al doilea vector conține greutățile corespunzătoare (o posibilă implementare pentru C++: std::pair). Astfel, pentru o muchie definită de o pereche de vârfuri la indecșii 2i, 2i+1 din primul vector, greutatea va fi egală cu elementul de la indexul i din al doilea vector.
Dar de ce este nevoie de asta?
Ei bine, autorului acestor rânduri i s-a părut suficient de util pentru a rezolva o serie de sarcini. Iar dintr-un punct de vedere formal, vor exista următoarele avantaje:
- Vectorul de adiacență, ca orice altă structură "enumerativă", este destul de compact, ocupă mai puțin memorie decât matricea de adiacență (pentru grafuri sparse), și se implementează relativ simplu.
- Vârfurile grafului, în principiu, pot fi marcate și cu numere negative. Poate că va fi nevoie și de un astfel de "exces".
- Grafurile pot conține muchii multiple și bucle multiple, fiecare având greutăți diferite (pozitive, negative, chiar și zero). Nu există nicio restricție în acest sens.
- De asemenea, muchiilor li se pot atribui diferite proprietăți – dar despre asta vezi pct. 4.
Cu toate acestea, trebuie să recunoaștem că accesul rapid la o muchie nu este prevăzut de această „listă”. Și aici vine în ajutor un Aranjament asociativ de adiacență, despre care vom vorbi mai jos.
3.2 Aranjament asociativ de adiacență
Așadar, dacă pentru noi accesul la o anumită muchie, greutatea acesteia și alte proprietăți sunt esențiale, iar cerințele de memorie nu permit utilizarea matricei de adiacență, atunci să ne gândim cum am putea modifica vectorul de adiacență pentru a rezolva această problemă. Așadar, cheia este o muchie a grafului, care poate fi definită ca o pereche ordonată de numere întregi. La ce se aseamănă asta? Oare nu este cheia unui aranjament asociativ? Și, dacă da, de ce să nu o implementăm? Să presupunem că avem un astfel de aranjament asociativ, în care fiecărei chei – perechei ordonate de numere întregi – îi va fi atribuit un valoare – un număr întreg sau real, care definește greutatea muchiei. În C++, implementarea acestei structuri este fezabilă pe baza containerului std::map (std::map <std::pair , int> sau std::map <std::pair , double>), sau std::multimap, dacă se prezintă multiple muchii. Așadar, am obținut o structură pentru stocarea graficelor, care ocupă mai puțin memorie decât structurile „matriceale”, poate defini grafice cu bucle și muchii multiple și nu are cerințe stricte pentru pozitivitatea numerelor de vârf (nu știu cine ar avea nevoie de asta, dar totuși).
4. Structuri de date tot „umplute”, dar lipsește ceva
Și într-adevăr: în rezolvarea unei serii de probleme, putem avea nevoie să atribuim muchiilor grafului anumite caracteristici și, prin urmare, să le stocăm. Dacă aceste caracteristici pot fi reduse în mod univoc la numere întregi, atunci este posibil să stocăm astfel de „grafuri cu caracteristici suplimentare” folosind versiuni extinse ale vectorului de adiacență și aranjamentului asociativ de adiacență.
Deci, să presupunem că avem un graf neponderat, pentru fiecare muchie a căruia trebuie să păstrăm, de exemplu, 2 caracteristici suplimentare, definite prin numere întregi. În acest caz, putem defini vectorul său de adiacență ca un set ordonat de nu «perechi», ci «cvartete» de numere întregi (a[2i], a[2i+1], a[2i+2], a[2i+3]…), unde a[2i+2] și a[2i+3] vor determina caracteristicile corespunzătoare ale muchiei. Pentru un graf cu greutăți întregi ale muchiilor, ordinea este, în general, similară (diferența constând doar în faptul că caracteristicile vor urma după greutatea muchiei și vor fi definite de elementele a[2i+3] și a[2i+4], iar muchia va fi definită nu prin 4, ci prin 5 numere ordonate). Iar pentru un graf cu greutăți nenumerice, caracteristicile vor putea fi înregistrate în componenta sa neponderată.
Când se folosește un tablou asociativ de adiacență pentru grafuri cu greutăți întregi ale muchiilor, este posibil ca valoarea să fie definită nu ca un singur număr, ci ca un tablou (vector) de numere, care, pe lângă greutatea muchiei, definește toate celelalte caracteristici necesare. Un dezavantaj în cazul greutăților nenumerice va fi necesitatea de a defini o caracteristică ca un număr cu virgulă mobilă (da, aceasta este o neplăcere, dar dacă nu există atât de multe caracteristici și dacă nu le definim ca double „prea complicate”, atunci poate că nu este atât de rău). Așadar, în C++, tablouri asociative extinse de adiacență pot fi definite astfel: std::map <std::pair , std::vector> sau std::map <std::pair , std::vector>, unde primul element din «vectorul-valoare-pe-cheie» va fi greutatea muchiei, iar celelalte vor fi denumirile numerice ale caracteristicilor sale.
Literatură:
Despre grafuri și algoritmi în general:
1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algoritmi: construcție și analiză, ediția a 2-a: Traducere din engleză – M.: Editura Williams, 2011.
2. Harari Frank. Teoria grafurilor. M.: Mir, 1973.
Prezentarea autorului despre acest vector și tabloul asociativ de adiacență:
3. Chernouhov S.A. Vector de adiacență și hartă de adiacență ca metode de reprezentare și stocare a graficelor / S.A. Chernouhov. Vector de adiacență și hartă de adiacență ca structuri de date pentru a reprezenta un grafic // Colecția de articole a conferinței științifice internaționale „Problemele implementării rezultatelor dezvoltărilor inovatoare și soluțiile acestora” (Saratov, 14.09.2019). – Sterlitamak: AMI, 2019, pp. 65-69
Resurse utile pe internet despre subiect:
4.
5.
Sursa: habr.com
