Conţinutul principal

Biblioteca de informatică

Curs: Biblioteca de informatică > Unitatea 1

Lecția 8: Reprezentarea grafurilor

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 |

de la 0 la

| V | - 1

. Iată graful rețelei sociale cu cele 10 vârfuri identificate prin numere, în loc de nume:

Lista muchiilor

O metodă simplă de reprezentare a grafurilor o reprezintă lista sau vectorul cu

| E |

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

Θ (E)

. De exemplu, iată cum reprezentăm în JavaScript o listă de muchii pentru graful rețelei sociale:

[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5],
[3,8], [4,5], [4,9], [7,8], [7,9] ]

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 |

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)

? Răspunsul este puțin mai delicat.

Matrice de adiacență

Pentru un graf cu

| V |

noduri, o matrice de adiacență este o matrice de dimensiuni

| V | \times | V |

cu elemente 0 și 1, pentru care elementul de pe linia

i

și coloana

j

este 1 dacă și numai dacă muchia

(i, j)

aparține grafului. Dacă vrem să precizăm costul unei muchii, vom atribui ca valoare a elementului de pe linia

i

și coloana

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:

[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
  [1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
  [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
  [0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
  [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
  [1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
  [0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]

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)

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ă

Θ (V^{2})

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

, trebuie să analizăm toate

| V |

valorile de pe linia

i

, chiar dacă doar puține noduri sunt adiacente cu nodul

i

Pentru un graf neorientat, matricea de adiacenţă este simetrică: Elementul de pe linia

i

și coloana

j

este 1 dacă și numai dacă elementul de pe linia

j

și coloana

i

este 1. Pentru un graf orientat, matricea de adiacenţă nu este neapărat simetrică.

Liste de adiacență

Reprezentarea unui graf prin liste de adjacență presupune combinarea matricelor de adiacență cu liste de muchii. Pentru fiecare vârf

i

, memorăm vectorul de vârfuri adiacente acestuia. De obicei, avem un vector cu

| V |

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:

[ 1, 6, 8],
  [0, 4, 6, 9],
  [4, 6],
  [4, 5, 8],
  [1, 2, 3, 5, 9],
  [3, 4],
  [0, 1, 2],
  [8, 9],
  [0, 3, 7],
  [1, 4, 7]

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)

aparține grafului, mergem la lista de adiacență a lui

i

și-l căutăm pe

j

în listă. Cât durează în cel mai defavorabil caz? Răspunsul este

Θ (d)

, unde

d

este gradul nodului

i

, deoarece aceasta este lungimea listei de adiacență a lui

i

. Gradul nodului

i

poate să fie cel mult

| V | - 1

(dacă

i

este adiacent la toate celelalte

| V | - 1

noduri) sau chiar egal cu 0 (dacă

i

este izolat, fără muchii incidente). Într-un graf neorientat, nodul

j

este în lista de adiacență a nodului

i

dacă și numai dacă

i

este în lista de adiacență a lui

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

. Atunci, pentru a apela funcţia doStuff pentru fiecare nod adiacent cu nodul

i

, am putea folosi următorul cod JavaScript:

for (var j = 0; j < graph[i].length; j++) {
    doStuff(graph[i][j]);
}

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

var vertex = graph[i];
for (var j = 0; j < vertex.length; j++) {
    doStuff(vertex[j]);
}

Cât spațiu ocupă listele de adjacență? Avem

| V |

liste și, deși fiecare listă ar putea avea până la

| V | - 1

vârfuri, listele de adjacență pentru un graf neorientat conțin în total

2 | E |

elemente. De ce

2 | E |

? Fiecare muchie

(i, j)

apare exact de două ori în listele de adiacenţă: o dată în lista lui

i

și o dată în lista lui

j

. Sunt

| E |

muchii. Pentru un graf orientat, listele de adiacență conțin

| E |

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ă de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.

Vrei să te alături conversației?

Conectare

Ordonare după:

Nici o postare încă.

Înțelegi engleza? Dă clic aici pentru a vedea mai multe discuții care au loc pe site-ul în limba engleză al Khan Academy.