Graphs

Introduzione

I graphs (grafi) sono una struttura dati fondamentale per rappresentare relazioni e connessioni tra elementi. A differenza di altre strutture dati che abbiamo visto, i graphs permettono connessioni multiple e non lineari tra gli elementi.

Terminologia

Prima di approfondire i graphs, è importante comprendere la terminologia corretta:

• Vertex (vertice): un elemento del grafo. Talvolta chiamato anche “node” (nodo), ma “vertex” è la terminologia corretta
• Edge (segmento): una connessione tra due vertici. Talvolta chiamata “connection”, ma “edge” è la terminologia corretta

1
// Rappresentazione grafica di un grafo
2
//  [A] ——— [B]
3
//   |       |
4
//   |       |
5
//  [E] ——— [C] ——— [D]

Caratteristiche dei Graphs

Connessioni multiple

Una caratteristica fondamentale dei graphs è che non ci sono limitazioni al numero di connessioni che un vertice può avere. Un vertice può connettersi a uno, due, o molti altri vertici.

1
// Esempio: vertice A può connettersi a B, E, e molti altri
2
//  [A] ——— [B]
3
//   | \
4
//   |  \
5
//  [E]  [C]

Edges pesati (Weighted Edges)

Gli edges possono avere un peso (weight) che rappresenta il costo o la distanza tra due vertici. Questo è utile per problemi di routing e ottimizzazione.

1
// Esempio: grafo con edges pesati
2
//  [A] ———5——— [B]
3
//   |           |
4
//   3           2
5
//   |           |
6
//  [E] ———1——— [C]

Caso d’uso: In un’app di navigazione GPS, gli edges rappresentano strade e i pesi rappresentano il tempo di percorrenza o la distanza. Il percorso più efficiente non è necessariamente quello con meno “salti”, ma quello con il peso totale minore.

Edges bidirezionali vs unidirezionali

Bidirezionali (Undirected)

Gli edges bidirezionali rappresentano relazioni reciproche. Se A è connesso a B, allora B è connesso ad A.

1
// Rappresentazione: linee senza frecce
2
//  [A] ——— [B]
3
// Rappresenta: A ↔ B (bidirezionale)

Esempio: In Facebook, se tu sei amico di qualcuno, quella persona è amica di te. La relazione è bidirezionale.

Unidirezionali (Directed)

Gli edges unidirezionali rappresentano relazioni direzionali. Se A punta a B, non significa che B punti ad A.

1
// Rappresentazione: linee con frecce
2
//  [A] ——→ [B]
3
// Rappresenta: A → B (unidirezionale)

Esempio: Su Twitter o Instagram, puoi seguire qualcuno senza che quella persona ti segua. La relazione è unidirezionale.

Nota: In questi appunti implementeremo graphs con edges bidirezionali e non pesati per semplicità, ma è importante sapere che esistono anche graphs diretti e pesati.

Graphs e altre strutture dati

I graphs sono una struttura dati molto generale. Infatti, altre strutture dati che abbiamo visto sono casi speciali di graphs:

1. Binary Tree: è un grafo con la limitazione che ogni vertice può avere al massimo due connessioni e le connessioni sono direzionali
2. Linked List: è un tipo di tree, e quindi anche un tipo di grafo
3. Tree: è un grafo senza cicli

Conclusione: Linked Lists → Trees → Graphs (gerarchia di generalità)

Rappresentazione dei Graphs

Esistono due modi principali per rappresentare un grafo in memoria:

1. Adjacency Matrix (Matrice di adiacenza)

Una adjacency matrix è una matrice bidimensionale dove ogni riga e colonna rappresenta un vertice. Il valore nella cella [i][j] indica se esiste un edge tra il vertice i e il vertice j.

1
// Grafo: A ↔ B, B ↔ C, C ↔ D, D ↔ E, E ↔ A
2
//
3
// Adjacency Matrix:
4
//      A  B  C  D  E
5
//   A [0][1][0][0][1]
6
//   B [1][0][1][0][0]
7
//   C [0][1][0][1][0]
8
//   D [0][0][1][0][1]
9
//   E [1][0][0][1][0]

Caratteristiche:

• Se il grafo ha edges bidirezionali, la matrice è simmetrica rispetto alla diagonale
• La diagonale principale contiene sempre zeri (un vertice non può connettersi a se stesso)
• Se il grafo ha edges direzionali, la matrice non è simmetrica
• Per edges pesati, invece di 0/1, si memorizzano i pesi

Esempio con edges direzionali:

1
// Se A → B ma B ↛ A:
2
//      A  B
3
//   A [0][1]
4
//   B [0][0]  ← non simmetrico!

Esempio con edges pesati:

1
// Invece di 0/1, memorizziamo i pesi:
2
//      A  B  C
3
//   A [0][5][0]
4
//   B [5][0][3]
5
//   C [0][3][0]

2. Adjacency List (Lista di adiacenza)

Una adjacency list è un oggetto (o hash table) dove ogni chiave è un vertice e il valore è un array contenente tutti i vertici connessi.

1
// Stesso grafo: A ↔ B, B ↔ C, C ↔ D, D ↔ E, E ↔ A
2
//
3
// Adjacency List:
4
{
5
  A: ['B', 'E'],
6
  B: ['A', 'C'],
7
  C: ['B', 'D'],
8
  D: ['C', 'E'],
9
  E: ['A', 'D']
10
}

Vantaggio: Molto più semplice e intuitivo da implementare e comprendere.

Nota: In questi appunti useremo l’adjacency list perché è più semplice da implementare e più efficiente in termini di spazio per la maggior parte dei casi d’uso.

Complessità temporale (Big O)

Confrontiamo le complessità delle operazioni principali tra adjacency matrix e adjacency list:

Space Complexity (Complessità spaziale)

Problema con adjacency matrix: Per grafi sparsi (pochi edges rispetto ai vertici possibili), la maggior parte della matrice contiene zeri. Ad esempio, se Facebook avesse 1 miliardo di utenti e ogni persona avesse 1000 amici, la matrice avrebbe 1 miliardo × 1 miliardo = 10¹⁸ celle, ma solo 10¹² connessioni reali. Il rapporto tra zeri e uno sarebbe 1 milione a 1!

Add Vertex (Aggiungere un vertice)

Add Edge (Aggiungere un edge)

Remove Edge (Rimuovere un edge)

Nota: Per l’adjacency list, la complessità dipende dal numero di edges del vertice. Nel caso peggiore, un vertice può essere connesso a tutti gli altri vertici, quindi O(E).

Remove Vertex (Rimuovere un vertice)

Ottimizzazione per adjacency list: Se il grafo è bidirezionale, possiamo usare l’array del vertice da rimuovere per trovare tutti i vertici connessi, evitando di scansionare tutti i vertici. Questo migliora l’efficienza.

Confronto riepilogativo

Legenda: Verde = Efficiente | Giallo = Moderato | Rosso = Meno efficiente

Conclusione: L’adjacency list è generalmente più efficiente per grafi sparsi (pochi edges), mentre l’adjacency matrix può essere migliore per grafi densi (molti edges) quando si ha bisogno di verificare rapidamente se esiste un edge tra due vertici.

Implementazione

Costruttore del Graph

Il costruttore crea un grafo vuoto usando un oggetto per l’adjacency list:

1
class Graph {
2
  constructor() {
3
    // Crea un oggetto vuoto per memorizzare l'adjacency list
4
    // Ogni chiave sarà un vertice, ogni valore sarà un array di vertici connessi
5
    this.adjacencyList = {};
6
  }
7
}

Spiegazione:

• this.adjacencyList = {}: crea un oggetto vuoto che conterrà tutti i vertici e le loro connessioni
• Ogni vertice sarà una chiave nell’oggetto
• Ogni valore sarà un array contenente i vertici connessi

Risultato in memoria:

1
{
2
  adjacencyList: {}
3
}

Add Vertex - Aggiungere un vertice

Aggiunge un nuovo vertice al grafo. Complessità: O(1)

Logica:

1. Verifica se il vertice esiste già (non possiamo avere duplicati)
2. Se non esiste, aggiungi il vertice con un array vuoto
3. Ritorna true se aggiunto con successo, false altrimenti

1
addVertex(vertex) {
2
  // Verifica se il vertice non esiste già nell'adjacency list
3
  if (!this.adjacencyList[vertex]) {
4
    // Inizializza un array vuoto per il nuovo vertice
5
    // Questo array conterrà tutti i vertici connessi a questo vertice
6
    this.adjacencyList[vertex] = [];
7
    // Ritorna true, indicando che il vertice è stato aggiunto con successo
8
    return true;
9
  }
10
  // Se il vertice esiste già, ritorna false
11
  return false;
12
}

Edge cases gestiti:

• Vertice duplicato: ritorna false senza modificare il grafo
• Vertice valido: aggiunge il vertice e ritorna true

Esempio di utilizzo:

1
const myGraph = new Graph();
2
myGraph.addVertex('A');  // true
3
myGraph.addVertex('A');  // false (duplicato)
4
// Risultato: { A: [] }

Add Edge - Aggiungere un edge

Aggiunge un edge bidirezionale tra due vertici. Complessità: O(1)

Logica:

1. Verifica che entrambi i vertici esistano nel grafo
2. Aggiungi vertex2 all’array di vertex1
3. Aggiungi vertex1 all’array di vertex2 (bidirezionale)
4. Ritorna true se aggiunto con successo, false altrimenti

