Tipi di grafici nella struttura dei dati e nelle applicazioni

introduzione

Un grafo è una struttura non lineare composta da nodi e spigoli. Può includere un insieme finito o infinito di nodi tenuti da un bordo che collega una coppia di nodi. Le strutture dati sono una parte essenziale di qualsiasi concetto di codifica; quindi, avere una solida conoscenza dei diversi tipi di grafici nelle strutture dati può aiutarti a superare complessi problemi del mondo reale.

Nel mondo di oggi, i dati sono potere. Pertanto, organizzare i dati in modo efficiente per un facile accesso è essenziale per qualsiasi programmatore. La conoscenza delle strutture di dati e della sua varietà di grafici potenzia le tue capacità di codifica per affrontare i problemi del mondo reale e fornire efficacemente le sue soluzioni.

Impara la scienza dei dati per ottenere un vantaggio sui tuoi concorrenti

Diamo un'occhiata ai diversi tipi di grafici comunemente usati nelle strutture dati e come vengono applicati nella vita reale.

Tipi di grafici nelle strutture dati

Una struttura dati è un pratico standard di archiviazione dei dati per tutti i linguaggi, come la struttura dati del grafico Python o la struttura dati del grafico Java. La padronanza di tutti i tipi di grafici dovrebbe essere una priorità per chiunque aspiri a studiare le strutture dei dati. Poiché la teoria dei grafi ha molte applicazioni nella vita reale, diventano vitali nelle strutture di dati.

I vari tipi di grafici nelle strutture dati possono essere elencati di seguito:

1. Grafico nullo

Come suggerisce il nome, il grafico nullo è vuoto; in altre parole, è un grafico senza spigoli. Consiste solo di vertici isolati nel grafico con un insieme di archi vacante.

2. Grafico finito

Se il numero di spigoli e nodi è costituito da un numero finito in un grafo, allora il grafo è noto come grafo finito.

3. Grafico infinito

Se non si può dare un numero finito al numero di nodi e al numero di spigoli in un grafico, il grafico è noto come un grafico infinito. I grafici infiniti non sono numerabili, il che significa che non puoi contare il numero di nodi o spigoli in questo tipo di grafico.

4. Grafico semplice

Un grafo si dice semplice quando c'è un solo arco tra una coppia di vertici. Pertanto, due nodi sono collegati da un bordo in un grafico, che può identificare una relazione definita tra di loro.

5. Grafico multiplo

Se una coppia di nodi è connessa con più bordi in un grafico, allora il grafico è noto come multi-grafo. Un multigrafo non è costituito da self-loop. Esistono due tipi di spigoli che possono esistere in un multigrafo. Sono:

• Bordi paralleli

I bordi che corrono paralleli, come due strade parallele che vanno da una sorgente alla stessa destinazione, sono noti come bordi paralleli.

• Ciclo continuo

Questo è un bordo i cui vertici di origine e destinazione sono gli stessi.

Dai un'occhiata ai nostri programmi di scienza dei dati negli Stati Uniti

6. Grafico orientato

Un grafo si dice orientato se tutti gli archi presenti tra due nodi o vertici hanno una direzione definita. Un grafico orientato è anche noto come digramma. Possiamo determinare il nodo iniziale e finale guardando un grafico diretto. Ricorda, tutti gli spigoli in un grafo orientato devono essere orientati per essere chiamati grafi orientati.

7. Grafico non orientato

Un grafo si dice non orientato se è difficile identificare il nodo iniziale e quello finale osservando i suoi bordi. Proprio come un grafo orientato, gli spigoli devono essere non orientati perché possa essere chiamato grafo non orientato.

8. Grafico connesso

Un grafo connesso è un grafo in cui esiste almeno un percorso tra tutti i nodi. In termini più semplici, se parti da un nodo in un grafo connesso, dovresti essere in grado di visitare ogni nodo presente nel grafo. Quindi, dovrebbe esserci almeno un percorso per ogni nodo.

9. Grafico disconnesso

In questo tipo di grafico, non esiste alcun bordo tra una coppia di nodi o vertici. Pertanto, a differenza dei grafi connessi, non è possibile raggiungere tutti i nodi da qualsiasi vertice. Se una qualsiasi coppia di vertici non ha un percorso tra di loro, si parla di grafo disconnesso.

10. Grafico completo

Un grafo è considerato completo solo quando esiste un bordo tra ogni nodo, il che significa che un bordo collegherà tutti i vertici nel grafo. Un grafo completo su n vertici è indicato come Kn e il numero di spigoli nel grafo è nC2 .

11. Grafico ciclico

Un grafico dovrebbe avere almeno una componente ciclica per essere considerato un grafico ciclico. Al contrario, se il grafo non contiene alcun ciclo, è considerato un grafo aciclico.

12. Grafico regolare

