Introduzione ai Grafi in Python

Un grafo è una struttura matematica composta da un insieme di nodi (o vertici) collegati tra loro da archi. I grafi sono usati per modellare reti di qualsiasi tipo: reti di computer, mappe stradali, social network, sistemi di routing.

Definizione e componenti

• Vertici (nodi): rappresentano gli “elementi” o “punti” del grafo. In una rete di computer, ogni dispositivo è un nodo.
• Archi (link): rappresentano le connessioni tra i nodi. Un arco può essere:
  • Orientato: la connessione ha una direzione (traffico unidirezionale)
  • Non orientato: la connessione è bidirezionale
• Pesi: valore assegnato agli archi per rappresentare costi o lunghezze (latenza, costo di trasmissione, distanza)

Applicazioni

Rappresentazione in Python

Il modo più comune è usare un dizionario con liste di adiacenza: le chiavi sono i nodi, i valori sono liste di tuple (nodo_adiacente, peso).

graph = {
    'A': [('B', 5), ('C', 1)],
    'B': [('A', 5), ('C', 2), ('D', 1)],
    'C': [('A', 1), ('B', 2), ('D', 4), ('E', 8)],
    'D': [('B', 1), ('C', 4), ('E', 3), ('F', 6)],
    'E': [('C', 8), ('D', 3)],
    'F': [('D', 6)],
}

def stampa_grafo(grafo):
    for nodo in grafo:
        print(f"{nodo} -> {grafo[nodo]}")

stampa_grafo(graph)

La lista di adiacenza è efficiente per grafi sparsi: memorizza solo le connessioni esistenti, senza sprecare memoria per le coppie non collegate.

Algoritmi di visita

DFS — Depth-First Search (visita in profondità)

Il DFS esplora il grafo “in profondità”: visita un nodo, poi tutti i suoi discendenti, prima di tornare indietro.

Pseudocodice:

Procedure DFS(grafo, nodo, visitato)
    if nodo non in visitato then
        aggiungi nodo a visitato
        per ogni vicino in grafo[nodo] do
            DFS(grafo, vicino, visitato)
    end if
End Procedure

Implementazione Python:

def dfs(grafo, nodo, visitato=None):
    if visitato is None:
        visitato = set()
    if nodo not in visitato:
        visitato.add(nodo)
        print(nodo, end=' ')
        for vicino, peso in grafo[nodo]:
            dfs(grafo, vicino, visitato)
    return visitato

dfs(graph, 'A')
# Output: A B C D E F

BFS — Breadth-First Search (visita in ampiezza)

Il BFS esplora il grafo “a livelli”: prima tutti i nodi a distanza 1 dal nodo iniziale, poi quelli a distanza 2, ecc.

Pseudocodice:

Procedure BFS(grafo, nodo_iniziale)
    crea coda vuota Q
    crea insieme visitato
    aggiungi nodo_iniziale a Q e a visitato

    mentre Q non è vuota do
        nodo = estrai il primo elemento da Q
        per ogni vicino in grafo[nodo] do
            se vicino non è in visitato allora
                aggiungi vicino a Q e a visitato
        fine per
    fine mentre
End Procedure

Implementazione Python:

from collections import deque

def bfs(grafo, nodo_iniziale):
    visitato = set()
    coda = deque([nodo_iniziale])
    visitato.add(nodo_iniziale)

    while coda:
        nodo = coda.popleft()
        print(nodo, end=' ')
        for vicino, peso in grafo[nodo]:
            if vicino not in visitato:
                visitato.add(vicino)
                coda.append(vicino)

bfs(graph, 'A')
# Output: A B C D E F

Cammini minimi

Algoritmo di Bellman-Ford

Funziona anche con pesi negativi e rileva cicli di peso negativo.

Pseudocodice:

Procedure BellmanFord(grafo, sorgente)
    distanza[v] = infinito per ogni nodo v
    distanza[sorgente] = 0

    per i = 1 a numero_nodi - 1 do
        per ogni arco (u, v) con peso w do
            se distanza[u] + w < distanza[v] allora
                distanza[v] = distanza[u] + w

    per ogni arco (u, v) con peso w do
        se distanza[u] + w < distanza[v] allora
            segnala "ciclo di peso negativo"

    restituisci distanza
End Procedure

• Complessità: O(V × E) dove V = nodi, E = archi
• Dopo V-1 iterazioni, le distanze sono garantite corrette
• L’iterazione finale serve a rilevare cicli negativi

Algoritmo di Dijkstra

Ottimale per grafi con pesi non negativi. Usa una coda di priorità per processare sempre il nodo con distanza minima.

Pseudocodice:

Procedure Dijkstra(grafo, sorgente)
    distanza[v] = infinito per ogni nodo v
    distanza[sorgente] = 0
    crea coda di priorità Q con (sorgente, 0)

    mentre Q non è vuota do
        (u, dist_u) = estrai nodo con distanza minima da Q
        per ogni vicino v di u con peso w do
            se distanza[u] + w < distanza[v] allora
                distanza[v] = distanza[u] + w
                inserisci o aggiorna (v, distanza[v]) in Q

    restituisci distanza
End Procedure

Implementazione Python:

import heapq

def dijkstra(grafo, sorgente):
    distanza = {nodo: float('inf') for nodo in grafo}
    distanza[sorgente] = 0
    coda = [(0, sorgente)]  # (distanza, nodo)

    while coda:
        dist_u, u = heapq.heappop(coda)
        if dist_u > distanza[u]:
            continue
        for v, peso in grafo[u]:
            nuova_dist = distanza[u] + peso
            if nuova_dist < distanza[v]:
                distanza[v] = nuova_dist
                heapq.heappush(coda, (nuova_dist, v))

    return distanza

distanze = dijkstra(graph, 'A')
for nodo, dist in distanze.items():
    print(f"A → {nodo}: {dist}")

Visualizzazione con NetworkX

pip install networkx matplotlib

import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()

edges = [
    ('A', 'B', 5), ('A', 'C', 1),
    ('B', 'C', 2), ('B', 'D', 1),
    ('C', 'D', 4), ('C', 'E', 8),
    ('D', 'E', 3), ('D', 'F', 6),
]

for u, v, w in edges:
    G.add_edge(u, v, weight=w)

pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True,
        node_color='lightblue', edge_color='gray', node_size=500)
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)

plt.title("Grafo pesato con NetworkX")
plt.show()

NetworkX include anche implementazioni pronte degli algoritmi:

# Dijkstra con NetworkX
percorso = nx.shortest_path(G, source='A', target='F', weight='weight')
distanza  = nx.shortest_path_length(G, source='A', target='F', weight='weight')
print(f"Percorso: {' → '.join(percorso)}, costo: {distanza}")

Connessione con il routing di rete

I grafi sono alla base dei protocolli di routing:

In OSPF, ogni router costruisce un grafo dell’intera rete (LSDB — Link State Database) e applica Dijkstra per calcolare i percorsi ottimali verso tutte le destinazioni.