1
addEdge(vertex1, vertex2) {
2
  // Verifica che entrambi i vertici esistano nel grafo
3
  if (this.adjacencyList[vertex1] && this.adjacencyList[vertex2]) {
4
    // Aggiungi vertex2 all'array di connessioni di vertex1
5
    this.adjacencyList[vertex1].push(vertex2);
6
    // Aggiungi vertex1 all'array di connessioni di vertex2
7
    // Questo rende l'edge bidirezionale
8
    this.adjacencyList[vertex2].push(vertex1);
9
    // Ritorna true, indicando che l'edge è stato aggiunto con successo
10
    return true;
11
  }
12
  // Se uno o entrambi i vertici non esistono, ritorna false
13
  return false;
14
}

Edge cases gestiti:

• Vertice inesistente: ritorna false senza modificare il grafo
• Entrambi i vertici esistenti: aggiunge l’edge bidirezionale e ritorna true

Esempio di utilizzo:

1
const myGraph = new Graph();
2
myGraph.addVertex('A');
3
myGraph.addVertex('B');
4
myGraph.addEdge('A', 'B');  // true
5
myGraph.addEdge('A', 'C');  // false (C non esiste)
6
// Risultato: { A: ['B'], B: ['A'] }

Remove Edge - Rimuovere un edge

Rimuove un edge bidirezionale tra due vertici. Complessità: O(E)

Logica:

1. Verifica che entrambi i vertici esistano nel grafo
2. Rimuovi vertex2 dall’array di vertex1 usando filter
3. Rimuovi vertex1 dall’array di vertex2 usando filter
4. Ritorna true se rimosso con successo, false altrimenti

Nota: Usiamo filter invece di splice perché è più pulito e funzionale. filter crea un nuovo array contenente tutti gli elementi che soddisfano la condizione (tutti tranne quello da rimuovere).

1
removeEdge(vertex1, vertex2) {
2
  // Verifica che entrambi i vertici esistano nel grafo
3
  if (this.adjacencyList[vertex1] && this.adjacencyList[vertex2]) {
4
    // Rimuovi vertex2 dall'array di connessioni di vertex1
5
    // filter ritorna un nuovo array con tutti gli elementi tranne vertex2
6
    this.adjacencyList[vertex1] = this.adjacencyList[vertex1]
7
      .filter(v => v !== vertex2);
8
    // Rimuovi vertex1 dall'array di connessioni di vertex2
9
    // filter ritorna un nuovo array con tutti gli elementi tranne vertex1
10
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2]
11
      .filter(v => v !== vertex1);
12
    // Ritorna true, indicando che l'edge è stato rimosso con successo
13
    return true;
14
  }
15
  // Se uno o entrambi i vertici non esistono, ritorna false
16
  return false;
17
}

Spiegazione di filter:

• filter è un metodo degli array in JavaScript che crea un nuovo array
• Prende una funzione callback che ritorna true per gli elementi da mantenere
• v => v !== vertex2 mantiene tutti i vertici tranne vertex2
• Questo è equivalente a rimuovere vertex2 dall’array

Edge cases gestiti:

• Vertice inesistente: ritorna false senza modificare il grafo
• Entrambi i vertici esistenti: rimuove l’edge bidirezionale e ritorna true

Esempio di utilizzo:

1
const myGraph = new Graph();
2
myGraph.addVertex('A');
3
myGraph.addVertex('B');
4
myGraph.addEdge('A', 'B');
5
// Risultato: { A: ['B'], B: ['A'] }
6
myGraph.removeEdge('A', 'B');
7
// Risultato: { A: [], B: [] }

Remove Vertex - Rimuovere un vertice

Rimuove un vertice e tutti i suoi edges dal grafo. Complessità: O(V + E)

Logica:

1. Verifica che il vertice esista nel grafo
2. Rimuovi prima tutti gli edges: itera attraverso l’array di connessioni del vertice
3. Per ogni vertice connesso, rimuovi il riferimento usando removeEdge
4. Poi rimuovi il vertice: elimina la chiave dall’oggetto
5. Ritorna il grafo (per method chaining) o undefined se il vertice non esiste

Ottimizzazione: Grazie agli edges bidirezionali, possiamo usare l’array del vertice da rimuovere per trovare tutti i vertici connessi, evitando di scansionare tutti i vertici del grafo.

