Structuri de date pentru reprezentarea graficelor
Informațiile despre grafice sau diagrame pot fi stocate în două moduri: ca o matrice de adjunct sau ca o listă de contiguiții. În această lucrare, graficul și digraph-urile sunt reprezentate în mod egal, așa că pentru ele vom folosi termenul general "graf". Vom vedea, de asemenea, că metodele utilizate pentru a stoca informații elimină diferența în prelucrarea grafurilor și digografiilor.
Matricea de adjacență oferă acces rapid la informații despre marginile graficului, dar dacă există câteva margini în grafic, atunci această matrice va conține mult mai multe celule goale decât cele pline. Lungimea listei de contiguiții este proporțională cu numărul de margini din grafic, cu toate acestea, atunci când se utilizează lista, timpul pentru obținerea informațiilor despre margine crește.
Nici una dintre aceste metode nu este superioară celeilalte. Alegerea unei metode potrivite ar trebui să se bazeze pe cunoștințele noastre preliminare despre graficele care vor fi procesate de algoritm. Dacă există multe noduri în grafic și fiecare dintre acestea este asociată doar cu un număr mic de alte noduri, lista adjunctelor se dovedește a fi mai avantajoasă, deoarece ocupă mai puțin spațiu, iar lungimea listelor marginilor care trebuie examinate este mică. Dacă numărul de noduri din grafic este mic, atunci este mai bine să folosiți matricea adjacency: va fi mică și chiar pierderile de stocare în forma matrice a graficului slab vor fi nesemnificative. Dacă există multe margini în grafic și este aproape completă, atunci matricea adjacency este întotdeauna cea mai bună metodă de a stoca graficul.
Utilizarea matricei și a listei de contiguiții este descrisă mai jos.
Matricea adiacentă
Matricea de adiacență AdjMat a graficului G = (V, E) cu numărul de vârfuri | V | = N este scris ca o matrice bidimensională de dimensiune N x N. În fiecare celulă [i, j] din această matrice, valoarea 0 este scrisă cu excepția acelor cazuri în care vârful vj duce la vârful vj și apoi valoarea 1 este scrisă în celulă. mai strict,
În Fig. Figura 2 prezintă matricile de adjuvant pentru grafic și digraful prezentat în Fig. 1.
Celula matricei de adjudecare a unui grafic ponderat sau digraph conține semnul infinitului dacă marginea corespunzătoare lipsește și în toate celelalte cazuri valoarea sa este egală cu greutatea marginii. Elementele diagonale ale unei astfel de matrice sunt egale cu 0, deoarece călătoria de sus în ea nu costă nimic.
Lista intersecțiilor
O listă de adjacități AdjList a graficului G = (V, E) cu numărul de vârfuri | V | = N este scris ca o matrice unidimensională de lungime N, fiecare element al căruia este o legătură către listă. O astfel de listă este atribuită fiecărui vârf al graficului și conține un element pe fiecare vertex al graficului adiacent celui dat.
În Fig. 3 prezintă listele de contiguiții pentru grafic și digraf prezentate în Fig. 1.
Elementele din lista de confidențialitate pentru un grafic ponderat conțin un câmp suplimentar pentru stocarea greutății marginii.
Articole similare
-
Scopul este de a oferi copiilor o idee de temperare, beneficiile pentru sănătate
-
Lucrul cu structurile de date din limbile C și Python Partea 6
Trimiteți-le prietenilor: