🚀 Nuova versione beta disponibile! Feedback o problemi? Contattaci

Grafi in C

Codegrind Team•Aug 23 2024

I grafi sono una struttura dati fondamentale utilizzata per rappresentare relazioni complesse tra oggetti. Un grafo è composto da nodi (o vertici) e collegamenti (o archi) tra di essi. I grafi sono ampiamente utilizzati in molti campi, come il networking, l’intelligenza artificiale, la teoria dei giochi, e molto altro. In questa guida, esploreremo come implementare grafi in C, come attraversarli e le loro applicazioni più comuni.

Cos’è un Grafo?

Un grafo è una struttura composta da un insieme di nodi collegati tra loro da archi. I grafi possono essere:

  • Orientati: Gli archi hanno una direzione specifica.
  • Non Orientati: Gli archi non hanno direzione e rappresentano una relazione bidirezionale.
  • Ponderati: Gli archi hanno un peso associato, rappresentando una “costo” o “distanza” tra i nodi.
  • Non Ponderati: Gli archi non hanno peso.

Tipi di Rappresentazione dei Grafi

Ci sono due modi comuni per rappresentare un grafo in C:

  1. Matrice di Adiacenza: Una matrice in cui l’elemento G[i][j] è 1 se c’è un arco tra il nodo i e il nodo j, altrimenti è 0.
  2. Lista di Adiacenza: Un array di liste, in cui ogni elemento dell’array è una lista dei nodi adiacenti a un nodo specifico.

Implementazione di un Grafo usando la Matrice di Adiacenza

Dichiarazione della Matrice di Adiacenza

#include <stdio.h>
#include <stdlib.h>

#define N 5  // Numero di nodi

void init_grafo(int grafo[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            grafo[i][j] = 0;  // Inizializza la matrice con 0
        }
    }
}

Aggiunta di un Arco

void aggiungi_arco(int grafo[N][N], int u, int v) {
    grafo[u][v] = 1;  // Aggiunge un arco da u a v
    grafo[v][u] = 1;  // Per un grafo non orientato, aggiungi anche l'arco inverso
}

Stampa del Grafo

void stampa_grafo(int grafo[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", grafo[i][j]);
        }
        printf("\n");
    }
}

Esempio Completo

int main() {
    int grafo[N][N];
    init_grafo(grafo);

    aggiungi_arco(grafo, 0, 1);
    aggiungi_arco(grafo, 0, 4);
    aggiungi_arco(grafo, 1, 2);
    aggiungi_arco(grafo, 1, 3);
    aggiungi_arco(grafo, 1, 4);
    aggiungi_arco(grafo, 2, 3);
    aggiungi_arco(grafo, 3, 4);

    printf("Matrice di Adiacenza:\n");
    stampa_grafo(grafo);

    return 0;
}

Uscita:

Matrice di Adiacenza:
0 1 0 0 1
1 0 1 1 1
0 1 0 1 0
0 1 1 0 1
1 1 0 1 0

Implementazione di un Grafo usando la Lista di Adiacenza

La lista di adiacenza è più efficiente in termini di spazio, specialmente per grafi sparsi (grafi con pochi archi rispetto al numero di nodi).

Definizione della Struttura del Nodo

struct Nodo {
    int vertice;
    struct Nodo* prossimo;
};

Definizione della Lista di Adiacenza

struct ListaAdiacenza {
    struct Nodo* testa;
};

Definizione del Grafo

struct Grafo {
    int numero_nodi;
    struct ListaAdiacenza* array;
};

Creazione di un Grafo

struct Grafo* crea_grafo(int numero_nodi) {
    struct Grafo* grafo = (struct Grafo*)malloc(sizeof(struct Grafo));
    grafo->numero_nodi = numero_nodi;
    grafo->array = (struct ListaAdiacenza*)malloc(numero_nodi * sizeof(struct ListaAdiacenza));

    for (int i = 0; i < numero_nodi; i++)
        grafo->array[i].testa = NULL;

    return grafo;
}

Aggiunta di un Arco alla Lista di Adiacenza

void aggiungi_arco(struct Grafo* grafo, int src, int dest) {
    struct Nodo* nuovo_nodo = (struct Nodo*)malloc(sizeof(struct Nodo));
    nuovo_nodo->vertice = dest;
    nuovo_nodo->prossimo = grafo->array[src].testa;
    grafo->array[src].testa = nuovo_nodo;

    // Poiché il grafo è non orientato, aggiungiamo anche l'arco inverso
    nuovo_nodo = (struct Nodo*)malloc(sizeof(struct Nodo));
    nuovo_nodo->vertice = src;
    nuovo_nodo->prossimo = grafo->array[dest].testa;
    grafo->array[dest].testa = nuovo_nodo;
}

