#GrafiMolti problemi algoritmici si possono formulare in termini di grafi. Chiamiamo grafi gli oggetti simili a quelli in figura.
2
1
3
5
0
1
2
3
0
1
2
3
4
5
6
7
0
1
2
3
4
5
Un grafo pesatoUn alberoUn grafo diretto
In generale possiamo modellare con un grafo un insieme di entità (dette nodi) tra le quali sussistono relazioni di qualche tipo (dette archi).
Sono esempi di grafi gli incroci di una città collegati dalle strade, gli esami necessari per laurearsi e le dipendenze del tipo “l’esame 𝑎 va dato prima dell’esame 𝑏”, l’insieme dei vostri amici e le relazioni di amicizia tra di loro e tanti altri oggetti.
Formalmente, un grafo 𝐺 è una coppia (𝑉,𝐸) dove 𝑉 è un insieme di nodi (o vertici) e 𝐸 è un (multi)insieme di archi, cioè coppie di nodi. Un arco può essere diretto, cioè una strada a senso unico, o non diretto, cioè una strada a doppio senso. Archi diretti e non diretti corrispondono a coppie ordinate e non ordinate. Denotiamo con 𝑁 il numero di nodi e con 𝑀 il numero di archi.
Due nodi 𝑢,𝑣 si dicono adiacenti se sono connessi da un arco.
A livello implementativo, un grafo può assumere tre forme:
•matrice di adiacenza•lista di archi•lista di adiacenzaQuest’ultima è la rappresentazione più pratica e comune, ma ognuna ha i propri vantaggi e svantaggi. Una lista di adiacenza da una lista di archi si costruisce come segue.
int main() {
int n; // numero di nodi
cin >> n;
int m; // numero di archi
cin >> m;
vector<vector<int>> adj(n);
for (int i = 0, a, b; i < m; i++) {
cin >> a >> b;
adj[a].push_back(b); // a -> b
adj[b].push_back(a); // b -> a
}
// la lista di adiacenza è pronta!
}
Sottolineiamo il fatto che non sempre è necessario memorizzare il grafo come oggetto esplicito: pensa al caso di una griglia 𝑅×𝐶 dove ogni cella è un nodo e ogni coppia di celle adiacenti è connessa da un arco. Non è necessario memorizzare esplicitamente gli archi, poiché dato un nodo puoi calcolare i suoi vicini in tempo costante.
Cosa ce ne facciamo di un grafo? Alcune delle domande che uno si potrebbe fare sono: posso andare dal nodo 𝐴 al nodo 𝐵? C’è solo un modo? Quanto è lungo il cammino più breve tra questi? Quanti sono i gruppi di nodi?
A queste e altre domande possiamo rispondere attraverso degli algoritmi che operano su uno o più grafi.
Abbiamo il nostro grafo in forma di lista di adiacenza: per ogni nodo 𝑣 il corrispondente vettore adj[𝑣] contiene i vicini di 𝑣. Ora ci piacerebbe visitarlo a partire da un nodo. Ci sono sostanzialmente due modi per farlo.
Prima di vedere quali, è importante introdurre alcuni termini che ci permetteranno di esprimere in modo più semplice alcuni concetti.
Un cammino fra due nodi 𝐴 e 𝐵 è una sequenza di nodi 𝑎1,𝑎2,…,𝑎𝑘 tale che 𝑎1=𝐴, 𝑎𝑘=𝐵 ed esiste un arco dal nodo 𝑎𝑖 al nodo 𝑎𝑖+1 per ogni 𝑖=1…𝑘−1. In altre parole seguo un cammino se mi muovo tra i nodi del grafo attraverso gli archi.
Due nodi sono connessi se esiste un cammino tra loro.
La lunghezza di un cammino in un grafo non pesato è il numero di archi che questo utilizza. Se il grafo è pesato, la lunghezza del cammino è la somma dei pesi degli archi percorsi.
La distanza fra due nodi è la lunghezza minima di un cammino tra questi.
#Visite in ampiezza e in profonditàLe due visite che seguono sono i mattoni con cui si costruiscono buona parte degli algoritmi sui grafi: la visita in ampiezza (Breadth-First Search) e in profondità (Depth-First Search).
La BFS visita il grafo a livelli: prima il nodo di partenza, seguito dai suoi vicini, poi i vicini dei vicini non già visitati, e così fino a visitare tutti i nodi raggiungibili. La BFS si implementa processando i nodi uno per volta: il nodo corrente si segna come visitato e i suoi vicini non già visitati si mettono in coda, in attesa di essere processati.
// leggi il grafo, ...
vector<bool> vis(adj.size()); // inizializzato a false
vis[root] = true;
queue<int> Q; // libreria <queue>
Q.push(root);
while (!Q.empty()) {
int u = Q.front();
Q.pop();
cout << "Processo il nodo " << u << "\n";
for (int v : adj[u]) {
if (vis[v])
continue;
vis[v] = true;
Q.push(v);
}
}
Nota come la BFS si può utilizzare per calcolare le distanze minime in un grafo non pesato: il livello di ogni nodo è la sua distanza dalla radice.
Prendiamo il seguente grafo e facciamo una visita in ampiezza assumendo root=0.
0
1
2
3
4
5
Passo 1 →𝑄=[0]
0
1
2
3
4
5
Passo 2 →𝑄=[0,1,5]
0
1
2
3
4
5
Passo 3 →𝑄=[0,1,5,2]
0
1
2
3
4
5
Passo 4 →𝑄=[0,1,5,2,4]
0
1
2
3
4
5
Passo 5 →𝑄=[0,1,5,2,4,3]
0
1
2
3
4
5
Passo 6 →𝑄=[0,1,5,2,4,3]
L’ordine di visita dei nodi è [0,1,5,2,4,3].
I nodi vengono visitati in ordine di distanza dal nodo di partenza, cioè il nodo 0. Dopo il nodo 0 vengono visitati i nodi 1 e 5 che sono a distanza 1, poi i nodi 2 e 4 a distanza 2 e infine il nodo 3 che si trova a distanza 3.
La DFS, invece, visita il grafo in maniera sostanzialmente ricorsiva. L’implementazione più naturale è quella che segue, ma se nel codice precedente sostituissi la parola stack a queue e la parola top a front otterresti lo stesso ordine di visita.
// la lista di adiacenza e vis devono essere dichiarati globalmente
void dfs(int u) {
vis[u] = true;
cout << "Processo il nodo " << u << "\n";
for (int v: adj[u])
if (!vis[v])
dfs(v);
};
Prendiamo il seguente grafo e facciamo una visita in profondità assumendo root=0.
0
1
2
3
4
5
Passo 1 →dfs(0)
0
1
2
3
4
5
Passo 2 →dfs(1)
0
1
2
3
4
5
Passo 3 →dfs(2)
0
1
2
3
4
5
Passo 4 →dfs(5)
0
1
2
3
4
5
Passo 5 →dfs(4)
0
1
2
3
4
5
Passo 6 →dfs(3)
In questo caso l’ordine di visita dei nodi è [0,1,2,5,4,3].
Sia nel caso della BFS che nel caso della DFS l’ordine di visita può variare in base all’ordine dei nodi nelle liste di adiacenza e all’implementazione della visita. Ti invitiamo a pensare in che senso una visita è in ampiezza e l’altra in profondità.
Per il momento diciamo che l’applicazione principale della BFS è trovare la distanza da un nodo verso tutti gli altri in un grafo non pesato. L’ordine di visita della DFS invece diventerà importante quando parleremo di alberi.
Prima di procedere, diciamo che un grafo è connesso se ogni coppia di nodi del grafo è connessa. Non tutti i grafi sono connessi, ma ogni grafo si partiziona naturalmente in componenti connesse, cioè sottografi connessi, ma sconnessi l’uno dall’altro.
0
1
2
3
4
5
6
7
Figure 4: Le componenti connesse sono evidenziate con colori diversi.
Ora che sappiamo visitare il grafo, possiamo anche contare il numero di isole su una mappa, come nel problema Find the Treasure (ois_islands).
Un’altra applicazione delle visite è dire se un grafo contiene o meno dei cicli, cioè dei cammini che partono e arrivano allo stesso nodo senza passare due volte per lo stesso arco, o ancora l’ordinamento topologico di un grafo diretto aciclico, che tratteremo più avanti.
#BFS multi-sorgenteUna variante piuttosto utile della visita in ampiezza è quella con più sorgenti. La visita si espande non da una sorgente sola ma da molte di queste. Virtualmente, ciò è equivalente a creare un nodo fittizio 𝑠 connesso ai nodi che vogliamo rendere sorgenti della BFS, per poi fare una BFS da 𝑠. Questa osservazione è sufficiente per dire che la BFS multi-sorgente ha la stessa complessità della BFS normale.
Questo algoritmo ci permette, ad esempio, di vedere come si propaga un incendio appiccato in più nodi di un grafo contemporaneamente, oppure, dati alcuni nodi speciali, di trovare per ogni nodo del grafo il nodo speciale più vicino.
3234443212
21233321S1
1S12233212
2122123323
3221S12334
4332123445
Figure 5: Una tipica applicazione della BFS multi-sorgente: trovare la minima distanza da uno dei nodi speciali.
L’implementazione è la stessa di una BFS normale ma all’inizio di inseriscono in coda tutte le sorgenti. Se si cerca la distanza occorre assegnare 0 alla distanza di ciascuna delle sorgenti.
for (int v: sorgenti) {
Q.push(v);
visitato[v] = true;
}
// BFS normale
Alcuni esercizi a riguardo:
Voci di Corridoio (https://territoriali.olinfo.it/task/gossip)
Caccia agli Interruttori (https://territoriali.olinfo.it/task/interruttori)
Monsters (https://cses.fi/problemset/task/1194)
Espansione del danno (https://territoriali.olinfo.it/task/espanditutto)
#Cammini minimi: L’algoritmo di DijkstraConsideriamo ora grafi pesati, cioè dove ogni arco ha un peso (o costo) associato.
In questo caso, nella lista di adiacenza memorizziamo anche il peso di ogni arco come segue.
vector<vector<pair<int, int>>> adj(n); // {nodo di arrivo, peso dell'arco}
for (int i = 0, a, b, w; i < m; i++) {
cin >> a >> b >> w; // arco a->b di peso w
adj[a].push_back({b, w});
}
Che te ne fai di un grafo pesato? Pensa a Google Maps che calcola il percorso migliore per andare da casa tua al panificio: in questo caso il peso di un arco è il tempo necessario per percorrerlo e tu vuoi arrivare al panificio nel minor tempo possibile.
Il problema, più in astratto, è: dato un grafo pesato, un nodo sorgente 𝑠 e un nodo obiettivo 𝑡, determina la lunghezza del minimo cammino da 𝑠 a 𝑡.
In un grafo non pesato, ogni arco ha lo stesso costo (ad esempio 1) e il problema si risolve facilmente con una BFS. In generale la questione si complica. Viene in soccorso l’algoritmo di Dijkstra (pronunciato “Daikstra”), che funziona in modo simile alla BFS, ma invece di usare una coda usa una coda di priorità per processare prima i nodi più vicini alla radice. In questo modo, quando si processa un nodo, si è sicuri di aver trovato il cammino più corto per raggiungerlo.
Ricordiamo che la coda di priorità, per noi priority_queue, supporta le seguenti operazioni:
•push(x): inserisce l’elemento 𝑥 nella coda, complessità 𝒪︀(log𝑛) con 𝑛 numero di elementi nella coda;•top(): restituisce l’elemento massimo, complessità 𝒪︀(1);•pop(): rimuove l’elemento massimo, complessità 𝒪︀(log𝑛).Normalmente le code a priorità hanno in cima l’elemento massimo, ma noi siamo interessati a quello con chiave (la distanza) minima.
Per ovviare a questo problema possiamo inserire le distanze cambiate di segno (sconsigliato, è facile dimenticarsi dei segni meno in giro) o specificare, quando dichiariamo la coda, come ordinarla.
Segue un’implementazione dell’algoritmo di Dijkstra.
// #include <le solite librerie>
#include <array>
#include <queue>
int main() {
// leggi il grafo
constexpr ll INF = 1e15;
int sorgente = 0;
vector<ll> dist(n, INF);
priority_queue<pair<ll, int>,
vector<pair<ll, int>>,
greater<>> Q; // {dist[u], u}
dist[sorgente] = 0;
Q.push({0, sorgente});
while (!Q.empty()) {
auto [d, u] = Q.top();
Q.pop();
if (d > dist[u])
continue;
for (auto [v, w]: adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
Q.push({dist[v], v});
}
}
}
for (int i = 0; i < n; i++)
cout << "La distanza minima da " << sorgente << " a " << i << " e' " << dist[i] << "\n";
}
Nel grafo sotto raffigurato, utilizzando il nodo 0 come sorgente, l’array dist conterrà i seguenti valori al termine dell’esecuzione: [0,6,2,5,9,7,9].
7
2
3
1
5
3
8
2
2
0
1
2
3
4
5
6
Per come è strutturato l’algoritmo, i nodi verranno estratti dalla coda in ordine di distanza dalla sorgente, in questo caso nell’ordine [0,2,3,1,5,4,6]. Poiché l’algoritmo esegue al più un inserimento per arco del grafo, la nostra implementazione ha complessità 𝒪︀(𝑀log𝑁).
##Minimo albero ricoprenteImmagina di dover progettare la rete elettrica dell’attuale Repubblica Ceca in modo tale che ogni luogo di interesse sia collegato, anche non direttamente, a ogni altro luogo di interesse, minimizzando la lunghezza totale dei collegamenti. Puoi convincerti facilmente che questo problema si formula naturalmente come segue in termini di grafi.
Dato un grafo 𝐺(𝑉,𝐸) connesso e pesato, un albero ricoprente è un sottografo connesso che contiene tutti i nodi di 𝐺 e non contiene cicli.
Questo problema si affronta sostanzialmente in tre modi: l’algoritmo di Prim, l’algoritmo di Kruskal e l’algoritmo di Borůvka. Trattiamo i primi due.
##Algoritmo di PrimL’algoritmo funziona nel seguente modo. Inizialmente si aggiunge un nodo arbitrario all’albero, dopodiché, per 𝑁−1 volte, si aggiunge un arco di peso minimo che connetta un nuovo nodo all’albero. Il sottografo risultante è un albero ricoprente di peso minimo.
Anche se inizialmente non si direbbe, l’implementazione è molto simile a quella di Dijkstra. Il cuore del programma cambia come segue.
vector<ll> cost(n, INF);
priority_queue<pair<ll, int>,
vector<pair<ll, int>>,
greater<>> Q; // {cost[u], u}
cost[0] = 0;
Q.push({0, 0});
ll peso_totale = 0;
while (!Q.empty()) {
auto [d, u] = Q.top();
Q.pop();
if (d > cost[u])
continue;
peso_totale += d;
for (auto [v, w]: adj[u]) {
if (w < cost[v]) {
cost[v] = w;
Q.push({cost[v], v});
}
}
}
cout << "L'MST ha peso totale " << peso_totale << "\n";
Come ti puoi aspettare, questa implementazione dell’algoritmo di Prim ha la stessa complessità del precedente algoritmo di Dijkstra, cioè 𝒪︀(𝑀log𝑁).
Consideriamo il seguente grafo:
7
2
3
1
5
8
4
2
2
0
1
2
3
4
5
6
Procediamo passo dopo passo seguendo l’algoritmo di Prim. Ogni volta prenderemo l’arco di peso minimo che connette un nodo preso (in rosso) e uno non preso. Cominceremo scegliendo arbitrariamente il nodo 0 come nodo preso.
2
0
1
2
3
4
5
6
Passo 1: l’arco più piccolo uscente da 0 è quello verso 2.
2
3
0
1
2
3
4
5
6
Passo 2: ora l’albero è composto da 0 e 2, l’arco minimo uscente è 2→3 con peso 3.
2
3
1
0
1
2
3
4
5
6
Passo 3: l’arco uscente minimo è 3→1 con peso 1.
2
3
1
4
0
1
2
3
4
5
6
Passo 4: l’arco uscente minimo è 3→6 con peso 4.
2
3
1
4
2
0
1
2
3
4
5
6
Passo 5: l’arco uscente minimo è 6→4 con peso 2.
2
3
1
4
2
2
0
1
2
3
4
5
6
Passo 6: l’arco uscente minimo è 6→5 con peso 2.
Abbiamo ottenuto l’albero che desideravamo. Di questo ora sappiamo dire il costo totale (14 in questo caso) e da quali archi è composto.
#Problemi consigliati
Message Route (https://cses.fi/problemset/task/1667)
Building Roads (https://cses.fi/problemset/task/1666)
Cammino minimo (https://training.olinfo.it/task/mincammino)
Counting Roads (https://cses.fi/problemset/task/1192)
Monsters (https://cses.fi/problemset/task/1194)
Episodio II: un lungo viaggio (https://training.olinfo.it/task/oii_bus)
Arte nei corridoi (https://training.olinfo.it/task/oii_corridoi)