Come implementare i grafi in C

tramite: O2O
Difficoltà: media
14

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.

24

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.

34

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
44

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

Come implementare gli alberi in C

In informatica per rappresentare dei dati si usano le strutture dati. Le strutture dati sono dei metodi per organizzare dati. A seconda delle operazioni che vogliamo fare su un insieme di dati, possiamo scegliere una struttura dati invece che un'altra....
Programmazione

Realizzare una semplice finestra grafica in Java

Java è un linguaggio di programmazione interamente dedicato agli oggetti ed offre costrutti utili, semplici e intuitivi per gestire ed implementare la totalità dei compiti che un programmatore desidera. La guida di oggi vuole mostrare come realizzare...
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 realizzare un'agenda personalizzata

Mediante tale tutorial vi spiegheremo come realizzare un'agenda personalizzata usando il linguaggio di programmazione Java. Lo scopo che vi vogliamo far capire è quello senza l'uso dell'interfaccia grafica, e quindi quello della struttura di un'agenda...
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

Il metodo di ordinamento Quicksort

Chiunque di noi (programmatori) si è trovato davanti alla necessità di dover ordinare dei dati, e sappiamo che, siano essi pochi o molti, il coefficiente di difficoltà per risolvere il problema rimane lo stesso. Proprio per agevolare la vita a chiunque...
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 Scrivere Su Schermo In Linguaggio C

Il linguaggio C è un linguaggio di programmazione classificabile come 'general purpose', nel senso che non è specifico per applicazioni particolari (gestionali, scientifiche, ludiche, ecc.), ma risulta adatto per la maggior parte delle esigenze informatiche....
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 »”.