Una componente fortemente connessa di un grafo diretto G è un sottografo massimale di G in cui esiste un cammino orientato tra ogni coppia di nodi ad esso appartenenti.
Le componenti fortemente connesse formano una partizione di G poiché un nodo non può trovarsi contemporaneamente in due componenti fortemente connesse, di conseguenza un grafo diretto è fortemente connesso se e solo se ha una sola componente fortemente connessa.
Due vertici di G sono fortemente connessi se e solo se fanno parte dello stesso ciclo orientato.
Algoritmi per il calcolo delle componenti fortemente connesse
[modifica | modifica wikitesto]Definizione del problema
[modifica | modifica wikitesto]Dato un grafo orientato ciclico, si richiede di identificare le componenti fortemente connesse e un loro ordine topologico
Algoritmo di Tarjan
[modifica | modifica wikitesto]L'algoritmo di Tarjan per le componenti fortemente connesse è uno degli algoritmi più efficienti per effettuare la ricerca delle strutture fortemente connesse in un grafo. Opera infatti a complessità lineare al numero degli archi e dei vertici O(|V|+|E|).
Algoritmo di Kosaraju
[modifica | modifica wikitesto]L'algoritmo di Kosaraju-Sharir consiste nell'eseguire una visita in profondità del grafo e una successiva visita in profondità del grafo trasposto, in cui gli archi sono invertiti, scegliendo i nodi nell'ordine di fine visita ottenuto durante la prima visita in profondità. In tal modo si riesce a identificare le componenti fortemente connesse del grafo in tempo Θ(V+E). Risulta quindi più semplice da implementare ma meno efficiente dell'algoritmo di Tarjan e di quello di Gabow che effettuano una sola visita in profondità del grafo.
Algoritmo di Gabow
[modifica | modifica wikitesto]L'algoritmo di Cheriyan–Mehlhorn/Gabow consiste nell'eseguire una sola ricerca in profondità sul grafo, utilizzando uno stack per tenere traccia dei vertici che non sono ancora stati assegnati ad una componente. Come l'algoritmo di Tarjan viene effettuata una sola ricerca in profondità.
Bibliografia
[modifica | modifica wikitesto]- (EN) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Capitolo 22.5, pp.552-557.
- Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, Algoritmi e strutture dati, McGraw-Hill, 2004, ISBN 9788838661617. Capitolo 11.5, pp.289-293
