Conţinutul principal
Biblioteca de informatică
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 de la 0 la . 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 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 . 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 muchii. Acum se pune întrebarea: Cum putem organiza o listă a muchiilor astfel încât căutarea unei anumite muchii să aibă timpul ? Răspunsul este puțin mai delicat.
Matrice de adiacență
Pentru un graf cu noduri, o matrice de adiacență este o matrice de dimensiuni cu elemente 0 și 1, pentru care elementul de pe linia și coloana este 1 dacă și numai dacă muchia aparține grafului. Dacă vrem să precizăm costul unei muchii, vom atribui ca valoare a elementului de pe linia și coloana 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 aparține grafului uitându-ne la 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 , trebuie să analizăm toate valorile de pe linia , chiar dacă doar puține noduri sunt adiacente cu nodul .
graph
, atunci putem verifica dacă muchia graph[i][j]
. Așadar, care este dezavantajul unei matrice de adiacență? De fapt, sunt două. În primul rând, necesită Pentru un graf neorientat, matricea de adiacenţă este simetrică: Elementul de pe linia și coloana este 1 dacă și numai dacă elementul de pe linia și coloana 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 , memorăm vectorul de vârfuri adiacente acestuia. De obicei, avem un vector cu 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 aparține grafului, mergem la lista de adiacență a lui și-l căutăm pe în listă. Cât durează în cel mai defavorabil caz? Răspunsul este , unde este gradul nodului , deoarece aceasta este lungimea listei de adiacență a lui . Gradul nodului poate să fie cel mult (dacă este adiacent la toate celelalte noduri) sau chiar egal cu 0 (dacă este izolat, fără muchii incidente). Într-un graf neorientat, nodul este în lista de adiacență a nodului dacă și numai dacă este în lista de adiacență a lui . 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 . Atunci, pentru a apela funcţia , am putea folosi următorul cod JavaScript:
graph
, astfel încât graph[i]
este vectorul cu vecinii nodului doStuff
pentru fiecare nod adiacent cu nodul 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 liste și, deși fiecare listă ar putea avea până la vârfuri, listele de adjacență pentru un graf neorientat conțin în total elemente. De ce ? Fiecare muchie apare exact de două ori în listele de adiacenţă: o dată în lista lui și o dată în lista lui . Sunt muchii. Pentru un graf orientat, listele de adiacență conțin 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?
Nici o postare încă.