Rappresentazione dei grafi

6.1 Matrice di adiacenza: come funziona, vantaggi e svantaggi.

Matrice di adiacenza — è un modo per rappresentare un grafo in forma di matrice quadrata di dimensioni n x n, dove n è il numero di nodi nel grafo. Gli elementi della matrice indicano la presenza o l'assenza di archi tra i nodi:

• Se c'è un arco tra i nodi i e j, allora l'elemento A[i][j] = 1 (oppure il peso dell'arco, se il grafo è ponderato).
• Se non c'è arco, allora A[i][j] = 0.

Esempio:

Per un grafo con nodi A, B, C e archi (A, B), (B, C) e (C, A), la matrice di adiacenza sarà:

Se tutti i nodi fossero collegati tra loro, la matrice di adiacenza sarebbe così:

Vantaggi:

• Semplicità: facile da capire e implementare.
• Accesso veloce: verifica della presenza di un arco tra due nodi eseguita in O(1).
• Adatto per grafi densi: efficiente per grafi con un gran numero di archi.

Svantaggi:

• Elevato consumo di memoria: richiede O(n^2) memoria, anche se il grafo contiene pochi archi (grafo sparso).
• Inefficiente per grafi sparsi: con un gran numero di nodi e pochi archi, la maggior parte degli elementi della matrice saranno zeri, portando a un uso inefficiente della memoria.

6.2 Liste di adiacenza: come funzionano, vantaggi e svantaggi.

Liste di adiacenza — è un modo per rappresentare un grafo in forma di array di liste. Ogni elemento dell'array corrisponde a un nodo del grafo e contiene una lista di tutti i nodi adiacenti.

Esempio:

Per un grafo con nodi A, B, C e archi (A, B), (B, C) e (C, A), le liste di adiacenza saranno:

Se tutti i nodi fossero collegati tra loro, le liste di adiacenza sarebbero così:

Vantaggi:

• Uso efficiente della memoria: richiede O(V + E) memoria, dove V è il numero di nodi e E è il numero di archi, rendendolo più adatto per grafi sparsi.
• Facilità di attraversamento: utile per eseguire operazioni di attraversamento del grafo (ad esempio, ricerca in ampiezza o in profondità).

Svantaggi:

• Accesso più complesso: la verifica della presenza di un arco tra due nodi richiede O(k) tempo, dove k è il numero di vicini del nodo.
• Struttura meno evidente: più complessa da implementare e comprendere rispetto a una matrice di adiacenza.

6.3 Confronto tra diversi metodi di rappresentazione dei grafi.

Confrontiamo i diversi metodi di rappresentazione dei grafi.

1. Matrice di adiacenza:

• Semplicità: facile da capire e implementare.
• Memoria: richiede O(n^2) memoria, che può essere inefficiente per grafi sparsi.
• Velocità d'accesso: la verifica della presenza di un arco è eseguita in O(1).
• Adatto: per grafi densi con un gran numero di archi.

2. Liste di adiacenza:

• Semplicità: meno evidenti rispetto alla matrice di adiacenza, ma ancora comprensibili.
• Memoria: richiedono O(V + E) memoria, che è più efficiente per grafi sparsi.
• Velocità d'accesso: la verifica della presenza di un arco è eseguita in O(k), dove k è il numero di vicini del nodo.
• Adatti: per grafi sparsi con un numero ridotto di archi.

Confronto:

Matrice di adiacenza è più adatta per grafi densi, dove la maggior parte dei nodi è collegata da archi, poiché fornisce un accesso rapido alle informazioni sugli archi ed è semplice da implementare.

Liste di adiacenza sono preferibili per grafi sparsi, dove il numero di archi è significativamente minore rispetto al numero di coppie possibili di nodi. Offrono un uso efficiente della memoria e sono comode per eseguire operazioni di attraversamento del grafo.