Reprezentarea grafurilor

Există mai multe moduri de a reprezenta grafurile, fiecare metodă având avantajele și dezavantajele sale. Unele situații, sau algoritmii pe care vrei să îi execuți cu grafuri ca intrări, necesită un mod de reprezentare, iar alții au nevoie de o reprezentare diferită. Aici vei vedea trei moduri de a reprezenta grafurile.

Vom vedea trei criterii după care alegem metode de reprezentare. Unul ține seama de câtă memorie, sau spațiu, are nevoie fiecare reprezentare. Vom folosi notația asimptotică pentru asta. Da, putem folosi notația asimptotică și pentru altceva decât exprimarea timpului de execuție! Este într-adevăr o metodă de caracterizare a funcțiilor, iar o funcție poate descrie timpul de execuție, cantitatea de spațiu necesar sau o altă resursă. Celelalte două criterii pe care le vom folosi se vor referi la timp. Unul este cât de mult durează pentru a determina dacă o anumită pereche este muchie a grafului. Celălalt este timpul necesar pentru a găsi vecinii unui vârf dat.

Uzual, identificăm nodurile nu după nume (cum ar fi "Audrey," "Boston," sau "pulover") ci după un număr. Mai exact, obișnuim să numerotăm nodurile $|V|$vertical bar, V, vertical bar de la 0 la $|V|-1$vertical bar, V, vertical bar, minus, 1. Iată graful rețelei sociale cu cele 10 vârfuri identificate prin numere, în loc de nume:

O metodă simplă de reprezentare a grafurilor o reprezintă lista sau vectorul cu $|E|$vertical bar, E, vertical bar muchii; o vom referi ca fiind lista muchiilor. Pentru a reprezenta o muchie, avem nevoie doar de o pereche de noduri sau un vector de obiecte conţinând numerele asociate nodurilor incidente muchiei respective. Dacă muchiile au cost, fie adăugăm un al treilea număr (element la vector), fie informaţie suplimentară pentru fiecare obiect, informație care reprezintă costul muchiei. Deoarece fiecare muchie conţine doar două sau trei numere, spaţiul total pentru o listă de muchii este $\Theta(E)$\Theta, left parenthesis, E, right parenthesis. De exemplu, iată cum reprezentăm în JavaScript o listă de muchii pentru graful rețelei sociale:

Listele muchiilor sunt simple, însă atunci când vrem să verificăm dacă o anumită muchie aparține grafului, trebuie să facem o căutare în listă. Dacă muchiile apar în listă fără o anumită ordine, atunci facem o căutare liniară prin $|E|$vertical bar, E, vertical bar muchii. Acum se pune întrebarea: Cum putem organiza o listă a muchiilor astfel încât căutarea unei anumite muchii să aibă timpul $O(\lg E)$O, left parenthesis, \lg, E, right parenthesis? Răspunsul este puțin mai delicat.

Pentru un graf cu $|V|$vertical bar, V, vertical bar noduri, o matrice de adiacență este o matrice de dimensiuni $|V| \times |V|$vertical bar, V, vertical bar, times, vertical bar, V, vertical bar cu elemente 0 și 1, pentru care elementul de pe linia $i$i și coloana $j$j este 1 dacă și numai dacă muchia $(i,j)$left parenthesis, i, comma, j, right parenthesis aparține grafului. Dacă vrem să precizăm costul unei muchii, vom atribui ca valoare a elementului de pe linia $i$i și coloana $j$j chiar acel cost sau o valoare specială (poate null) dacă nu există în graf acea muchie. Iată matricea de adiacență pentru graful rețelei sociale:

În JavaScript, reprezentăm această matrice prin:

Cu o matrice de adiacenţă, putem afla în timp constant dacă o muchie aparține grafului, prin simpla căutare în matrice a valorii corespunzătoare. De exemplu, dacă matricea de adiacență se numeşte graph, atunci putem verifica dacă muchia $(i,j)$left parenthesis, i, comma, j, right parenthesis aparține grafului uitându-ne la graph[i][j]. Așadar, care este dezavantajul unei matrice de adiacență? De fapt, sunt două. În primul rând, necesită $\Theta(V^2)$\Theta, left parenthesis, V, squared, right parenthesis spațiu, chiar dacă graful este rar: relativ puține muchii. Cu alte cuvinte, pentru un graf rar, matricea de adiacență are în cea mai mare parte valori 0 și folosim mult spațiu pentru a reprezenta doar câteva muchii. În al doilea rând, dacă vrem să aflăm vârfurile adiacente unui anumit nod $i$i, trebuie să analizăm toate $|V|$vertical bar, V, vertical bar valorile de pe linia $i$i, chiar dacă doar puține noduri sunt adiacente cu nodul $i$i.

