Buna ziua.
În această notă, am decis să enumerez principalele structuri de date utilizate pentru stocarea graficelor în informatică și voi vorbi și despre câteva astfel de structuri care s-au „cristalizat” cumva pentru mine.
Deci, să începem. Dar nu de la bun început - cred că știm cu toții deja ce este un grafic și ce sunt ele (direcționat, nedirecționat, ponderat, neponderat, cu sau fără margini și bucle multiple).
Deci să mergem. Ce opțiuni pentru structurile de date pentru „stocare grafică” avem?
1. Structuri de date matriceale
1.1 Matricea adiacentei. Matricea de adiacență este o matrice în care titlurile rândurilor și coloanelor corespund numerelor vârfurilor graficului, iar valoarea fiecăruia dintre elementele sale a(i,j) este determinată de prezența sau absența muchiilor între vârfuri. i și j (este clar că pentru un grafic nedirecționat o astfel de matrice va fi simetrică sau putem fi de acord că stocăm toate valorile numai deasupra diagonalei principale). Pentru graficele neponderate, a(i,j) poate fi setat de numărul de muchii de la i la j (dacă nu există o astfel de muchie, atunci a(i,j)= 0), iar pentru graficele ponderate, de asemenea, de pondere (greutatea totală) a marginilor menționate.
1.2 Matricea de incidenta. În acest caz, graficul nostru este stocat și într-un tabel în care, de regulă, numerele rândurilor corespund numerelor vârfurilor sale, iar numerele coloanelor corespund muchiilor pre-numerotate. Dacă un vârf și o muchie sunt incidente unul cu celălalt, atunci o valoare diferită de zero este scrisă în celula corespunzătoare (pentru graficele nedirecționate, se scrie 1 dacă vârful și muchia sunt incidente, pentru graficele orientate - „1” dacă muchia „ieșiri” din vârf și „-1” dacă „include” în el (este destul de ușor de reținut, deoarece semnul „minus” pare să fie și el „inclus” în numărul „-1”). Pentru graficele ponderate, din nou, în loc de 1 și -1, puteți specifica greutatea totală a muchiei.
2. Structuri de date de enumerare
2.1 Lista adiacentei. Ei bine, totul pare să fie simplu aici. Fiecare vârf al graficului poate fi asociat, în general, cu orice structură de enumerare (listă, vector, tablou, ...), care va stoca numerele tuturor vârfurilor adiacente celui dat. Pentru graficele direcționate, vom adăuga la o astfel de listă doar acele vârfuri la care există o margine „direcționată” dintr-un vârf de caracteristică. Pentru graficele ponderate implementarea va fi mai complexă.
2.2 Lista de coaste. O structură de date destul de populară. Lista de muchii, după cum ne spune căpitanul Obviousness, este de fapt o listă de muchii ale graficului, fiecare dintre acestea fiind specificată de vârful de început, vârful de sfârșit (pentru graficele nedirecționate ordinea nu este importantă aici, deși pentru unificare puteți utilizați diverse reguli, de exemplu, specificând vârfurile în ordine crescătoare) și ponderea (numai pentru graficele ponderate).
Puteți consulta listele de matrice enumerate mai sus mai detaliat (și cu ilustrații), de exemplu, .
2.3 Matrice de adiacență. Nu este cea mai comună structură. În esență, este o formă de „împachetare” liste de adiacență într-o singură structură de enumerare (matrice, vector). Primele n (după numărul de vârfuri ale graficului) elemente ale unui astfel de tablou conțin indici de pornire ai aceleiași matrice, începând de la care toate vârfurile adiacente celui dat sunt scrise pe rând.
Aici am găsit cea mai înțeleasă (pentru mine) explicația:
3. Vector de adjacență și matrice de adiacență asociativă
S-a dovedit că autorul acestor rânduri, nefiind un programator profesionist, dar care s-a ocupat periodic de grafice, s-a ocupat cel mai adesea de liste de margini. Într-adevăr, este convenabil dacă graficul are mai multe bucle și muchii. Așadar, în dezvoltarea listelor clasice de muchii, îmi propun să acordăm atenție „dezvoltării/ramificării/modificării/mutației” acestora și anume: vectorul de adiacență și tabloul de adiacență asociativă.
3.1 Vector de adiacență
Cazul (a1): grafic neponderat
Vom numi un vector de adiacență pentru un grafic neponderat o mulțime ordonată a unui număr par de numere întregi (a[2i], a[2i+1],..., unde i este numerotat c 0), în care fiecare pereche de numere este a[2i], a[2i+1 ] specifică o muchie a graficului între vârfurile a[2i] și, respectiv, a[2i+1].
Acest format de înregistrare nu conține informații despre direcționarea graficului (ambele opțiuni sunt posibile). Când se utilizează formatul digraf, muchia este considerată a fi direcționată de la a[2i] la a[2i+1]. Aici și mai jos: pentru graficele nedirecționate, dacă este necesar, pot fi aplicate cerințe pentru ordinea înregistrării nodurilor (de exemplu, ca vârful cu valoarea mai mică a numărului atribuit să fie primul).
În C++, este recomandabil să specificați un vector de adiacență folosind std::vector, de unde și numele acestei structuri de date.
Cazul (a2): grafic neponderat, ponderile marginilor sunt întregi
Prin analogie cu cazul (a1), numim vectorul de adiacență pentru un grafic ponderat cu ponderi de muchii întregi o mulțime ordonată (matrice dinamică) de numere (a[3i], a[3i+1], a[3i+2], ..., unde i este numerotat c 0), unde fiecare „triplet” de numere a[3i], a[3i+1], a[3i+2] specifică o muchie a graficului între vârfurile numerotate a[3i] și respectiv a[3i+1], iar valoarea a [3i+2] este greutatea acestei muchii. Un astfel de grafic poate fi, de asemenea, fie direcționat, fie nu.
Cazul (b): grafic neponderat, greutăți ale muchiilor neîntregi
Deoarece este imposibil să stocați elemente eterogene într-o singură matrice (vector), de exemplu, următoarea implementare este posibilă. Graficul este stocat într-o pereche de vectori, în care primul vector este vectorul de adiacență al graficului fără a specifica greutățile, iar al doilea vector conține greutățile corespunzătoare (implementare posibilă pentru C++: std::pair). ). Astfel, pentru o muchie definită de o pereche de vârfuri sub indicii 2i, 2i+1 ai primului vector, ponderea va fi egală cu elementul sub indicele i al celui de-al doilea vector.
Ei bine, de ce este necesar acest lucru?
Ei bine, autorul acestor rânduri l-a găsit destul de util pentru a rezolva o serie de probleme. Ei bine, din 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 grafice rare) și este relativ ușor de implementat.
- Vârfurile graficului, în principiu, pot fi marcate și cu numere negative. Ce se întâmplă dacă este nevoie de o astfel de „perversie”?
- Graficele pot conține mai multe margini și mai multe bucle, cu greutăți diferite (pozitive, negative, chiar zero). Nu există restricții aici.
- De asemenea, puteți atribui diferite proprietăți muchiilor - dar pentru mai multe despre asta, consultați secțiunea 4.
Cu toate acestea, trebuie să admitem că această „listă” nu implică acces rapid la margine. Și aici vine în ajutor Matricea de Adjacență Asociativă, care este discutată mai jos.
3.2 Matrice de adiacență asociativă
Deci, dacă accesul la o anumită muchie, greutatea acesteia și alte proprietăți sunt critice pentru noi, iar cerințele de memorie nu ne permit să folosim matricea de adiacență, atunci să ne gândim cum putem schimba vectorul de adiacență pentru a rezolva această problemă. Deci, cheia este o margine a graficului, care poate fi specificată ca o pereche ordonată de numere întregi. Cum arată asta? Nu este o cheie într-un tablou asociativ? Și, dacă da, de ce nu o implementăm? Să avem o matrice asociativă în care fiecare cheie - o pereche ordonată de numere întregi - va fi asociată cu o valoare - un număr întreg sau un număr real care specifică greutatea muchiei. În C++, este recomandabil să implementați această structură pe baza containerului std::map (std::map , int> sau std::map , double>), sau std::multimap dacă sunt de așteptat mai multe margini. Ei bine, avem o structură pentru stocarea graficelor care ocupă mai puțină memorie decât structurile „matrice”, poate defini grafice cu mai multe bucle și muchii și nici măcar nu are cerințe stricte pentru non-negativitatea numerelor de vârfuri (nu știu cine are nevoie de asta, dar totuși).
4. Structurile de date sunt pline, dar lipsește ceva
Și este adevărat: atunci când rezolvăm o serie de probleme, este posibil să fie nevoie să atribuim anumite caracteristici marginilor graficului și, în consecință, să le stocăm. Dacă este posibil să reduceți fără ambiguitate aceste caracteristici la numere întregi, atunci este posibil să stocați astfel de „grafice cu caracteristici suplimentare” folosind versiuni extinse ale vectorului de adiacență și ale matricei de adiacență asociativă.
Deci, să avem un grafic neponderat, pentru fiecare muchie a căruia este necesar să stocăm, de exemplu, 2 caracteristici suplimentare specificate prin numere întregi. În acest caz, este posibil să se definească vectorul său de adiacență ca o mulțime ordonată nu de „perechi”, ci de „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 muchiei corespunzătoare. Pentru un grafic cu greutăți întregi ale muchiilor, ordinea este în general similară (singura diferență va fi că atributele vor urma greutatea muchiei și vor fi specificate de elementele a[2i+3] și a[2i+4] , iar marginea în sine va fi specificată nu 4, ci 5 numere ordonate). Și pentru un grafic cu greutăți de margine non-întregi, caracteristicile pot fi scrise în componenta sa neponderată.
Atunci când se utilizează o matrice de adiacență asociativă pentru grafice cu greutăți întregi ale muchiei, este posibil să se specifice ca valoare nu un singur număr, ci un tablou (vector) de numere care specifică, pe lângă greutatea unei muchii, toate celelalte necesare. Caracteristici. În același timp, un inconvenient pentru cazul greutăților care nu sunt întregi va fi necesitatea de a specifica un semn cu un număr în virgulă mobilă (da, acesta este un inconvenient, dar dacă nu există atât de multe astfel de semne și dacă nu nu le setați prea „delicate” duble, atunci poate fi nimic). Aceasta înseamnă că în C++, matricele de adiacență asociativă extinsă pot fi definite după cum urmează: std::map , std::vector> sau std::map , std::vector, în care prima valoare din „cheie-valoare-vector” va fi ponderea marginii, iar apoi sunt localizate denumirile numerice ale atributelor sale.
Literatură:
Despre grafice și algoritmi în general:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmi: construcție și analiză, ediția a II-a: Trad. din engleza – M.: Editura Williams, 2.
2. Harari Frank. Teoria grafurilor. M.: Mir, 1973.
Raportul autorului despre același vector și matrice asociativă de adiacente:
3. Cernouhov S.A. Vector de adiacență și matrice de adiacență asociativă ca modalități de reprezentare și stocare a graficelor / SA Chernouhov. Vector de adiacență și harta de adiacență ca structuri de date pentru a reprezenta un grafic // Culegere de articole ale Conferinței internaționale științifice și practice „Probleme de implementare a rezultatelor dezvoltărilor inovatoare și modalități de rezolvare a acestora” (Saratov, 14.09.2019 septembrie 2019). – Sterlitamak: AMI, 65, p. 69-XNUMX
Surse online utile pe această temă:
4.
5.
Sursa: www.habr.com