Algoritmo di Tarjan per le componenti fortemente connesse
# Algoritmo di Tarjan per le componenti fortemente connesse

L'algoritmo di Tarjan, così chiamato per il nome del suo inventore Robert Tarjan, è un algoritmo usato nella teoria dei grafi per trovare le componenti fortemente connesse di un grafo. Un'applicazione tipica dell'algoritmo è la ricerca dei cicli. Ha la stessa efficienza dell'algoritmo di Gabow.

## Concetto di base

L'idea alla base dell'algoritmo è che una ricerca depth-first inizia sempre da un nodo di partenza. Le componenti fortemente connesse, insieme, formano i sotto-alberi dell'albero di ricerca le cui radici sono le componenti fortemente connesse.

I nodi sono dunque inseriti in uno stack, ossia una pila, nell'ordine in cui sono visitati. Quando la ricerca risale da un sotto-albero visitato, i nodi corrispondenti sono ripresi dalla pila e viene determinato se ognuno è la radice di una componente fortemente connessa. Se lo è un nodo, allora insieme a tutti quelli presi prima (cioè appartenenti al sotto-albero di cui è radice) formano una componente fortemente connessa.

## Determinare se un nodo è una radice

Il punto centrale dell'algoritmo consiste nel determinare se un nodo è la radice di una componente fortemente connessa. Per farlo, a ogni nodo v è assegnato un indice di profondità della ricerca, chiamato v.indice, che viene incrementato man mano che vengono trovati nuovi nodi. Inoltre, ogni nodo ha un altro valore assegnato chiamato v.minima_distanza (o lowlink) che indica che indice deve avere per essere raggiungibile dalla radice. Quindi, un nodo è la radice di una componente fortemente connessa se e solo se indice e minima_distanza sono uguali. Il valore minima_distanza è calcolato durante la ricerca depth-first in modo da poter essere sempre recuperabile.

## L'algoritmo in pseudocodice

L'algoritmo riceve in input il grafo G composto da un insieme di vertici V e di archi orientati (se non è un grafo orientato si può modellizzare ogni arco con due archi orientati nei due orientamenti).

## Implementazione in Java

Ecco un codice Java che implementa l'algoritmo utilizzando un grafo Neo4j.

La funzione commitTransazione, omessa per semplicità, chiude la transazione e la riapre, per salvare i valori di proprietà assegnati ed evitare anomalie dovute al fatto che nei successivi passaggi non sarebbero letti i valori appena assegnati. Si è supposto che ogni nodo abbia una proprietà name che lo identifica.

## Osservazioni

* Complessità: La procedura è chiamata una volta per ogni nodo. L'iterazione analizza ogni arco per due volte se non è orientato, altrimenti una. L'algoritmo dunque ha complessità computazionale lineare in base al numero di archi nel grafo, ossia $O(|V|+|E|)$
* Il test per determinare se v' è nella pila andrebbe fatto in tempo costante, per esempio controllando un valore memorizzato nel nodo stesso. Se non ci sono insiemi fortemente connessi molto grandi, comunque, si può iterare sulla pila senza peggiorare troppo la complessità dell'algoritmo.
