De fapt, am considerat deja unul dintre exemplele unei astfel de structuri ca graficele - un copac. Un arbore este un grafic nesemnificativ.
Contele sunt de fapt destul de nebuni. Dar, pentru simplitate, pentru moment vom împărți graful în două tipuri:
- Un grafic nedirecționat
- Grafic orientat (grafic orientat).
Grafic nedirecționat. un subset de perechi (V, E), unde V - un subset de noduri și E - subset de muchii care conectează aceste noduri. Pentru a renunța la tot felul de descrieri și termeni complexe mai ușor de imaginat conta ca două puncte A și B, conexiunile de margine. Într-un grafic nedirecționat de-a lungul unei margini de la punctul A se poate ajunge la punctul B și de la punctul B la punctul A.
Într-un grafic direcționat toate la fel, cu excepția faptului că nervurile sunt deja numit arc, și se conectează în mod clar un punct la altul. De exemplu, punctul A la punctul B, ceea ce înseamnă că, din punctul A la punctul B, pentru a obține un arc, poate, dar de la punctul B la punctul A - shish aici. Desigur, poate exista un arc de la punctul B la punctul A :)
În graficele, tot nu este sfârșitul celor două puncte, grafice sunt acum sute de milioane de noduri, sau chiar miliarde, sau chiar mai mult, cu un număr foarte mare de muchii sau arce (da, există grafice mixte, în cazul în care unele vârfuri cu altul sunt conectate prin arce, și niște nervuri) între vârfuri.
Un grafic ponderat este un grafic pe fiecare margine a căruia este atașat un anumit număr care se numește greutatea unei margini.
De fapt, un grafic poate fi reprezentat ca o listă de adjacități și ca o matrice de adjuvant.
Matricea de adiacență este matricea nxn unde n este numărul de vârfuri ale graficului, iar celula [i, j] reprezintă sau este legătura dintre vârfurile i, j. Cu matricea de adjuvantă, este suficient să spunem pur și simplu dacă există o legătură între vârfurile i, j, chiar dacă există multe alte vârfuri între ele. Minusul matricei de adiacență este cantitatea de memorie necesară pentru stocarea informațiilor din grafic. De exemplu, 10 vârfuri ne dau o matrice - 10 la 10, care este egală cu 100 de celule ale matricei. Dacă avem cel puțin o mie de vârfuri, atunci numărul de celule crește la 1 milion :)
Să admitem aici un astfel de grafic:
Acesta va arata astfel:
O alternativă pentru a reprezenta un grafic este lista de adjacități. De fapt, aceasta este o prezentare a unei liste a în cazul în care pe de o parte - în partea de sus, iar pe de cealaltă parte a unei liste de noduri cu care există o legătură.
Această structură este mai optimă din punct de vedere al memoriei utilizate, dar este mai puțin eficientă în ceea ce privește efectuarea operațiunilor.
Pentru posturile ulterioare, va fi utilizată reprezentarea graficului ca listă de vecinătate. În primul rând, memoria, în al doilea rând, este mai ușor pentru mine să reprezint grafice într-o astfel de structură.
Se creează un grafic în timpul transferului numărului de noduri către el. Atunci când creăm un grafic, creăm o matrice în care pentru fiecare vârf vom stoca conexiuni cu alte noduri.
Adăugarea unui vârf. Deoarece graficul este nedirecțional dacă vârful A este conectat la vârful B, apoi invers.
Reprezentarea graficului direcționat este exact aceeași, cu o singură modificare:
După cum puteți vedea, diferența este doar într-o singură metodă addEdge - aici adăugăm doar o conexiune vertex.
Ca de obicei: puteți găsi sursa de exemple aici.
codificarea blogului lui maleev
Articole similare
Trimiteți-le prietenilor: