Ce este Structura datelor grafice?

A Grafic este o structură de date neliniară constând din vârfuri și muchii. Vârfurile sunt uneori denumite și noduri, iar muchiile sunt linii sau arce care conectează oricare două noduri din grafic. Mai formal, un grafic este compus dintr-un set de vârfuri ( ÎN ) și un set de muchii( ȘI ). Graficul este notat cu G(V, E) .

cheie primară compusă

Reprezentări ale graficului

Iată cele mai comune două moduri de a reprezenta un grafic:

1. Matricea adiacentei
2. Lista adiacentei

Matricea adiacentei

O matrice de adiacență este o modalitate de a reprezenta un grafic ca o matrice de boolean (0 și 1).

Să presupunem că există n vârfuri în grafic Deci, creați o matrice 2D adjMat[n][n] având dimensiunea n x n.

• Dacă există o muchie de la vârf i la j , marcă adjMat[i][j] la fel de 1 .
• Dacă nu există muchie de la vârf i la j , marcă adjMat[i][j] la fel de 0 .

Reprezentarea graficului nedirecționat la matricea de adiacență:

Figura de mai jos arată un grafic nedirecționat. Inițial, întreaga Matrice este inițializată la 0 . Dacă există o margine de la sursă la destinație, inserăm 1 în ambele cazuri ( adjMat[destinație] și adjMat [ destinaţie]) pentru că putem merge în orice direcție.

sortare listă după java

Graficul nedirecționat către matricea de adiacență

Reprezentarea graficului direcționat la matricea de adiacență:

Figura de mai jos prezintă un grafic direcționat. Inițial, întreaga Matrice este inițializată la 0 . Dacă există o margine de la sursă la destinație, inserăm 1 pentru acel anume adjMat[destinație] .

Graficul direcționat către matricea de adiacență

Lista adiacentei

O matrice de liste este folosită pentru a stoca muchiile dintre două vârfuri. Mărimea matricei este egală cu numărul de vârfuri (adică n) . Fiecare index din această matrice reprezintă un punct specific în grafic. Intrarea de la indexul i al tabloului conține o listă legată care conține vârfurile care sunt adiacente vârfurilor i .

Să presupunem că există n vârfuri în grafic Deci, creați un matrice de liste de mărime n la fel de adjList[n].

algoritm pentru rsa

• adjList[0] va avea toate nodurile care sunt conectate (vecin) la vârf 0 .
• adjList[1] va avea toate nodurile care sunt conectate (vecin) la vârf 1 și așa mai departe.

Reprezentarea graficului nedirecționat la lista de adiacență:

Graficul nedirecționat de mai jos are 3 vârfuri. Deci, o matrice de listă va fi creată de dimensiunea 3, unde fiecare indici reprezintă vârfurile. Acum, vârful 0 are doi vecini (adică 1 și 2). Deci, introduceți vârfurile 1 și 2 la indicii 0 ai matricei. În mod similar, pentru vârful 1, are două vecine (adică 2 și 0). Deci, inserați vârfurile 2 și 0 la indicii 1 ai tabloului. În mod similar, pentru vârful 2, inserați vecinii săi în matricea listei.

Grafic nedirecționat către lista de adiacență

Reprezentarea graficului direcționat la lista de adiacență:

Graficul direcționat de mai jos are 3 vârfuri. Deci, o matrice de listă va fi creată de dimensiunea 3, unde fiecare indici reprezintă vârfurile. Acum, vârful 0 nu are vecini. Pentru vârful 1, are două vecine (adică 0 și 2). Deci, inserați vârfurile 0 și 2 la indicii 1 ai tabloului. În mod similar, pentru vârful 2, inserați vecinii săi în matricea listei.

Graficul direcționat către lista de adiacență