Grafuri in STL

[•mateiuli]

Salut,

M-am apucat acum cateva zile de STL si mi se par extrem de utile.
Am incercat sa stochez graful prin liste de adiacenta numai ca nu reusesc - vreau sa le tin ca o multime sa le gasesc mai usor.

Am incercat ceva de genul:

Cod:

set<int> lista;
vector<lista> A;

Cam asta ar fi in mare ce vreau eu sa fac. Vreau ceva de genul:

Cod:

A[1] - > 2, 4, 7 // exista leg directa dintre 1 si 2, 4, 7
A[2] - > 1, 6, 4 // exista leg directa dintre 2 si 1, 6, 4

Sa am un vector de multimi.

Cum pot implementa asta in STL?

Sau daca nu merge cum vreu eu, cum pot sa ma folosesc de STL la grafuri?

[•PlayLikeNeverB4]

In general nu cred ca e cea mai buna solutie sa folosesti set-uri, deoarece nu permit accesul indexat.
In schimb poti folosi cate o lista pentru fiecare nod. Daca ai N noduri, poti proceda in felul urmator:
Declari asa

Cod:

vector<int> A[N];

Creezi listele asa

Cod:

A[1].push_back(2); A[1].push_back(4); A[1].push_back(7);
A[2].push_back(1); A[2].push_back(6); A[2].push_back(4);

A[1][0] va fi 2, A[1][1] va fi 4, A[2][0] va fi 1 si tot asa.

Pentru a parcurge vecinii nodului p, poti scrie asa:

Cod:

for(i=0;i<A[p].size();i++)
   printf("%d ",A[p][i]);

Sper ca ti-a fost de folos.

[•mateiuli]

Multumesc.

Am reusit acum sa fac si pe set.

// graful
set<int> noduri;
vector<set<int> > G(201, noduri);

Prefer sa folosesc set pentru ca am metoda find() care imi spune daca exista legatura intre doua noduri in O(log(n)).

[•devilkind]

Nu e o idee buna sa folosesti set, deoarece daca vei vrea sa iterezi prin vecinii unui nod, vei avea complexitate O(VlogV) in loc de O(V) (V e numarul de vecini) deoarece trecerea de la un element la urmatorul in set se face in log(N).

[•wefgef]

Nu e o idee buna sa folosesti set, deoarece daca vei vrea sa iterezi prin vecinii unui nod, vei avea complexitate O(VlogV) in loc de O(V) (V e numarul de vecini) deoarece trecerea de la un element la urmatorul in set se face in log(N).

De fapt daca iterezi prin toate elementele unui set vei avea complexitate O(N), unde N este marimea setului.

[•mateiuli]

Am facut un test la problema DFS cu variantele de mai sus. (cum a zis @PlayLikeNeverB4 si cum am zis eu cu set)

Uitati rezultatele:
Cu set
Cum a zis @PlayLikeNeverB4

Se pare ca varianta mea e mai lenta si mananca si mai multa memorie.

Dar daca folosesc metoda cu vector<int> A[100];, cum fac sa vad daca am legatura dintre nodul 2 si 6 de exemplu?

[•MciprianM]

Varianta cu set, cum ai scris-o tu are complexitatea de O(n^2 log n). La fel ca si la dfs cu matrice de adiacenta, atata doar ca la set iti ia O(log n) pe accesarea elementului a de i si j fata de O(1) la matrice. Incearca sa o scrii cu un iterator pe set.

Si apropo, daca scrii asa nu declari o lista:

Cod:

vector<int> v;

Lista nu permite accesarea celui de-al k-lea element in O (1). In schimb lista permite adaugare/stergerea unui element in O (1) (aici nu intra si cautarea elementului).
Clasa Vector permite accesarea unui element in O (1). Dureaza O (n) sa stergi sau sa adaugi un element dintr-o sau intr-o pozitie oarecare.
Asa ca clasa Vector seamana mai mult cu un array (un sir obisnuit) decat cu o lista. Ce are in plus fata de un sir obisnuit e faptul ca dimensiunea lui e dinamica (se poate schimba in timp), mentinand complexitatile pentru inserare, stergere si random access la fel ca la sir. Dezavantajul la vector e ca pot exista elemente care desi sunt alocate nu sunt folosite. Adica, in orice clipa, un vector e un sir care are alocata memorie pentru capacity () elemente; ceea ce va da size () e numarul de elemente folosite din vector. In momentul in care size ()== capacity () si inserati un nou element, se aloca o noua zona continua de memorie, care poate fi de 2*capacity (), si se copiaza toate elementele vectorului in noua zona, si se adauga noul element inserat la sfarsit. Apoi se elibereaza vechea zona de memorie. Inserarea ia astfel, pentru un numar mare de elemente O (1) si din cand in cand ia O (n), dar per total, pentru a insera n elemente ia O (n), astfel se zice ca inserarea ia O (1)/element. Ceva de genu e si cu stergerea.


http://en.wikipedia.org/wiki/Sequence_container_(C%2B%2B)#Vector

Poti vedea si codul stl aici. Ca sa vezi inserarea trebuie sa te uiti in stl_vector.h la

Cod:

void push_back(const _Tp& __x) {
    if (_M_finish != _M_end_of_storage) {
      construct(_M_finish, __x);
      ++_M_finish;
    }
    else
      _M_insert_aux(end(), __x);
  }

si

Cod:

template <class _Tp, class _Alloc>
void 
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x) {
//codul il iei de pe dowload stl
}

[•mateiuli]

Imi poti da un exemplu cum pot folosi iteratori acolo?

[•MciprianM]

Am implementat eu cu iterator, un dfs ce ia O(n+m) (am folosit codul tau): http://infoarena.ro/job_detail/686376

[•mateiuli]

Ok. Mersi mult pentru ajutor.

Observ ca dintre cele doua variante tot cea a lui @Play... e mai optima (ca timp si memorie).
Pe care varianta mi-o recomanzi sa o folosesc pe la concursuri?

[•MciprianM]

Pe care varianta mi-o recomanzi sa o folosesc pe la concursuri?

Depinde de ce ai nevoie. In general, pe infoarena, se foloseste clasa vector pentru a stoca listele de adiacenta (desi cuvantul "liste" ne duce cu gandul sa folosim chiar o lista - care este si ea implementata in STL).

Am incercat sa stochez graful prin liste de adiacenta numai ca nu reusesc - vreau sa le tin ca o multime sa le gasesc mai usor.

De ce ai nevoie sa "gasesti" un nod? Eu nu am avut niciodata nevoie sa folosesc set pentru a memora grafuri, dar cine stie?

Cum memorezi grafurile, decizi in functie de problema. Dar in general e ok daca folosesti vector.