Lista de adiacență și reprezentarea matriceală a graficului
Chiar dacă arată diferit, toate tipuri de grafice poate fi reprezentat într-un mod similar. În general, există două tipuri de reprezentare grafică:
- Matricea adiacentei
- Lista adiacenței
Lista adiacenței
Lista de adiacență constă din liste legate. Fiecare vârf este considerat un index de matrice, iar fiecare element reprezintă o listă legată. Aceste liste legate conțin vârfurile care au muchii cu vârful index.
Iată un exemplu de listă de adiacență:
Să presupunem că un grafic conține V număr de vârfuri și E număr de muchii.
În general, complexitatea spațiului va fi O(V + E)
.
În cel mai rău caz complexitatea spațiului va fi O(V2)
dacă Graficul dat este Graficul complet
Matricea adiacentei
Matricea de adjacență este compusă dintr-o matrice 2D. Graficul având un număr V de vârfuri, dimensiunea matricei va fi VxV
.
Spune, matrix[i][j] = 5
. Înseamnă că există o margine între nodul i și j unde greutatea este 5.
Să ne uităm la următorul grafic și matricea sa de adiacență:
Am creat Matrice 2D folosind acești pași:
Pas 1) Vârful A are o margine directă cu B, iar greutatea este 5. Deci, celula din rândul A și coloana B vor fi umplute cu 5. Restul celulelor din rândul A vor fi umplute cu zero.
Pas 2) Vârfurile B au o margine directă cu C, iar greutatea este 4. Deci, celula din rândul B și coloana C vor fi umplute cu 4. Celulele rămase din rândul B vor fi umplute cu zero, deoarece B nu are margine de ieșire pentru niciunul. alte noduri.
Pas 3) Vârfurile C nu au muchii directe cu alte vârfuri. Deci, rândul C va fi umplut cu zerouri.
Pas 4) Vârful D are o muchie direcționată cu A și C.
- Aici, celula din rândul D și coloana A vor avea valoarea 7. Celulele din rândul D și coloana C vor avea valoarea 2.
- Restul celulelor din rândul D vor fi umplute cu zerouri.
Pas 5) Vârfurile E au marginea direcționată cu B și D. Celula din rândul E și coloana B vor avea valoarea 6. Celulele din rândul E și coloana D vor avea valoarea 3. Restul celulelor din rândul D vor fi umplut cu zerouri.
Iată câteva puncte de observat:
- Graficul nu are auto-bucle atunci când diagonala primară a matricei de adiacență este 0.
- Graficul este un grafic direcționat dacă indicii (a,b) și (b,a) nu au aceeași valoare. În caz contrar, Graficul este un grafic direcționat.
- Graficul va fi un grafic ponderat dacă valoarea celulelor este mai mare de 1.
Există o problemă cu matricea de adiacență, deoarece necesită spații pătrate. Aici stocăm marginile care nu sunt conectate. Aceste margini alocă spațiu în memorie.
De exemplu, dacă avem un grafic cu 100 de noduri, atunci sunt necesare 10 mii de celule pentru a-l stoca în RAM. Cu mai puține margini în grafic, alocarea unei astfel de memorie mari poate fi o risipă. Deci, complexitatea spațiului folosind matricea Adjacență va fi O(N2)
, unde N înseamnă numărul de noduri din grafic.