In un grafico regolare, tutti i vertici dovrebbero avere lo stesso grado. Il grado di un nodo può essere definito come il numero di nodi ad esso connessi. Pertanto, in un grafo regolare, tutti i nodi dovrebbero essere collegati allo stesso numero di nodi.

13. Grafico bipartito

Affinché un grafo sia bipartito, deve soddisfare i seguenti criteri.

• Il grafico dovrebbe essere diviso in insiemi di vertici.
• I bordi dovrebbero formarsi solo tra un gruppo di nodi e l'altro lato. Questa regola impedisce la connessione tra due vertici dello stesso insieme di nodi.
• I due gruppi non dovrebbero avere vertici comuni tra di loro.

Un grafico che segue tutte le regole di cui sopra dovrebbe essere considerato un grafico bipartito.

14. Grafico etichettato

I bordi nei grafici possono essere ponderati. Un peso associato a un bordo può essere inteso come il costo del viaggio attraverso quel bordo. Questi valori possono essere basati su un parametro fisso e possono cambiare tra i grafici. Ora, se tutti i bordi hanno un certo peso ad essi associato, allora quel grafico può essere definito un grafico etichettato.

15. Grafico aciclico diretto

Un grafico aciclico diretto è una combinazione di grafici diretti e aciclici in cui i bordi diretti del grafico non creano alcuna forma di ciclo. Al contrario, un grafo ciclico orientato è un grafo con spigoli orientati che forma un ciclo.

Applicazione del grafico nella struttura dei dati

L'applicazione più importante di un grafico in informatica è la rappresentazione del flusso di calcolo. Alcuni altri famosi casi usati di grafici sono:

1. Google Maps

In Google Maps, le strutture di dati dei grafici definiscono e calcolano il sistema di trasporto. Quando una strada incontra un'altra strada e forma un incrocio, viene considerata un nodo e la strada tra due di questi nodi viene trattata come un bordo. Pertanto, Google Maps ti trova la via più breve e veloce per raggiungere la tua destinazione utilizzando la struttura dei dati del grafico.

2. Facebook

Facebook utilizza grafici non orientati per identificare un utente e i suoi amici. Ogni utente viene trattato come i vertici e le connessioni che li uniscono come amici sono i bordi della rete. Con algoritmi basati sulla struttura dei dati del grafico, Facebook suggerisce "persone che potresti conoscere" e mostra "amici in comune".

3. Rete mondiale

Il World Wide Web è un esempio di grafico diretto. È anche l'idea alla base del sistema di ranking di Google. Nel sistema World Wide Web, ogni sito Web e app Web viene trattato come un nodo o vertici e i collegamenti da un sito Web a un altro sono considerati il ​​bordo.

4. Sistema operativo

Il sistema operativo è un caso comunemente usato di grafici di allocazione delle risorse che utilizza ogni processo e risorsa come nodi o vertici. I bordi si verificano tra le risorse al processo allocato o dal processo richiedente alle risorse richieste. A volte questo ciclo potrebbe formare un ciclo infinito, inizializzando lo stallo.

5. Sistema di mappatura

Il tuo GPS è un caso di grafici comunemente usato per individuare ristoranti, negozi e luoghi nelle vicinanze che scegli di cercare con l'aiuto di questa tecnologia.

6.Microsoft Excel

I grafici aciclici diretti o DAG vengono utilizzati in Microsoft Excel.

7. L'algoritmo di Dijkstra

L'algoritmo Dijkstra utilizza la struttura dei dati del grafico per identificare il percorso più breve tra due o, in alcuni casi, più di due nodi.

8. Reti di volo:

Il calcolo delle reti di volo ottimizzate è un'altra applicazione nella vita reale della struttura dei dati del grafico. Se si considerano gli aeroporti come nodi e le rotte come bordi, i dati si adattano perfettamente ai criteri dei grafici. Ecco perché, con l'aiuto di vari algoritmi avanzati, vengono determinate le migliori rotte tra due aeroporti o nodi.

Queste sono le varie applicazioni dei grafici nella struttura dei dati , utilizzate in tutto il mondo in varie applicazioni e sistemi per organizzare e mantenere il loro buon funzionamento,

Inizia il tuo viaggio come data scientist

Se vuoi diventare un data scientist e gestire i dati con tatto utilizzando i vari grafici che abbiamo appreso, dai un'occhiata a una vasta gamma di corsi di data science su upGrad. Uno dei corsi più popolari è il corso PG-IIITB su Data Science , un corso eccellente per aspiranti data scientist in erba per iniziare!

Ecco cosa offre il corso.

• Supporto professionale a 360 gradi da parte di esperti e mentori del settore
• Esperienza pratica con progetti di settore e case study dettagliati per valutare i progressi regolari
• Collegamento in rete con esperti di data science in tutti i settori, a livello globale

Puoi anche controllare tutti gli altri corsi upGrad su Data Science .