Introduzione al grafico nella struttura dei dati

I grafici sono strutture di dati non lineari comprendenti un insieme finito di nodi e spigoli. I nodi sono gli elementi e i bordi sono ordinate coppie di connessioni tra i nodi.

Notare la parola non lineare. Una struttura di dati non lineare è una struttura in cui gli elementi non sono disposti in ordine sequenziale. Ad esempio, un array è una struttura di dati lineare perché gli elementi sono disposti uno dopo l'altro. È possibile attraversare tutti gli elementi di un array in una singola corsa. Questo non è il caso delle strutture di dati non lineari. Gli elementi di una struttura di dati non lineare sono disposti su più livelli, spesso seguendo uno schema gerarchico. I grafici non sono lineari.

La parola successiva a cui prestare attenzione è limitata. Definiamo il grafico per avere un numero finito e numerabile di nodi. Questo è un termine piuttosto non piacevole. In sostanza, un grafico può avere un numero infinito di nodi ed essere ancora finito. Ad esempio, un albero genealogico che risale ad Adamo ed Eva. Questo è un grafico relativamente infinito ma è ancora numerabile ed è quindi considerato finito.

Esempio del mondo reale

Il miglior esempio di grafici nel mondo reale è Facebook. Ogni persona su Facebook è un nodo ed è collegato attraverso i bordi. A è un amico di B. B è un amico di C e così via.

terminologie

Ecco le terminologie del grafico nella struttura dei dati menzionate di seguito

1. Rappresentazione del grafico: generalmente un grafico è rappresentato come una coppia di insiemi (V, E). V è l'insieme di vertici o nodi. E è l'insieme di bordi. Nell'esempio sopra,
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)

2. Nodo o vertice: gli elementi di un grafico sono collegati attraverso i bordi.

3. Bordi: un percorso o una linea tra due vertici in un grafico.

4. Nodi adiacenti: due nodi vengono chiamati adiacenti se sono collegati attraverso un bordo. Nell'esempio sopra, il nodo A è adiacente ai nodi B, C e D, ma non al nodo E.

5. Path: Path è una sequenza di spigoli tra due nodi. È essenzialmente un attraversamento che inizia da un nodo e termina in un altro. Nell'esempio sopra, ci sono più percorsi dal nodo A al nodo E.

Percorso (A, E) = (AB, BE)
O
Percorso (A, E) = (AC, CD, DE)
O
Percorso (A, E) = (AD, DE)

6. Grafico non diretto : un grafico non diretto è uno in cui i bordi non specificano una direzione particolare. I bordi sono bidirezionali.

Esempio

Pertanto, in questo esempio, il bordo CA può essere attraversato da A a C e da C ad A. Simile a tutti i bordi. Un percorso dal nodo B al nodo C sarebbe (BA, AC) o (BD, DC).

7. Grafico diretto : un grafico diretto è uno in cui i bordi possono essere attraversati solo in una direzione specificata.

Esempio

Quindi, nello stesso esempio, ora i bordi sono direzionali. Puoi solo attraversare il bordo lungo la sua direzione. Al momento non esiste alcun percorso dal nodo B al nodo C.

8. Grafico ponderato: un grafico ponderato è quello in cui i bordi sono associati a un peso. Questo è generalmente il costo per attraversare il bordo.

Esempio

Quindi, nello stesso esempio, ora i bordi hanno un certo peso associato ad essi. Esistono due possibili percorsi tra il nodo A e il nodo E.
Percorso1 = (AB, BD, DE), Peso1 = 3 + 2 + 5 = 10
Path2 = (AC, CD, DE), Weight2 = 1 + 3 + 5 = 9
Chiaramente, si preferirebbe Path2 se l'obiettivo è raggiungere il nodo E dal nodo A con un costo minimo.

Operazioni di base sul grafico

Ecco le operazioni di base del grafico menzionate di seguito

1. Aggiungi / Rimuovi vertice

Questa è l'operazione più semplice nel grafico. È sufficiente aggiungere un vertice a un grafico. Non è necessario che sia collegato a nessun altro vertice attraverso un bordo. Quando si rimuove un vertice, è necessario rimuovere tutti i bordi che hanno origine e terminano sul vertice eliminato.

2. Aggiungi / Rimuovi bordo

Questa operazione aggiunge o rimuove un bordo tra due vertici. Quando tutti i bordi che hanno origine e terminano in corrispondenza di un vertice vengono eliminati, il vertice diventa un vertice isolato.

3. Ricerca per primo (BFS)

Questa è un'operazione trasversale nel grafico. BFS attraversa orizzontalmente il grafico. Ciò significa che attraversa tutti i nodi a un singolo livello prima di passare al livello successivo.
L'algoritmo BFS inizia nella parte superiore del primo nodo nel grafico e quindi attraversa tutti i nodi adiacenti ad esso. Una volta attraversati tutti i nodi adiacenti, l'algoritmo ripete la stessa procedura per i nodi figlio.

Esempio

Attraversare il grafico sopra in modo BFS risulterebbe da A -> B -> C -> D -> E -> F -> G. L'algoritmo inizia dal nodo A e attraversa tutti i suoi nodi adiacenti B, C e D. Contrassegna tutti e quattro i nodi visitati. Una volta attraversati tutti i nodi adiacenti di A, l'algoritmo si sposta sul primo nodo adiacente di A e ripete la stessa procedura. In questo caso, il nodo è B e i nodi adiacenti a B sono E e F. Successivamente, i nodi adiacenti a C vengono attraversati. Una volta visitati tutti i nodi, l'operazione termina.

4. Profondità prima ricerca (DFS)

Depth First Search o DFS attraversa il grafico in verticale. Inizia con il nodo radice o il primo nodo del grafico e attraversa tutti i nodi figlio prima di spostarsi sui nodi adiacenti.

Esempio

Attraversare il grafico sopra in modo BFS risulterebbe da A -> B -> E -> F -> C -> G -> D. L'algoritmo inizia dal nodo A e attraversa tutti i suoi nodi figlio. Non appena incontra B, sembra che abbia ulteriori nodi figlio. Pertanto, i nodi figlio di B vengono attraversati prima di passare al nodo figlio successivo di A.

Realizzazioni nel mondo reale di grafici

  • Progettazione di circuiti elettrici per la trasmissione di potenza.
  • Progettazione di una rete di computer interconnessi.
  • Studio della struttura molecolare, chimica e cellulare di qualsiasi sostanza, ad esempio DNA umano.
  • Progettazione di percorsi di trasporto tra città e luoghi all'interno di una città.

Conclusione - Grafico nella struttura dei dati

I grafici sono un concetto molto utile nelle strutture di dati. Ha implementazioni pratiche in quasi tutti i campi. È molto importante comprendere le basi della teoria dei grafi, per sviluppare una comprensione degli algoritmi della struttura dei grafi.
Questo articolo è stato semplicemente un'introduzione ai grafici. È solo un trampolino di lancio. Si consiglia di approfondire ulteriormente l'argomento della teoria dei grafi.

Articoli consigliati

Questa è una guida al grafico nella struttura dei dati. Qui discutiamo le terminologie e le operazioni di base del grafico nella struttura dei dati. Puoi anche leggere il seguente articolo per saperne di più -

  1. Domande di intervista sulla struttura dei dati
  2. Modello di dati in Cassandra
  3. Che cos'è Data Mart?
  4. Che cos'è uno scienziato di dati?

Categoria:

Big Data