Stampa del Grafo

void stampa_grafo(struct Grafo* grafo) {
    for (int v = 0; v < grafo->numero_nodi; ++v) {
        struct Nodo* nodo = grafo->array[v].testa;
        printf("\n Lista di adiacenza per il nodo %d\n head ", v);
        while (nodo) {
            printf("-> %d", nodo->vertice);
            nodo = nodo->prossimo;
        }
        printf("\n");
    }
}

Esempio Completo

int main() {
    int numero_nodi = 5;
    struct Grafo* grafo = crea_grafo(numero_nodi);

    aggiungi_arco(grafo, 0, 1);
    aggiungi_arco(grafo, 0, 4);
    aggiungi_arco(grafo, 1, 2);
    aggiungi_arco(grafo, 1, 3);
    aggiungi_arco(grafo, 1, 4);
    aggiungi_arco(grafo, 2, 3);
    aggiungi_arco(grafo, 3, 4);

    stampa_grafo(grafo);

    return 0;
}

Uscita:

Lista di adiacenza per il nodo 0
 head -> 4-> 1

Lista di adiacenza per il nodo 1
 head -> 4-> 3-> 2-> 0

Lista di adiacenza per il nodo 2
 head -> 3-> 1

Lista di adiacenza per il nodo 3
 head -> 4-> 2-> 1

Lista di adiacenza per il nodo 4
 head -> 3-> 1-> 0

Traversamento di un Grafo

Due algoritmi comuni per attraversare un grafo sono:

1. Depth-First Search (DFS)

Il DFS esplora il piĂą possibile lungo ogni ramo prima di tornare indietro.

void DFS_util(int v, int visitato[], struct Grafo* grafo) {
    visitato[v] = 1;
    printf("%d ", v);

    struct Nodo* nodo = grafo->array[v].testa;
    while (nodo) {
        int adj = nodo->vertice;
        if (!visitato[adj])
            DFS_util(adj, visitato, grafo);
        nodo = nodo->prossimo;
    }
}

void DFS(struct Grafo* grafo, int v) {
    int* visitato = (int*)malloc(grafo->numero_nodi * sizeof(int));
    for (int i = 0; i < grafo->numero_nodi; i++)
        visitato[i] = 0;

    DFS_util(v, visitato, grafo);
}

2. Breadth-First Search (BFS)

Il BFS esplora tutti i vicini di un nodo prima di passare ai nodi di livello successivo.

void BFS(struct Grafo* grafo, int start) {
    int* visitato = (int*)malloc(grafo->numero_nodi * sizeof(int));
    for (int i =

0; i < grafo->numero_nodi; i++)
        visitato[i] = 0;

    struct Queue* queue = crea_queue(grafo->numero_nodi);

    visitato[start] = 1;
    enqueue(queue, start);

    while (!is_empty(queue)) {
        int v = dequeue(queue);
        printf("%d ", v);

        struct Nodo* nodo = grafo->array[v].testa;
        while (nodo) {
            int adj = nodo->vertice;
            if (!visitato[adj]) {
                visitato[adj] = 1;
                enqueue(queue, adj);
            }
            nodo = nodo->prossimo;
        }
    }
}

Applicazioni Comuni dei Grafi

I grafi sono utilizzati in numerose applicazioni pratiche:

  • Reti di Comunicazione: Per modellare le connessioni tra dispositivi.
  • Social Networks: Per rappresentare le connessioni tra persone.
  • Intelligenza Artificiale: Per rappresentare spazi di ricerca o reti neurali.
  • Percorsi Minimi: Algoritmi come Dijkstra sono usati per trovare il percorso piĂą breve in un grafo ponderato.

Conclusioni

I grafi sono una struttura dati essenziale per rappresentare relazioni complesse e risolvere problemi in cui gli oggetti sono interconnessi. Comprendere come implementare, attraversare e manipolare grafi in C è fondamentale per affrontare una vasta gamma di problemi in informatica e ingegneria. Con un’implementazione efficiente, i grafi possono offrire soluzioni eleganti e potenti per problemi complessi.

PrecedenteAlberiSuccessivoUnion