Matrice di Adiacenza

1. Cos'è la Matrice di Adiacenza?

La matrice di adiacenza è una rappresentazione basata su una tabella bidimensionale (array 2D) di dimensione $V \times V$, dove $V$ è il numero di vertici del grafo. Ciascuna riga $i$ e colonna $j$ corrisponde a un vertice.

L'elemento alla posizione $M[i][j]$ assume valori specifici in base alle caratteristiche del grafo:

Grafi non pesati: $M[i][j] = 1$ se esiste un arco che collega il nodo $i$ al nodo $j$; altrimenti $M[i][j] = 0$.
Grafi pesati: $M[i][j]$ memorizza direttamente il peso dell'arco tra $i$ e $j$, mentre i valori speciali (come $\infty$ o $0$) indicano l'assenza di collegamento diretto.

Esempio Pratico di Tabella

Consideriamo un grafo non orientato con 4 nodi ($0, 1, 2, 3$) e archi tra $(0,1), (0,2), (1,3), (2,3)$:

	0	1	2	3
0	0	1	1	0
1	1	0	0	1
2	1	0	0	1
3	0	1	1	0

2. Vantaggi, Svantaggi e Complessità

L'utilizzo della matrice di adiacenza offre compromessi ben definiti in termini di efficienza computazionale:

Controllo adiacenza in $\mathcal{O}(1)$: Verificare se due nodi $i$ e $j$ sono connessi richiede l'accesso diretto all'elemento $M[i][j]$, operazione immediata.
Occupazione di Memoria $\mathcal{O}(V^2)$: Indipendentemente dal numero reale di archi presenti, la matrice richiede sempre uno spazio proporzionale al quadrato dei vertici. Questo la rende inefficiente per i grafi sparsi (pochi archi).
Ricerca dei vicini in $\mathcal{O}(V)$: Per trovare tutti i nodi adiacenti a un vertice $i$, è necessario scorrere l'intera riga $i$ di lunghezza $V$.

                // Implementazione base di una Matrice di Adiacenza in C++
                #include <vector>
                #include <iostream>

                class AdjacencyMatrixGraph {
                int V;
                std::vector<std::vector<int>> matrix;
                public:
                AdjacencyMatrixGraph(int v) : V(v), matrix(v, std::vector<int>(v, 0)) {}

                void addEdge(int u, int v, int weight = 1) {
                matrix[u][v] = weight;
                matrix[v][u] = weight; // Solo se non orientato
                }
                };
            

3. Simulatore Interattivo: Generazione Matrice $V \times V$

Inserisci il numero di vertici del grafo per calcolare la dimensione strutturale e l'occupazione teorica di memoria della matrice.

matrix-engine@nexus-core:~# Adjacency Matrix Calculator

Numero di Vertici ($V$):

Azione:

> Inserisci il numero di vertici e avvia il calcolo dei parametri di memorizzazione.

1. Cos'è la Matrice di Adiacenza?

Esempio Pratico di Tabella

2. Vantaggi, Svantaggi e Complessità

3. Simulatore Interattivo: Generazione Matrice $V \times V$

Gestione della Privacy e dei Cookie