Come implementare i grafi in C

Tramite: O2O
Difficoltà: media
15

Introduzione

I grafi come gli esperti di informatica sanno, sono uno strumento molto potente per la rappresentazione dei problemi e molte volte anche dei problemi complessi. Infatti, le soluzioni ai cosiddetti problemi complessi possono essere trovate con i grafi che sono composti da algoritmi normali e soprattutto algoritmi avanzati. Un grafo è una coppia ovvero formato da due lettere ad esempio (V, E) dove V tende a rappresenta l'insieme di nodi, mentre E rappresenta l'insieme di coppie di nodi. Vediamo come implementare i grafi in C.

25

Le proprietà

Il grafo o i grafi possiedono delle proprietà che devono essere studiate in questo caso per la successiva implementazioni che vedremo. Innanzitutto i grafi possono essere orientati e non orientati. I grafi orientati sono chiamati così se l'insieme di archi o nodi "E" è una relazione binaria. Mentre quelli non orientati sono così se l'insieme dei nodi "E" è un insieme di coppie non ordinate.
In un grado non orientato, il grado di un vertice è il numero di nodi che da esso dipendono ha come grado 0. In quello orientato invece hanno tutti gradi uscente 2 ed entranti 1.

35

L'implementazione di un Grafo

L'implementazione di un grafo orientato è possibile da alcune liste, vediamo di seguito tramite una lista come implementare il grafo orientato.
typedef struct graph {
int nv; / numero di vertici del grafo
edge **adj; / vettore con le liste delle adiacenze
} graph;

typedef struct edge {
int key;
struct edge*next;}.

Continua la lettura
45

Aggiunta o rimozione di un arco

L'aggiunta degli archi all'interno dei grafi è molto importante e anche questi possono essere possibili tramite due liste una per l'aggiunta e uno per la rimozione.
L'aggiunta di un arco è possibile dalla seguente lista:
void g_add (graph *G, int u, int v) {
edge*new, *e;
new = (edge*) malloc (sizeof (edge));
if (new==NULL) printf ("ERRORE: impossibile allocare memoria ");
else{
new->key=v; new->next=NULL;
if (G->adj[u] = new;
else{
e=G->adj[u];
while (e->next!=NULL) e=e->next;
e->next=new;}}

mentre per la rimozione di un arco vediamo questa lista di seguito:
void g_remove_edge (graph *G, int u, int v) {
edge*prev; /l'arco precedente a quello da togliere /
edge *e; /l'arco preciso da togliere /
e=G->adj[u];
if (e->key==v)
G->adj[u] = e->next;
else{
prev=e;
while (prev->next->key != v)
prev=prev->next;
e=prev->next;
prev->next=e->next;}
free (e);
return;}

Questi sono i due metodi migliori per l'aggiunta o la rimozione di un arco all'interno di un grafo dopo ovviamente l'implementazione principali di un grafo di orientato che non orientato e anche dopo aver visto le proprietà principali. Un'altra versione molto importante è anche quella di stampa di un grafo che può essere attuata grazie al comando "g_print".

Potrebbe interessarti anche

Segnala contenuti non appropriati

Tipo di contenuto
Devi scegliere almeno una delle opzioni
Descrivi il problema
Devi inserire una descrizione del problema
Si è verificato un errore nel sistema. Riprova più tardi.
Verifica la tua identità
Devi verificare la tua identità
chiudi
Grazie per averci aiutato a migliorare la qualità dei nostri contenuti

Guide simili

Programmazione

Guida alla programmazione a basso livello

In questa guida tratteremo della programmazione a basso livello. Nei vari passi successivi all'introduzione vi rilascio molte informazioni molto utili che vi aiuteranno certamente a programmare sempre meglio a basso livello. Un consiglio che vi dò e...
Programmazione

Come spostare un file in Java

Spostare i file in Java potrebbe sembrare inizialmente un'operazione complessa, ma con un po' di attenzione potremo farlo semplicemente da soli, senza dunque rivolgerci ad un tecnico informatico specializzato. Così facendo, non solo potremo imparare...
Programmazione

Come imparare a programmare in C++

L'avvento del computer, ha richiesto la creazione di appositi linguaggi per facilitare la comunicazione tra utente e macchina. I linguaggi sono aumentati di numero e via via è aumentata anche la facilità di comunicazione tra questi due canali. Si parla...
Programmazione

Come definire una classe in C++

Attraverso la lettura di quest'interessante guida, andremo a occuparci del linguaggio C++. Per essere più specifici, come abbiamo avuto occasione di indicarvi nel titolo di questa guida, ci dedicheremo a spiegarvi come definire una classe all'interno...
Programmazione

Inserire elementi in una lista in C++

Molti programmatori Java o utenti principianti, trovano il linguaggio C++ uno tra i più ostici nel suo utilizzo. Java, noto per la sua semplicità, offre dei costrutti utili per gestire e manipolare una struttura dinamica quali una Lista di oggetti....
Programmazione

Come creare animazioni con HTML5

Dalla sua nascita, il linguaggio HTML ha subito diverse modifiche e miglioramenti che, col passare del tempo, l'hanno portato alla sua ultima versione: ovvero l'HTML5. Inizialmente HTML veniva usato per la creazione di siti web statici e anche molto spartani...
Programmazione

Come programmare in Assembler

L'Assembler, o Assembly, è un linguaggio di programmazione a basso livello, ovvero più vicino alla macchina, perciò molto più complicato da utilizzare per il programmatore, in quanto, per poter effettuare elaborazioni, elementari per i linguaggi ad...
Programmazione

Come inserire codice javascript in un html

La programmazione informatica è complessa, ma non se si hanno dalla propria le giuste basi che solo uno specialista (o un buon libro di testo) è in grado di dare. Detta in modo molto semplice, la programmazione si basa sulla scrittura di codici attraverso...
I presenti contributi sono stati redatti dagli autori ivi menzionati a solo scopo informativo tramite l’utilizzo della piattaforma www.o2o.it e possono essere modificati dagli stessi in qualsiasi momento. Il sito web, www.o2o.it e Arnoldo Mondadori Editore S.p.A. (già Banzai Media S.r.l. fusa per incorporazione in Arnoldo Mondadori Editore S.p.A.), non garantiscono la veridicità, correttezza e completezza di tali contributi e, pertanto, non si assumono alcuna responsabilità in merito all’utilizzo delle informazioni ivi riportate. Per maggiori informazioni leggi il “Disclaimer »”.