14 marzo 2024 - esercizio 5

[CuriousCI]

Fornire un algoritmo in pseudo-codice che dato un grafo diretto e aciclico $G = (V, E)$, restituisce un ordinamento topologico di $G$. È possibile implementarlo in modo che il tempo di esecuzione sia $\theta(|V|+|E|)$?

Come dovrebbe essere modificato tale algoritmo per restituire l’elenco di tutti gli ordinamenti topologici di $G$? È possibile fare questa ulteriore modifica mantenendo lo stesso tempo di esecuzione?

[CarloDaRomadev]

1)

def global_ord_top (G directed and acyclic graph) => list:
    output = []
    vis = [0] * n                //O(N) time complexity 
    for x in V(G):
        rec_aux(x, output)
    return output

def aux_rec (x: node, output: list) => none:
    vis[x] = 1
    for w in x.adjacent_out:
        if vis[w] == 0:
            aux_rec(w)
        output.insert(w,0)
    return

• aux_rec ha costo computazionale $O(deg(v))$, in global:ord_top questo viene ripetuto N volte quindi il ciclo for di global_ord_top ha costo computazionale $O(\sum_{v \in V(G)}deg(v))$ = $O(M)$. La costruzione della lista vis ha costo computazionale $O(N)$. Il costo computazionale totale dell'algoritmo è $O(N+M)$.

[LeoCosta02]

Ord_topologico(G){
L: list //output
Vis: int [n]= [0,0...0]
for each( v appartiene al grafo){
if(Vis[v]==0){
Dfs_ord(G,v,Vis,L)
}
}
}

Dfs_ord(G,v,Vis,L){
vis[v]=1
for each(w adiacente a v){
if(vis[w]==0)
Dfs_ord(G,w,Vis,L)

}

  L.add_Head(v)

}

[Frisbon]

Penso sia impossibile avere tutti gli ordinamenti topologici in O(n+m)

[CarloDaRomadev]

def OrdineTopologico(G, vis = [0...0])
	ordine = []
	for x in v(G){
		if vis[x] != 0{
			ordina(G, vis, x)
		}
	}
	return ordine

def ordina(G, vis, x, ordine)
	vis[x] = 1
	for w in v.adiacenti(){
		if vis[w] == 0{
			ordina(G, vis, w)
		}
	}
	ordine.insert(x)


//O(n+m)