Struttura dei dati del grafico

In questo tutorial imparerai cos'è una struttura dati grafico. Inoltre, troverai rappresentazioni di un grafico.

Una struttura dati a grafo è una raccolta di nodi che contengono dati e sono collegati ad altri nodi.

Proviamo a capirlo attraverso un esempio. Su facebook tutto è un nodo. Ciò include utente, foto, album, evento, gruppo, pagina, commento, storia, video, collegamento, nota … tutto ciò che ha dati è un nodo.

Ogni relazione è un confine da un nodo all'altro. Sia che tu pubblichi una foto, ti unisca a un gruppo, come una pagina, ecc., Viene creato un nuovo bordo per quella relazione.

Esempio di struttura dati del grafico

Tutto Facebook è quindi una raccolta di questi nodi e bordi. Questo perché Facebook utilizza una struttura dati a grafo per memorizzare i suoi dati.

Più precisamente, un grafico è una struttura dati (V, E) che consiste in

Una raccolta di vertici V
Una raccolta di archi E, rappresentati come coppie ordinate di vertici (u, v)

Vertici e bordi

Nel grafico,

 V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)

Terminologia dei grafici

Adiacenza : si dice che un vertice è adiacente a un altro vertice se c'è un bordo che li collega. I vertici 2 e 3 non sono adiacenti perché non ci sono bordi tra di loro.
Percorso : una sequenza di bordi che consente di andare dal vertice A al vertice B è chiamata percorso. 0-1, 1-2 e 0-2 sono percorsi dal vertice 0 al vertice 2.
Grafico orientato: un grafico in cui un arco (u, v) non significa necessariamente che ci sia anche un arco (v, u). I bordi in un tale grafico sono rappresentati da frecce per mostrare la direzione del bordo.

Rappresentazione grafica

I grafici sono comunemente rappresentati in due modi:

1. Matrice di adiacenza

Una matrice di adiacenza è un array 2D di vertici V x V. Ogni riga e colonna rappresentano un vertice.

Se il valore di qualsiasi elemento a(i)(j)è 1, rappresenta che c'è un bordo che collega il vertice i e il vertice j.

La matrice di adiacenza per il grafico che abbiamo creato sopra è

Matrice di adiacenza del grafico

Dato che è un grafo non orientato, per il bordo (0,2), dobbiamo anche contrassegnare il bordo (2,0); rendendo la matrice di adiacenza simmetrica rispetto alla diagonale.

La ricerca del bordo (controllando se esiste un bordo tra il vertice A e il vertice B) è estremamente veloce nella rappresentazione della matrice di adiacenza, ma dobbiamo riservare spazio per ogni possibile collegamento tra tutti i vertici (V x V), quindi richiede più spazio.

2. Elenco delle adiacenze

Un elenco di adiacenza rappresenta un grafico come un array di elenchi collegati.

L'indice della matrice rappresenta un vertice e ogni elemento nella sua lista collegata rappresenta gli altri vertici che formano un bordo con il vertice.

L'elenco delle adiacenze per il grafico che abbiamo creato nel primo esempio è il seguente:

Rappresentazione in lista di adiacenza

Una lista di adiacenza è efficiente in termini di archiviazione perché abbiamo solo bisogno di memorizzare i valori per i bordi. Per un grafico con milioni di vertici, questo può significare molto spazio risparmiato.