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.