Reprezentare grafuri recomandata

[•Harald]

Bună!

Care este cea mai recomandată formă de reprezentare a grafurilor pentru un concurs precum OJI? În momentul de față folosesc matricea de adiacență, însă nu este chiar economă din punct de vedere al memoriei pentru grafurile mari. De exemplu, dacă la concurs graful poate avea pana la 10.000 noduri, atunci matricea de adiacență (de tipul int) va ocupa aproximativ 200MB memorie, care depăsește cu mult limita de 64MB (asta dacă programul nu dă eroare la rulare din cauza matricei prea mari).

Ce formă de reprezentare îmi recomandați?

Mulțumesc anticipat!

[•Owlree]

De ce mai multe ori cea mai adecvată metodă este lista de adiacență.

Totuși, în unele cazuri, spre exemplu când știi că graful e destul de mic, sau că e dens, poate fi de preferat să folosești matricea.

[•Harald]

Mulțumesc pentru răspuns! Am să încerc să mă obișnuiesc și cu lista de adiacență până la OJI.

Totuși, am văzut la multe din soluțiile trimise în arhiva de probleme că este folosit un vector din librăria cu același nume. Este doar o altă alternativă de scriere pentru lista de adiacență?

[•PlayLikeNeverB4]

Este doar o altă alternativă de scriere pentru lista de adiacență?

Da, te scuteste de implementarea manuala.

[•Harald]

Am înțeles. Mulțumesc pentru clarificări!

[•Owlree]

Biblioteca vector are ceva mai multe aplicații decât folosirea în listele de adiacență. Încearcă să te documentezi mai mult despre ea, și în general despre ceva numit STL (Standard Template Library), îți va fi de mare ajutor la olimpiade.

[•Harald]

Îți mulțumesc pentru sfat. M-am folosit de containerul queue pentru BFS, însă nu am avut ocazia până acum să mă acomodez și cu vector, însă asta am de gând să fac acum.

Mulțumesc încă odata.
Numai bine!