Classificazione archi

Gli archi che non fanno parte di un albero di copertura non è detto che indichino un ciclo.

Back edge Arco che porta ad un nodo già visitato, e non appartiene quindi all’albero di copertura. Rivela cicli. La visita dell’antenato v (1 nell’immagine), termina successivamente alla visita del nodo u (3 nell’immagine).

Forward edge Arco che porta ad un discendente, in un modo più veloce. La visita dell’antenato v (1) è già iniziata quando inizia la visita del discendente u (3). La visita del discendente, però, è già terminata quando si esplora (v, u).

Cross edge Porta ad un nodo che non è nè antenato nè discendente. È il nodo di un altro ramo. La visita di v (2) è già stata effettuata quando la si inizia da u (4).

Classificazione in DFS

Per classificare ogni arco servono tre oggetti di supporto:

• time: contatore per tenere traccia del numero di step
• pre: array per salvare il time di inizio visita del nodo
• post: array per salvare il time di fine visita del nodo

pre[v]<post[v]<pre[u]

DFS(G):
	for all v ∈ V do
		prev[v] := 0
		post[v] := 0
	time := 0
	for all v ∈ V do
		if pre[v] == 0 then
			DFS_visit(G, v)

DFS_visit(G, v):
	time := time + 1
	pre[v] := time
	for all (v, u) ∈ E do
		if pre[u] == 0 then
			// arco tree
			DFS_visit(G, u)
		else
			if pre[u] < pre[v] and post[v] == 0 then
				// arco BACK
			else if pre[u] > pre[v] and post[u] > 0 then
				// arco FORWARD
			else
				// arco CROSS
	time := time + 1
	post[v] := time

Costo computazionale $O(|V|+|E|)$

asd_27