Ordinamento topologico

Dato un grafo orientato aciclico (“dag”), è sempre possibile ordinare i suoi vertici in modo che, per ogni arco <u, v> del grafo, u preceda v nell’ordinamento.

Un ordinamento topologico di un dag è un ordinamento lineare dei suoi vertici che soddisfa la condizione precedente,cioè, per ogni arco <u, v> del grafo, u precede v nell’ordinamento.

A

DB

C

E

F

F C E D A B

È un ordinamento topologico

Infatti disegnando gli archi del grafo essi risultano tutti orientati nella stessa direzione (da sinistra verso destra):

Esempio:

F C E D A B

A

DB

C

E

FEsempio:

Ma non è l’unico, anche i seguenti sono ordinamenti topologici

C D A F E B

A B C F D E

Come è possibile usare una visita del grafo per scoprire un suo ordinamento topologico?

Visitiamo il grafo in profondità considerando i vertici in ordine alfabetico: A B C D E F

Otteniamo i seguenti tempi di inizio e fine visita

A

DB

C

E

F1/4

2/3

5/10 11/12

8/9

6/7

Riportiamo i tempi sui vertici nel primo ordinamentopreso in esame

F C E D A B

1/4 2/35/1011/12 8/9 6/7

Anche per gli altri due ordinamenti si possono trovare degli ordini, in cui considerare i vertici per effettuare una visita inprofondità, che permettono di “intuire” quale informazione ottenuta con la visita stessa è utile per scoprire un ordinamento topologico.

Per il secondo ordinamento, se visitiamo i vertici nell’ordine:E D F C A B, si ottiene:

A B C F D E

3/4 1/210/11 9/12 7/8 5/6

A

DB

C

E

F9/12

10/11

7/8 5/6

1/2

3/4

Ed infine, visitando i vertici nell’ordine B E F A C B,si ottiene, per il terzo ordinamento:

C D A F E B

3/4 1/210/11 9/12 7/8 5/6

A

DB

C

E

F7/8

1/2

9/12 5/6

3/4

10/11

Che cosa hanno in comune i tre ordinamenti, rispetto alle visite?

C D A F E B

3/4 1/210/11 9/12 7/8 5/6

A B C F D E

3/4 1/210/11 9/12 7/8 5/6

F C E D A B

1/4 2/35/1011/12 8/9 6/7

Che cosa hanno in comune i tre ordinamenti, rispetto alle visite?

C D A F E B

3/4 1/210/11 9/12 7/8 5/6

A B C F D E

3/4 1/210/11 9/12 7/8 5/6

F C E D A B

1/4 2/35/1011/12 8/9 6/7

I vertici sono sempre in ordine decrescente dei tempi di fine visita

Adattiamo la struttura standard dell’algoritmo di visita al problema dell’ordinamento topologico.

Basta creare una lista dei vertici in ordine decrescente dei tempi di fine visita.

Topological_Sort (G) INIZIALIZZA (G) for ogni u V do

if color u = white then DFS-topologica (G, u)

DFS-topologica (G, u) color u gray d[u] time time + 1 while c’è v ADJ u

non considerato do if color v = white then v u DFS-VISITA-ricorsiva (G, v) color u black f[u] time time + 1 Intesta (u, LISTA)

Complessità: O(V + E)

Dimostrando che una (qualunque) DFS del grafo associa aivertici tempi di fine visita tali che: f[v] < f[u] per ogni arco <u, v> del grafo, si dimostra la correttezza del programma.

{ G grafo orientato aciclico }

VISITA_TUTTI_I_VERTICI (G) INIZIALIZZA (G) for ogni u V do

if color u = white then DFS-topologica (G, u)

{ LISTA contiene i vertici di G in ordine topologico }