Pentru un graf neorientat, matricea de adiacenţă este simetrică: Elementul de pe linia $i$i și coloana $j$j este 1 dacă și numai dacă elementul de pe linia $j$j și coloana $i$i este 1. Pentru un graf orientat, matricea de adiacenţă nu este neapărat simetrică.

Reprezentarea unui graf prin liste de adjacență presupune combinarea matricelor de adiacență cu liste de muchii. Pentru fiecare vârf $i$i, memorăm vectorul de vârfuri adiacente acestuia. De obicei, avem un vector cu $|V|$vertical bar, V, vertical bar liste de adiacență, câte o listă de adiacență pentru fiecare vârf. Iată o reprezentare cu o listă de adiacență a grafului rețelei sociale:

În JavaScript, reprezentăm aceste liste de adiacență prin:

Numerele nodurilor într-o listă de adiacență nu necesită o anumită ordine, dar de de multe ori este convenabil să le enumerăm în ordine crescătoare, ca în acest exemplu.

Putem ajunge la fiecare nod din lista de adiacență în timp constant, deoarece trebuie doar să parcurgem vectorul. Pentru a verifica dacă o muchie $(i,j)$left parenthesis, i, comma, j, right parenthesis aparține grafului, mergem la lista de adiacență a lui $i$i și-l căutăm pe $j$j în listă. Cât durează în cel mai defavorabil caz? Răspunsul este $\Theta(d)$\Theta, left parenthesis, d, right parenthesis, unde $d$d este gradul nodului $i$i, deoarece aceasta este lungimea listei de adiacență a lui $i$i. Gradul nodului $i$i poate să fie cel mult $|V|-1$vertical bar, V, vertical bar, minus, 1 (dacă $i$i este adiacent la toate celelalte $|V|-1$vertical bar, V, vertical bar, minus, 1 noduri) sau chiar egal cu 0 (dacă $i$i este izolat, fără muchii incidente). Într-un graf neorientat, nodul $j$j este în lista de adiacență a nodului $i$i dacă și numai dacă $i$i este în lista de adiacență a lui $j$j. Dacă graful este ponderat, atunci fiecare item din fiecare listă de adiacență este fie o pereche, fie un obiect, care conțin numărul nodului și costul muchiei.

Putem folosi o repetiție for pentru a parcurge nodurile dintr-o listă de adiacență. De exemplu, presupunem că avem o listă de adiacență a unui graf în variabila graph, astfel încât graph[i] este vectorul cu vecinii nodului $i$i. Atunci, pentru a apela funcţia doStuff pentru fiecare nod adiacent cu nodul $i$i, am putea folosi următorul cod JavaScript:

Dacă te încurcă notația cu doi indici, atunci poți gândi astfel:

Cât spațiu ocupă listele de adjacență? Avem $|V|$vertical bar, V, vertical bar liste și, deși fiecare listă ar putea avea până la $|V| -1$vertical bar, V, vertical bar, minus, 1 vârfuri, listele de adjacență pentru un graf neorientat conțin în total $2|E|$2, vertical bar, E, vertical bar elemente. De ce $2|E|$2, vertical bar, E, vertical bar? Fiecare muchie $(i,j)$left parenthesis, i, comma, j, right parenthesis apare exact de două ori în listele de adiacenţă: o dată în lista lui $i$i și o dată în lista lui $j$j. Sunt $|E|$vertical bar, E, vertical bar muchii. Pentru un graf orientat, listele de adiacență conțin $|E|$vertical bar, E, vertical bar elemente în total, câte un element pentru fiecare muchie orientată.

Acest conținut este o colaborare a profesorilor Thomas Cormen și Devin Balkcom, de la Dartmouth Computer Science, cu echipa de elaborare a curriculumului de informatică a Khan Academy. Conținutul este licențiat CC-BY-NC-SA.