1
removeVertex(vertex) {
2
  // Se il vertice non esiste nell'adjacency list, ritorna undefined
3
  if (!this.adjacencyList[vertex]) return undefined;
4

5
  // Itera finché l'array di connessioni del vertice non è vuoto
6
  // Questo rimuove tutti gli edges connessi a questo vertice
7
  while (this.adjacencyList[vertex].length) {
8
    // Rimuovi l'ultimo elemento dall'array di connessioni
9
    // Questo ci dice quale vertice è connesso al vertice che stiamo rimuovendo
10
    let temp = this.adjacencyList[vertex].pop();
11
    // Usa removeEdge per rimuovere l'edge tra vertex e temp
12
    // Questo rimuove anche il riferimento da temp a vertex (bidirezionale)
13
    this.removeEdge(vertex, temp);
14
  }
15

16
  // Dopo aver rimosso tutti gli edges, elimina il vertice stesso
17
  delete this.adjacencyList[vertex];
18

19
  // Ritorna il grafo per permettere il method chaining
20
  return this;
21
}

Spiegazione dettagliata:

1. Verifica esistenza: Se il vertice non esiste, ritorna undefined immediatamente
2. Rimozione edges: Il while loop continua finché l’array di connessioni non è vuoto
3. Pop e removeEdge: pop() rimuove l’ultimo elemento dall’array e lo salva in temp. Poi removeEdge(vertex, temp) rimuove l’edge bidirezionale tra vertex e temp
4. Eliminazione vertice: delete rimuove la chiave dall’oggetto
5. Return: Ritorna this per permettere il method chaining

Vantaggio dell’ottimizzazione: Invece di scansionare tutti i vertici del grafo per trovare i riferimenti al vertice da rimuovere, usiamo direttamente l’array del vertice. Questo è molto più efficiente!

Edge cases gestiti:

• Vertice inesistente: ritorna undefined senza modificare il grafo
• Vertice connesso: rimuove prima tutti gli edges, poi il vertice
• Vertice isolato: rimuove direttamente il vertice (l’array è già vuoto)

Esempio di utilizzo:

1
const myGraph = new Graph();
2
myGraph.addVertex('A');
3
myGraph.addVertex('B');
4
myGraph.addVertex('C');
5
myGraph.addEdge('A', 'B');
6
myGraph.addEdge('B', 'C');
7
// Risultato: { A: ['B'], B: ['A', 'C'], C: ['B'] }
8
myGraph.removeVertex('B');
9
// Risultato: { A: [], C: [] }
10
// L'edge A-B e B-C sono stati rimossi automaticamente

Implementazione completa

Ecco il codice completo della classe Graph:

1
class Graph {
2
  constructor() {
3
    // Crea un oggetto vuoto per memorizzare l'adjacency list
4
    this.adjacencyList = {};
5
  }
6

7
  addVertex(vertex) {
8
    // Verifica se il vertice non esiste già
9
    if (!this.adjacencyList[vertex]) {
10
      // Inizializza un array vuoto per il nuovo vertice
11
      this.adjacencyList[vertex] = [];
12
      return true;
13
    }
14
    return false;
15
  }
16

17
  addEdge(vertex1, vertex2) {
18
    // Verifica che entrambi i vertici esistano
19
    if (this.adjacencyList[vertex1] && this.adjacencyList[vertex2]) {
20
      // Aggiungi edge bidirezionale
21
      this.adjacencyList[vertex1].push(vertex2);
22
      this.adjacencyList[vertex2].push(vertex1);
23
      return true;
24
    }
25
    return false;
26
  }
27

28
  removeEdge(vertex1, vertex2) {
29
    // Verifica che entrambi i vertici esistano
30
    if (this.adjacencyList[vertex1] && this.adjacencyList[vertex2]) {
31
      // Rimuovi edge bidirezionale usando filter
32
      this.adjacencyList[vertex1] = this.adjacencyList[vertex1]
33
        .filter(v => v !== vertex2);
34
      this.adjacencyList[vertex2] = this.adjacencyList[vertex2]
35
        .filter(v => v !== vertex1);
36
      return true;
37
    }
38
    return false;
39
  }
40

41
  removeVertex(vertex) {
42
    // Se il vertice non esiste, ritorna undefined
43
    if (!this.adjacencyList[vertex]) return undefined;
44

45
    // Rimuovi tutti gli edges connessi al vertice
46
    while (this.adjacencyList[vertex].length) {
47
      let temp = this.adjacencyList[vertex].pop();
48
      this.removeEdge(vertex, temp);
49
    }
50

51
    // Elimina il vertice dall'adjacency list
52
    delete this.adjacencyList[vertex];
53

54
    // Ritorna il grafo per method chaining
55
    return this;
56
  }
57
}

Quando usare Graphs

Usa un Graph quando:

• Devi rappresentare relazioni complesse tra elementi: reti sociali, mappe, reti di computer
• Hai bisogno di navigazione tra elementi: routing, pathfinding, algoritmi di ricerca
• Le connessioni sono non lineari: non seguono una struttura gerarchica come i tree
• Devi risolvere problemi di ottimizzazione: percorso più breve, flusso massimo