Ordinamento topologico
# Ordinamento topologico

In teoria dei grafi un ordinamento topologico (in inglese topological sort) è un ordinamento lineare di tutti i vertici di un grafo diretto. I nodi di un grafo si definiscono ordinati topologicamente se i nodi sono disposti in modo tale che ogni nodo viene prima di tutti i nodi collegati ai suoi archi uscenti. L'ordinamento topologico non è un ordinamento totale, poiché la soluzione può non essere unica. Nel caso peggiore infatti si possono avere $n!$ ordinamenti topologici diversi che corrispondono a tutte le possibili permutazioni degli $n$ nodi. È possibile ordinare topologicamente un grafo se e solo se non contiene cicli (cioè solo se è un grafo aciclico diretto), e sono noti algoritmi per determinare un ordinamento topologico in tempo lineare.

## Esempi

L'applicazione canonica dell'ordinamento topologico risiede nel problema di pianificare l'esecuzione di una sequenza di attività in base alle loro dipendenze. Le attività sono rappresentate dai nodi di un grafo: vi è un arco tra $x$ e $y$ se l'attività $x$ deve essere completata prima che possa iniziare l'esecuzione dell'attività $y$. Un ordinamento topologico del grafo così ottenuto fornisce un ordine in cui eseguire le attività.

* Alcuni ordinamenti topologici validi per il grafo mostrato a sinistra sono:
* 7, 5, 3, 11, 8, 2, 9, 10 (graficamente da sinistra a destra e dall'alto al basso)
* 3, 5, 7, 8, 11, 2, 9, 10 (prima i nodi con i valori minori della loro numerazione)
* 3, 7, 8, 5, 11, 10, 2, 9
* 5, 7, 3, 8, 11, 10, 9, 2
* 7, 5, 11, 3, 10, 8, 9, 2 (prima i nodi con i valori maggiori della loro numerazione)
* 7, 5, 11, 2, 3, 8, 9, 10

## Algoritmi

Uno degli algoritmi classici per ordinare topologicamente un grafo è basato sul concetto di visita in profondità (ricerca depth-first). L'algoritmo di ordinamento topologico effettua una visita in profondità del grafo (a partire da ognuno dei nodi senza archi entranti) e, terminata la visita di ogni vertice, lo inserisce in testa ad una lista concatenata L. Al termine dell'esecuzione, questa lista conterrà i nodi ordinati. In pseudocodice:

dove la procedura visit è definita come

Si noti che l'algoritmo di cui è fornito lo pseudocodice non è in grado di determinare il caso (di errore) in cui nel grafo sono presenti cicli, ma può farlo con semplici modifiche.

L'algoritmo harvtxt, descritto da Kahn (1962), sceglie i vertici rispettando l'ordinamento topologico. Inizialmente, costruisce un insieme di vertici che non hanno archi entranti (grado entrante=0); dato che il grafo è aciclico esiste almeno uno di questi nodi. Poi:

Se il grafo è un DAG, la soluzione è contenuta nella lista L (non necessariamente unica). Altrimenti, il grafo ha almeno un ciclo ed è impossibile ottenere un ordinamento topologico.

L'insieme S può essere un set, una coda o una pila dato che non importa in quale ordine vengono estratti i vertici. Differenti soluzioni sono dovute all'ordine in cui i nodi vengono estratti da S.

### Complessità

Per un grafo G(V,E) dove V è l'insieme dei nodi e E l'insieme degli archi, entrambi gli algoritmi presentano una complessità lineare O(|V|+|E|), mentre l'inserimento di ciascuno dei |V| vertici in testa alla lista concatenata richiede tempo costante. Complessivamente, quindi, gli algoritmi impiegano tempo O(|V|+|E|).

