Articolo originale: Graph Algorithms and Data Structures Explained with Java and C++ Examples
Cos'è un Algoritmo di Grafo?
Gli algoritmi di grafo sono un insieme di istruzioni per attraversare (visitare i nodi di) un grafo.
Alcuni algoritmi sono usati per trovare uno specifico nodo o il percorso tra due dati nodi.
Perché gli Algoritmi di Grafo Sono Importanti
I grafi sono strutture dati molto utili che possono essere usate per modellare diversi problemi. Questi algoritmi hanno applicazione diretta nei siti di Social Network, nella modellazione di Macchine a Stati e molto altro.
Alcuni Comuni Algoritmi di Grafo
Alcuni dei più comuni sono:
- Ricerca in Ampiezza - Breadth First Search (BFS)
- Ricerca in Profondità - Depth First Search (DFS)
- Algoritmo di Dijkstra
- Algoritmo di Floyd-Warshall
Algoritmo di Bellman Ford
L'algoritmo di Bellman Ford è l'algoritmo per trovare il percorso più breve per grafi che possono avere pesi negativi. Questo algoritmo è anche valido per rilevare cicli di pesi negativi visto che l'algoritmo converge verso una soluzione ottimale in O(V*E) passaggi. Se quanto risultato non è ottimale, allora il grafo contiene un ciclo di peso negativo.
Ecco un'implementazione in Python:
infinity = 1e10
def bellman_ford(graph, start, end):
num_vertices = graph.get_num_vertices()
edges = graph.get_edges()
distance = [infinity for vertex in range(num_vertices)]
previous = [None for vertex in range(num_vertices)]
distance[start] = 0
for i range(end+1):
for (u, v) in edges:
if distance[v] > distance[u] + graph.get_weight(u, v):
distance[v] = distance[u] + graph.get_weight(u, v)
previous[v] = u
for (u,v) in edges:
if distance[v] > distance[u] + graph.get_weight(u, v):
raise NegativeWeightCycleError()
return distance, previous
# 'distance' è la distanza dall'inizio verso quel nodo con il
# percorso più breve, utile per stampare la distanza più breve.
# 'previous' è un array che contiene il nodo che viene prima di
# quello corrente, utile per stampare il percorso.
Ricerca in Profondità - Deep Search First (DFS)
È uno dei più semplici algoritmi di grafo. Attraversa il grafo prima verificando il nodo corrente, poi spostandosi verso uno dei suoi successori e ripetendo il processo. Se il nodo corrente non ha successori da verificare, torna indietro al suo predecessore e il processo continua (spostandosi verso un altro successore). Se viene trovata la soluzione la ricerca si arresta.
Implementazione (C++14)
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
class Graph{
int v; // numero di vertici
// puntatore a un vettore che contiene una lista di adiacenze
vector < int > *adj;
public:
Graph(int v); // Costruttore
// funzione per aggiugere una connessione tra due nodi (edge)
void add_edge(int v, int w);
// stampa l'attraversamento dfs da una data sorgente `s`
void dfs();
void dfs_util(int s, vector < bool> &visited);
};
Graph::Graph(int v){
this -> v = v;
adj = new vector < int >[v];
}
void Graph::add_edge(int u, int v){
adj[u].push_back(v); // aggiunge v alla lista u
adj[v].push_back(v); // aggiunge u alla lista v (elimina questa istruzione se il grafo è diretto!)
}
void Graph::dfs(){
// vettore dei visitati - per tenere traccia dei visitati durante la ricerca DFS
vector < bool > visited(v, false); // marca tutti i nodi/vertici come non visitati
for(int i = 0; i < v; i++)
if(!visited[i])
dfs_util(i, visited);
}
// nota l'utilizzo di una chiamata per riferimento qui!
void Graph::dfs_util(int s, vector < bool > &visited){
// marca il nodo/vertice corrente come visitato
visited[s] = true;
// stampa allo standard output (schermo)
cout << s << " ";
// attraversa la suo lista di adiacenze e chiama ricorsivamente dfs_util per tutti i suoi vicini!
// (solo se il vicino non è ancora stato visitato!)
for(vector < int > :: iterator itr = adj[s].begin(); itr != adj[s].end(); itr++)
if(!visited[*itr])
dfs_util(*itr, visited);
}
int main()
{
// crea un grafo usando la classe Graph definita qui sopra
Graph g(4);
g.add_edge(0, 1);
g.add_edge(0, 2);
g.add_edge(1, 2);
g.add_edge(2, 0);
g.add_edge(2, 3);
g.add_edge(3, 3);
cout << "Il seguente è l'attraversamento Deep First del grafo fornito"
<< "(a partire dal vertice 0): ";
g.dfs();
// il risultato sarebbe: 0 1 2 3
return 0;
}
Valutazione
Complessità di spazio: O(n)
Complessità temporale per il caso peggiore O(n). Depth First Search è completo su una serie di nodi finita. Funziona meglio su alberi shallow (vale a dire alberi che hanno una piccola altezza o profondità, cioè un limitato numero di livelli o strati - n.d.t.).
Implementazione di DFS in C++
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct Graph{
int v;
bool **adj;
public:
Graph(int vcount);
void addEdge(int u,int v);
void deleteEdge(int u,int v);
vector<int> DFS(int s);
void DFSUtil(int s,vector<int> &dfs,vector<bool> &visited);
};
Graph::Graph(int vcount){
this->v = vcount;
this->adj=new bool*[vcount];
for(int i=0;i<vcount;i++)
this->adj[i]=new bool[vcount];
for(int i=0;i<vcount;i++)
for(int j=0;j<vcount;j++)
adj[i][j]=false;
}
void Graph::addEdge(int u,int w){
this->adj[u][w]=true;
this->adj[w][u]=true;
}
void Graph::deleteEdge(int u,int w){
this->adj[u][w]=false;
this->adj[w][u]=false;
}
void Graph::DFSUtil(int s, vector<int> &dfs, vector<bool> &visited){
visited[s]=true;
dfs.push_back(s);
for(int i=0;i<this->v;i++){
if(this->adj[s][i]==true && visited[i]==false)
DFSUtil(i,dfs,visited);
}
}
vector<int> Graph::DFS(int s){
vector<bool> visited(this->v);
vector<int> dfs;
DFSUtil(s,dfs,visited);
return dfs;
}
Algoritmo di Floyd Warshall
È un ottimo algoritmo per trovare la distanza più breve tra tutti i vertici in un grafo. È un algoritmo molto conciso e una complessità temporale di O(V^3) (dove V è il numero dei vertici). Può essere usato con pesi negativi, anche se i cicli di pesi negativi non devono essere presenti nei grafi.
Valutazione
Complessità di spazio: O(V^2)
Complessità temporale per il caso peggiore: O(V^3)
Implementazione Python
# Un grande valore come infinito
inf = 1e10
def floyd_warshall(weights):
V = len(weights)
distance_matrix = weights
for k in range(V):
next_distance_matrix = [list(row) for row in distance_matrix] # fa una copia della matrice di distanze
for i in range(V):
for j in range(V):
# Sceglie se il vertice k può andare bene come percorso con una distanza minore
next_distance_matrix[i][j] = min(distance_matrix[i][j], distance_matrix[i][k] + distance_matrix[k][j])
distance_matrix = next_distance_matrix # update
return distance_matrix
# Un grafo rappresentato come matrice delle adiacenze
graph = [
[0, inf, inf, -3],
[inf, 0, inf, 8],
[inf, 4, 0, -2],
[5, inf, 3, 0]
]
print(floyd_warshall(graph))
Ricerca in Ampiezza - Breadth First Search (BFS)
È uno degli algoritmi di grafo più semplici. Attraversa il grafo prima verificando il nodo corrente, quindi espandendosi aggiungendo i suoi successori al livello successivo. Questo processo viene ripetuto per tutti i nodi nel livello corrente prima di spostarsi a quello successivo. Se la soluzione viene trovata, la ricerca si arresta.
Visualizzazione
Valutazione
Complessità di spazio: O(n)
Complessità per il caso peggiore: O(n)
La Ricerca in Ampiezza è completa su un insieme finito di nodi e ottimale se il costo dello spostamento da un nodo all'altro è costante.
Codice C++ per l'implementazione di BFS
// Programma per stampre l'attraversamento BFS da un dato
// vertice sorgente. BFS(int s) attraversa i vertici
// raggiungibili da s
#include<iostream>
#include <list>
using namespace std;
// Questa classe rappresenta un grafo diretto usando una
// rappresentazione con lista di adiacenze
class Graph
{
int V; // No. of vertices
// Puntatore a un array che contiene una lista di adiacenze
list<int> *adj;
public:
Graph(int V); // Costruttore
// funczione per aggiungere una connessione tra due nodi (edge) al grafo
void addEdge(int v, int w);
// stampa l'attraversamento BFS da una data sorgente s
void BFS(int s);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::BFS(int s)
{
// marca tutti i vertici come non visitati
bool *visited = new bool[V];
for(int i = 0; i < V; i++)
visited[i] = false;
// Crea una coda per BFS
list<int> queue;
// Marca il nodo corrente come visitato e lo accoda
visited[s] = true;
queue.push_back(s);
// 'i' verrà usato per ottenere tutti i vertici
// adiacenti di un vertice
list<int>::iterator i;
while(!queue.empty())
{
// Fa uscire un vertice dalla code e lo stampa
s = queue.front();
cout << s << " ";
queue.pop_front();
// Ottiene tutti i vertici adiacenti di quello
// tolto dalla coda s. Se una adiacente non è stato
// visitato, viene marcato come visitato e accodato
for (i = adj[s].begin(); i != adj[s].end(); ++i)
{
if (!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
}
// Programma per testare i metodi della classe Graph
int main()
{
// Crea un grafo dato il diagramma seguente
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Il seguente è un attraversamento Breadth First Traversal "
<< "(a partire dal vertice 2) \n";
g.BFS(2);
return 0;
}
Algoritmo di Dijkstra
È un algoritmo presentato da E.W. Dijkstra. Cerca la sorgente del percorso più breve in un grafo con connessioni (edge) non negative (perché?).
Creiamo 2 array: visited e distance, che registrano rispettivamente se un vertice è visitato e qual è la distanza minima dal vertice sorgente. Inizialmente l'array visited viene assegnato con valori false e distance come infinito.
Partiamo dal vertice sorgente, che sarà u, e i suoi vertici adiacenti v. Ora per ogni v che è adiacente a u, la distanza è aggiornata se non è stato visitato prima e la distanza da u è minore della distanza corrente. Poi selezioniamo il vertice successivo con la distanza minore e che non sia stato ancora visitato.
Una coda di priorità è spesso usata per soddisfare quest'ultimo requisito nel minor tempo. Qui sotto un'implementazione della stessa idea usando PriorityQueue in Java.
import java.util.*;
public class Dijkstra {
class Graph {
LinkedList<Pair<Integer>> adj[];
int n; // Numero di vertici.
Graph(int n) {
this.n = n;
adj = new LinkedList[n];
for(int i = 0;i<n;i++) adj[i] = new LinkedList<>();
}
// aggiunge una connessione tra i vertici a e b con il costo come peso public void addEdgeDirected(int a, int b, int cost) {
adj[a].add(new Pair(b, cost));
}
public void addEdgeUndirected(int a, int b, int cost) {
addEdgeDirected(a, b, cost);
addEdgeDirected(b, a, cost);
}
}
class Pair<E> {
E first;
E second;
Pair(E f, E s) {
first = f;
second = s;
}
}
// Comparator per ordinare gli oggetti Pairs nella Priority Queue
class PairComparator implements Comparator<Pair<Integer>> {
public int compare(Pair<Integer> a, Pair<Integer> b) {
return a.second - b.second;
}
}
// Calola il percorso più corto dalla sorgente per ogni vertice e ritorna la distanza
public int[] dijkstra(Graph g, int src) {
int distance[] = new int[g.n]; // la distanza più breve di ciascun vertice da src
boolean visited[] = new boolean[g.n]; // il vertice è visitato o no
Arrays.fill(distance, Integer.MAX_VALUE);
Arrays.fill(visited, false);
PriorityQueue<Pair<Integer>> pq = new PriorityQueue<>(100, new PairComparator());
pq.add(new Pair<Integer>(src, 0));
distance[src] = 0;
while(!pq.isEmpty()) {
Pair<Integer> x = pq.remove(); // Estrae il vertice con la distanza più breve da src
int u = x.first;
visited[u] = true;
Iterator<Pair<Integer>> iter = g.adj[u].listIterator();
// Itera sui vicini di u e aggiorna le loro distanze
while(iter.hasNext()) {
Pair<Integer> y = iter.next();
int v = y.first;
int weight = y.second;
// Verifica se il vertice v non è visitato
// Se il nuovo percorso attraverso u offre un costo minore allora aggiorna l'array distance e aggiungi a pq
if(!visited[v] && distance[u]+weight<distance[v]) {
distance[v] = distance[u]+weight;
pq.add(new Pair(v, distance[v]));
}
}
}
return distance;
}
public static void main(String args[]) {
Dijkstra d = new Dijkstra();
Dijkstra.Graph g = d.new Graph(4);
g.addEdgeUndirected(0, 1, 2);
g.addEdgeUndirected(1, 2, 1);
g.addEdgeUndirected(0, 3, 6);
g.addEdgeUndirected(2, 3, 1);
g.addEdgeUndirected(1, 3, 3);
int dist[] = d.dijkstra(g, 0);
System.out.println(Arrays.toString(dist));
}
}
Algoritmo di Ford Fulkerson
Questo algoritmo risolve il problema del massimo flusso del grafo. Trova la migliore soluzione di flusso tramite le connessioni (edge) dei grafi in modo da ottenere il massimo flusso in uscita dall'altra parte. La sorgente ha una specifica velocità di input e ciascuna connessione ha un peso associato a essa che è la quantità massima che può passare attraverso quella connessione.
L'algoritmo di Ford Fulkerson è anche chiamato algoritmo di Edmund-Karp visto che le specifiche complete sono state fornite da Jack Edmonds e Richard Karp.
Funziona creando percorsi di aumento, ovvero percorsi dalla sorgente all'uscita che hanno un flusso non zero. Facciamo passare il flusso attraverso i percorsi e aggiorniamo i limiti. Ciò può portare a situazioni in cui non abbiamo più mosse disponibili. Ecco dove la capacità di "annullamento" di questo algoritmo gioca un ruolo importante. In caso di blocco, diminuiamo il flusso e apriamo la connessione per far passare la nostra sostanza corrente.
Passaggi
- Imposta il flusso a zero per tutte le connessioni.
- Fintanto che c'è un percorso dalla sorgente allo scarico:
- Cerca il peso minimo sul percorso, che associ a
limit. - Trova tutte le connessioni (
u,v) sul percorso e:
1. Aggiungilimital flusso dauav. (Per la mossa corrente)
2. Sottrailimitdal flusso davau(Per un annullamento della mossa in futuro)
Valutazione
Complessità temporale: O(V*E^2)
Implementazione Python
# Un numero grande per infinito
inf = 1e10
def maximum_flow(graph, source, sink):
max_flow = 0
parent = bfs(graph, source, sink)
while path:
limit = inf
v = sink
while v != source:
u = parent[s]
path_flow = min(limit, graph[u][v])
v = parent[v]
max_flow += path_flow
v = sink
while v != source:
u = parent[v]
graph[u][v] -= path_flow
graph[v][u] += path_flow
v = parent[v]
path = bfs(graph, source, sink)
return max_flow