Pentru a reprezenta grafice orientate, puteți utiliza diferite structuri de date. Alegerea structurii de date depinde de operatorii care vor fi aplicați vârfurilor și arcurilor digraphului.
Una din metodele utilizate în mod obișnuit de reprezentare a digraph G = (V, E) este matricea de adiacenta. Să presupunem că o multitudine de noduri ale digraph V =. apoi matricea graficului adiacenta G - A este o matrice de dimensiune n n valori cu tipul Boolean, unde A [i, j] = true dacă și numai dacă există un arc de la vertex i trece prin punctul j. De multe ori, în matricea de adiacenta se înlocuiește cu valoarea reală a 1 și o valoare de fals - 0. Timpul de acces matrice element de adiacență depinde de mărimea setului de vârfuri și o multitudine de arce. Digraph reprezentare sub forma matricei adiacenta este convenabil să se folosească în algoritmi, care de multe ori au nevoie pentru a verifica existența arcului.
Folosind matricea de adjudecție, este posibilă reprezentarea digraphs-urilor marcate. În acest caz, elementul A [i, j] este egal cu eticheta arcului i j. Dacă nu există nici un arc de la vârful i până la punctul j, atunci A [i, j] poate fi considerat ca o celulă goală. În Fig. 7.2 prezintă digraphul marcat și matricea de adjunct corespunzătoare acestuia.
Fig. 7.2 - Digraphul marcat și matricea de adjuvant corespunzătoare
Principalul dezavantaj al matricelor de contiguitate este că necesită o capacitate de memorie egală chiar dacă arcele sunt mult mai mici decât. Prin urmare, citirea matricei sau găsirea elementului necesar în ea necesită un timp de comandă. care nu permite crearea de algoritmi cu timpul n pentru a lucra cu digraphs având ordinea n arcs.
Prin urmare, în locul matricilor de adjuvant, reprezentările digraphs pot fi utilizate cu ajutorul listelor de situații de urgență. Lista de contiguitate pentru vertex i este o listă a tuturor vârfurilor adiacente vârfului i. și ordonate într-un anumit mod. Astfel, digraphul G poate fi reprezentat prin intermediul matricei HEAD. al cărui element HEAD [i] este un pointer la lista de adiacentă a vârfului i. Reprezentarea digografilor utilizând listele de contiguitate necesită o capacitate de stocare proporțională cu suma numărului de vârfuri și a numărului de arce de stocat. Dacă numărul de arce este de ordinul n. atunci cantitatea totală de memorie necesară este de aceeași ordine. Dar pentru listele de adjuvant, timpul de căutare al unui anumit arc poate fi de ordinul lui n, deoarece Aceeași ordine poate avea numărul de arce la un anumit vârf. În Fig. 7.3 prezintă structura de date reprezentând digrafa din Fig. 7.1 prin intermediul listelor conexe de contiguitate. Dacă arcele au etichete, ele pot fi stocate în celulele listelor legate. Pentru a insera și a șterge elemente în liste de contiguitate, trebuie să aveți o matrice HEAD. Acesta conține un indicator pentru celulele anteturilor listelor de contiguitate, dar nu și nodurile adiacente.
Fig. 7.3 - Structura listelor de adiacentă pentru digar
Articole similare
Trimiteți-le prietenilor: