Struttura dei dati - Struttura dei dati del grafico
Un grafico è una rappresentazione pittorica di un insieme di oggetti in cui alcune coppie di oggetti sono collegate da collegamenti. Gli oggetti interconnessi sono rappresentati da punti denominati comeverticese vengono chiamati i collegamenti che collegano i vertici edges.
Formalmente, un grafico è una coppia di insiemi (V, E), dove V è l'insieme di vertici e Eè l'insieme dei bordi, che collega le coppie di vertici. Dai un'occhiata al grafico seguente:
Nel grafico sopra,
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
Struttura dei dati del grafico
I grafici matematici possono essere rappresentati nella struttura dei dati. Possiamo rappresentare un grafo usando un array di vertici e un array bidimensionale di bordi. Prima di procedere oltre, familiarizziamo con alcuni termini importanti:
Vertex- Ogni nodo del grafico è rappresentato come un vertice. Nell'esempio seguente, il cerchio etichettato rappresenta i vertici. Quindi, da A a G sono vertici. Possiamo rappresentarli usando un array come mostrato nell'immagine seguente. Qui A può essere identificato dall'indice 0. B può essere identificato usando l'indice 1 e così via.
Edge- Edge rappresenta un percorso tra due vertici o una linea tra due vertici. Nell'esempio seguente, le linee da A a B, da B a C e così via rappresentano i bordi. Possiamo usare un array bidimensionale per rappresentare un array come mostrato nell'immagine seguente. Qui AB può essere rappresentato come 1 nella riga 0, colonna 1, BC come 1 nella riga 1, colonna 2 e così via, mantenendo le altre combinazioni come 0.
Adjacency- Due nodi o vertici sono adiacenti se sono collegati tra loro tramite un bordo. Nell'esempio seguente, B è adiacente ad A, C è adiacente a B e così via.
Path- Path rappresenta una sequenza di bordi tra i due vertici. Nell'esempio seguente, ABCD rappresenta un percorso da A a D.
Operazioni di base
Di seguito sono riportate le operazioni primarie di base di un grafico:
Add Vertex - Aggiunge un vertice al grafico.
Add Edge - Aggiunge un bordo tra i due vertici del grafico.
Display Vertex - Visualizza un vertice del grafico.
Per saperne di più su Graph, leggi il tutorial sulla teoria dei grafi . Impareremo come attraversare un grafico nei prossimi capitoli.