Lista di adiacenze e rappresentazione matriciale del grafico
Sara Chen
Anche se sembrano diversi, tutti tipi di grafici possono essere rappresentati in modo simile. Esistono generalmente due tipi di rappresentazione grafica:
- Matrice di adiacenza
- Elenco di adiacenza
Elenco di adiacenza
L'elenco di adiacenza è costituito da elenchi collegati. Ogni vertice è considerato un indice di array e ogni elemento rappresenta una lista concatenata. Queste liste concatenate contengono i vertici che hanno spigoli con il vertice indice.
Ecco un esempio di elenco di adiacenze:
Diciamo che un grafico contiene il numero V di vertici e il numero E di spigoli.
In generale, la complessità dello spazio sarà O(V + E).
La complessità spaziale nel caso peggiore sarà O(V2) se il grafico dato è il grafico completo
Matrice di adiacenza
La matrice di adiacenza è composta da un array 2D. Grafico avente un numero V di vertici, la dimensione della matrice sarà VxV.
Dire, matrix[i][j] = 5. Significa che c'è un bordo tra i nodi i e j dove il peso è 5.
Diamo un'occhiata al seguente grafico e alla sua matrice di adiacenza:
Abbiamo creato il file matrice 2D utilizzando questi passaggi:
Passo 1) Il vertice A ha un bordo diretto con B e il peso è 5. Pertanto, la cella nella riga A e la colonna B verranno riempite con 5. Il resto delle celle nella riga A verrà riempito con zero.
Passo 2) I vertici B hanno un bordo diretto con C e il peso è 4. Pertanto, la cella nella riga B e nella colonna C verrà riempita con 4. Le celle rimanenti nella riga B verranno riempite con zero poiché B non ha alcun bordo uscente verso nessuno altri nodi.
Passo 3) I vertici C non hanno bordi diretti con nessun altro vertice. Quindi, la riga C sarà riempita con zeri.
Passo 4) Il vertice D ha un bordo diretto con A e C.
- Qui, la cella nella riga D e nella colonna A avrà un valore pari a 7. Le celle nella riga D e nella colonna C avranno un valore pari a 2.
- Il resto delle celle nella riga D verrà riempito con zeri.
Passo 5) I vertici E hanno un bordo diretto con B e D. La cella nella riga E e nella colonna B avrà un valore di 6. Le celle nella riga E e nella colonna D avranno un valore di 3. Il resto delle celle nella riga D sarà pieno di zeri.
Ecco alcuni punti da notare:
- Il grafico non ha self-loop quando la diagonale primaria della matrice di adiacenza è 0.
- Il grafico è un grafico orientato se gli indici (a,b) e (b,a) non hanno lo stesso valore. Altrimenti, il grafico è un grafico orientato.
- Il grafico sarà un grafico ponderato se il valore delle celle è maggiore di 1.
C'è qualche problema con la matrice di adiacenza poiché richiede spazi quadrati. Qui memorizziamo i bordi che non sono collegati. Questi bordi allocano spazio nella memoria.
Ad esempio, se abbiamo un grafico con 100 nodi, saranno necessarie 10mila celle per memorizzarlo nel RAM. Con meno spigoli nel grafico, allocare una memoria così grande può essere uno spreco. Quindi, la complessità dello spazio usando la matrice di adiacenza sarà O(N2), dove N indica il numero di nodi nel grafico.
