esercizi asd

-grafo
	25-06-2012
	11-09-2015
	22-09-2011
	20-02-2015
	24-06-2013
	14-02-2013
	17-07-2015
-albero
	01-31-2013
	11-09-2015
	14-02-2013
	14-06-2013


prova asd 2011-09
Albero
Algo2(t,x,p,k1,k2)
int u=0,v=0;
	if(t)
		if(t.k >= k1 and t.k <= t.k)
			u=Algo(t.sx,x,t,k1,k2)
			v=Algo(t.dx,x,t,k1,k2)

			if( (u+v)>=x and (t.k%2==0) )
				if(p)
					if(p.sx==t)
						p.sx=cancella(t)
					else p.dx=cancella(t)
				else return -1;
			return u+v+1

	return u+v;
endAlgo2
Algo1(x,k1,k2,t)
	if(Algo2(t,null,x,k1,k2)==-1)//cancella la radice dell'albero
		t=cancella(t)
endAlgo1

Grafo
DSF(G:grafo)
bool prosegui=false
	for each vertice u E V
		do colore[u]= Bianco

	pred[u]= NIL

	for each vertice u E V and !prosegui
		if colore[u]= Bianco
			prosegui=DFS-Visita(G,u,pred);
			if(prosegui)
				stampaPercorso(G,s,v,pred)

endDsf
DSF-Visita(G:grafo,u:vertice,pred[]:vertice) : bool
	bool cicloTrovato=false;
	colore[u]=Grigio

	for each vertice v E Adiac[u] and !cicloTrovato
		if colore[v]= Bianco
			pred[v]= u
			cicloTrovato=DFS-Visit(G,v,pred)
		else if(colore[v]=grigio)
			return true;

	colore[u]=Nero

return cicloTrovato
endDfsVisit

stampaPercorso(G:grafo,s:vertice,v:vertice,pred[]:vertice
	if(v==s)
		print s
	else
		stampaPercorso(G,s,pred[v],pred)
		print v

grafo 26-06-2014

Grafo
DSF(G:grafo,v:vertice)
//Crea e alloca Grafo G'
	for each vertice u E V
		do colore[u]= Bianco

	G'.V'=G.V
	DFS-Visita(G,v,G');

endDsf
DSF-Visita(G:grafo,u:vertice,G':Grafo)

	colore[u]=Grigio

	for each vertice v E Adiac[u]

		if (colore[v]= Bianco or colore[v] = Nero)
			G'.Adj[u]=Insert(u,v);

				if(colore[v]= Bianco)
					DFS-Visit(G,v,G')

	colore[u]=Nero

endDfsVisit

grafo 11-09-2015
DFS(G,r)
boolean continua = true
int n = r.size,i;
	i=n-1
	foreach v in V
		c[v]=nero
	foreach v in r
		c[v]=bianco

	while(i>=0 and continua==true){
		if(c[r[i]]==bianco)
			dfs_visit(G,r[i])
		else
			 continua = false
		i=i-1;
	}

	if(continua==true)
		print("r è ordinamento topologico)
	else print("r non è ordinamento topologico)
end DFS

dfs_visit(G,v)
	c[v]=grigio
	foreach u in Adj(v)
		if(c[u]==bianco)
			dfs_visit(G,u)

	c[v]=nero
endDfs

albero 25-06-2012
algo(t,x,k1,k2,p)
int sx=0,dx=0,h=0
	if(t)
		if(t.k<=k1)
			sx=algo(t.sx,x,k1,k2,t)
			dx=algo(t.dx,x,k1,k2,t)
		else if(t.k<=k2)
			sx=algo(t.sx,x,k1,k2,t)
			dx=algo(t.dx,x,k1,k2,t)

			h=sx+sx+1

			if(h<=x)
				if(p)
					if(p.sx=t)
						p.sx=cancella(t)
					else p.dx=cancella(t)
	return h

albero 2013 01 31
algo(t,k1,k2,a[],x)
i=0;
	if(t)
		if(t.k>=k1)
			i=algo(t.sx,k1,k2,a[],x)

		if(t.k>=k1 and t.k<=k2)
			a[i]=t.k
			i=i+1
		x=i;
		i=algo(t.dx,k1,k2,a[],i)


return x;

grafo 20-02-2015

SUCCO : Trasponi grafo,color i vertici di X neri cosi da non andarci a finire sopra.
	Fai BFS per ogni vertice di X, quando incontri vertice bianco se la sua
	distanza dalla sorgente è < k allora signfica che esiste un percorso tale
	che non rispetti la proprietà di essere lungo > k, quindi inserisce in lista
	solamente quei vertici che quando vengono scoperti(bianchi) hanno dist[k]>k

Algo(G,X,k)
//Crea lista array L
	GT=TrasponiGrafo(G)
	foreach x in V
		c[v]=b
	foreach x in X
		c[x]=n

	foreach x in X
		L=BFS(G,x,k,L)
end Algo

BFS(G,s,k,L) : List
//crea array distanze dist[]
	dist[s]=0
	Q=ins(s)
	while(Q){
		u=estrai(Q)
		foreach i in V
			if(c[i]=b)
				c[i]=g;
				dist[i]=dist[u]+1;
				if(dist[i]>k)
					L=ins(i)
	}
return L;
endBFS

albero 11-09-2012

main(h1,h2,n1,n2)
int n = algo(t,null,h1,h2,n1,n2,k,0)

	if((n1<=n<=n2) and (h1<=0<h2) and (t.k%2==0))
		t=cancella(t)
end main

Algo(t,p,h1,h2,n1,n2,k,depth)
int sx=0,dx=0,d=0;
	if(t)
		if(t.k>=k)
			sx=Algo(t.sx,t,h1,h2,k,x+1)
		else
			sx=Algo(t.sx,t,h1,h2,k,x+1)
			dx=Algo(t.dx,t,h1,h2,k,x+1)

			d=sx+dx
			if((h1<= x <=h2) and (n1<= d <= n2) and (t.k%2==0))
				if(p)
					if(p.sx=t)
						p.sx=cancella(t)
					else p.dx=cancella(t)

			d=d+1

return d
end algo

25-06-2012

IDEA :  Marcare di colore rosso i vertici di A che NON vengono raggiunti da nessun
	vrtice di B tramite un percorso lungo più di K. Al termine dell'algoritmo
	se c'è almeno un vertice di A ancora rosso allora la distanza di A da B non è k
	Nello specifico ,sia k la distanza data in input:
	Trasponi il grafo, colora A di verde all'iniziio,B di nero e il resto bianco.
	Lancia una bfs su ogni vertice di B. Durante una qualsiasi visita da un vertice

x di B appena
	trovo un vertice di A la prima volta (sarà verde) succede che:
		1)lo coloro di rosso se dista da x meno di k e lo inserisco in coda

Q.Questo
		vertice verrà confrontato con gli altri di B al fine di verificare se

almeno
		uno dei B lo raggiunge in un percorso >k.
					altrimenti
		2)se dista >k  da x ho verificato la proprietà (esiste un b per a tale

che D(a,b)>k)
		quindi lo coloro di grigio e tale vertice prosegue normale la sua vita

fino a diventare nero.

	Mentre data un'altra qualsiasi iterazione con un altro vertice x' di B,se

incontro un vertice di A
	già visitato in passato (quindi rosso) si ha che Grazie al punto 1) il vertice

da verde è passato a rosso ed è stato inserito in coda,
	dunque i suoi adiacenti sono stati già controllati (grazie a questo giochetto

dei 2 colori evito reiserimenti inutili) e quindi
	può succedere che :
		3)se stavolta la distanza dai lui ad  x' è >k, esso viene colorato

direttamente di nero e finisce la sua vita.
						altrimenti
		4)resta rosso, in attesa di un successivo controllo sulla distanza tra

lui ed un altro vertice di B

	Per qualsiasi altro vertice di A invece, esso viene trattato

normalmente,colorato di grigio e inserito in coda per
	esplorare i suoi vertici.
	Al termine viene fatto uno scorrimento della lista di A, se c'è ancora un rosso

allora nessun B lo raggiungeva tramite percorso
	>k e quindi FALSO.

Algo(G,A,B,k)
//crea array colori c[]
boolean continua = true
	GT=TrasponiGrafo(G);

	foreach x in V
		c[v]=bianco
	foreach x in A
		c[v]=verde
	foreach x in B
		c[v]=nero

	foreach x in B
		bfs(G,x)

	foreach x in A and continua
		if(c[x]=rosso)
			print"A non dista "k" da B
			continua=false;

end algo
bfs(G,x,k)
	dist[x]=0;
	Q=ins(x)
	while(Q){
		u=testa(Q)
		foreach i in Adj(x)
				dist[i]=dist[u]+1
				if(c[i]=bianco)
					c[i]=grigio
					Q=ins(i)
				else if(c[i]=verde or rosso)
					if(c[i]=verde and dist[i]>k)
						c[i]=grigio
						Q=ins(i)
					else if(c[i]=verde and dist[i]<k )
						c[i]=rosso
						Q=ins(i)
					else if(c[i]=rosso and dist[i]>k)
						c[i]=nero

		if(c[u]!=rosso)
			Decoda(Q)
			c[u]=nero

	}//endwhile
end bfs

22-09-2011

IDEA : Utilizzare una BFS per scoprire se ci sono cicli. In caso di ciclo viene

utilizzato
	l'array dei predecessori per ricostruire il percorso contenente il ciclo.
	Nel dettaglio, viene lanciata una BFS su ogni vertice bianco di V.
	Durante la visita a partire da una sorgente s può succedere che:
		1)viene incontrato un vertice bianco, si prosegue come di norma nella

bfs
				oppure
		2)viene incontrato un vertice nero :
			2)in questo caso siamo in un ciclo solamente se la distanza

dalla radice s(ricalcolata
				per ogni nuova radice) del vertice corrente u (di cui

stiamo analizzando gli adiacenti)
				e dell'adiacente di u appena estratto (vertice i) è

dist[u]>dist[i]
				(ovvero poichè u dista da s di più di i, signfica che i

è stato scoperto lungo
				qusto percorso e dunque è un ciclo).
				Infatti nel caso in cui c[i]= nero e dist[u]<dist[i]

signfica che siamo in una nuova
				bfs da una nuova radice e abbiamo ricalcolato la

distanza di i dalla sorgente s per cui
				non è un ciclo (arco in avanti)

Algo(G)
//crea array colori color[] e pred[] e distanze[]
boolean cicloTrovato = false
	foreach x in V
		c[x]=bianco
		pred[x]=null
		dist[x]=infinito

	foreach x in V and (!cicloTrovato)
		if(c[x]=bianco)
			cicloTrovato=bfs(G,x,color,pred,dist)

	if(!cicloTrovato)
		"Il grafo è aciclico"

end algo

bfs(G,s,color,pred):cicloTrovato
boolean cicloTrovato = false
	pred[s]=null
	dist[s]=0
	c[s]=grigio
	Q=ins(s)
	while(Q){
		u=testa(Q)
		foreach i in Adj(u) and !cicloTrovato
				dist[i]=dist[u]+1
				if(c[i]=bianco)
					c[i]=grigio
					pred[i]=u
					Q=ins(Q,i)
				else if( (c[i] = nero) and (dist[u]>dist[i]))
						cicloTrovato=true;
						print"Il grafo contiene un ciclo nel

percorso"
						print(G,s,u,pred[])


	    Decoda(Q)
	    c[u]=nero
	}//endwhile
return cicloTrovato;
end bfs

print(G,s,u,pred[])
	temp=u
	while(temp!=null){//stampa il percorso al contrario :/
		print temp
		temp=pred[temp;
	}
end print

albero 11-09-2015
Algo(t,k,p') :int
nodobst p=p',pcand=p',cand=null,temp=t
int ris=0
	while(temp and temp.k!=k)
		if(temp.k<k)
			p=temp
			temp=temp.dx
		else
			if(temp.k%2==0)
				pcand=p
				cand=temp
			p=temp
			temp=temp.sx

	if(cand and temp.dx)
		p=temp
		temp=temp.dx
		while(temp)
			if(temp.k%2==0)
				pcand=p
				cand=temp
		   p=temp
	           temp=temp.sx

	if(pcand and cand)
		if(cand=pcand.sx)
			pcand.sx=cancella(cand)
		else pcand.dx=cancella(cand)
	else ris=1

return ris
endAlgo
main(t,k)
	n=algo(t,k,null)
	if(n=1)//successore testa albero
		t=cancella(t)

grafo 24-06-2013

dfs(G,a,b)
boolean trovato = false;
boolean continua = true;
	foreach v di V
		c[v]=b

	foreach v di V and !trovato and continua
		if(c[v]=b)
			trovato=dfs_visit(G,v,a,b)
			if((c[a]=nero and c[b]=bianco))
				continua=false

	if(trovato=true)
		print "L'arco a b sta in un ciclo"
	else print "No"

return continua;
end dfs;

dfs_visit(G,s,a,b){
boolean trovato = false;
	c[s]=g
	foreach x in Adj(s) and !trovato
		if(c[x]=b)
			c[x]=g
			trovato=dfs_visit(G,x,a,b)
		else if(c[x]=g)
			if((c[a]=g and c[b]=g))//Se nel ciclo sono grigi oppure uno dei

due
				trovato=true;
	c[s]=n
return trovato;
}
end dfs_visit

grafo 14-02-2013
Algo(G,A,B)
//Crea sottografo G2

	foreach v in V
		c[v]=b

	foreach v in B
		if(c[v]=b)
			dfs_visit(G,v)//classica dfs_visit DFS


	GT=TrasponiGrafo(G)

	foreach v in A
		if(c[v]=b)
			dfs_visit_mod(GT,G2,v)//dfs_visit modificata
return GT
end Algo;

dfs_visit_mod(G,G2,s)
	c[s]=g
	G2.VertList=ins(G2,s)
	foreach v in Adj(s)
		if(c[v]=b)
			G2.Adj(v)=ins(s)
			df_visit_mod(G,G2,v)

	c[s]n
end dfs_visit_mod

TrasponiGrafo(G)
	//Crea grafo GT e copia array di G in GT

	foreach v in V
		foreach u in Adj(v)
			G2.Adj(u) = insert (u,v)
return GT;
end

albero 14-02-2013
Algo(t,a)
int numNodi=0

	numNodi=creaArray(t,a,0)
	t'=bilancia(t',A,0,n)

endAlgo

bilancia(a,t,t',inf,sup)

	if(sup>inf)
		mid=(inf+sup)/2
		t'=creaNodo(a[mid])
		t'.sx=bilancia(t'.sx,inf,mid)
		t'.dx=bilancia(t'.dx,mid+1,sup)
return t'
and bilancia

creaArray(a,t,i)

	if(t)
		indice=creaArray(t.sx,a,i)
		a[indice]=t.k
		return creaArray(t.dx,a,indice+1)

return i;

albero 14-06-2013
algo(t,pos,prof,l1,l2,p)
int curind=0,curind2=0;
	if(t)
		curind=algo(t.sx,pos,prof+1,l1,l2,t)

		curind2=algo(t.dx,pos,curind+1,l1,l2,t)

		if(curind%3==0)
			if(p)
				if(p.sx==t)
					p.sx=cancella(t)
				else p.dx=cancella(t)

		pos=curind2;

return pos;

grafo 17-07-2015
IDEA: Mi sono basato dinuovo sull'idea di cercare un percorso massimale di soli vertici
dispari,quando lo trovo ritorno false a catena e termina l'algoritmo. Durante la visita
quando trovo un vertice pari lo coloro di nero e non scendo a visitare nulla al di

sotto
di lui, poichè i percorsi massimali che potrò trovare rispetteranno la proprietà di

avere
almeno un vertice pari. Quando invece sono in presenza di un ciclo oppure di un vertice

pozzo
ritorno direttamente false, in quanto lui e quelli prima di lui erano tutti dispari.

dfs(G,u,VAL)
	foreach k in V
		c[k]=b

	if(VAL[u]%2==0 OR dfs_visit(G,u,VAL)==true)
		print"Tutti i percorsi massimali contengono un vertice pari"
	else print"Esiste almeno un percorso massimale che contiene tutti vertici

dispari"
end dfs
dfs_visit(G,s,VAL):BOOLEAN
boolean risp = true
	c[s]=g
	if(Adj(s)!=NULL)
		foreach x in Adj(s) and risp=true
			if(c[x]=b)
				if(VAL[x]%2!=0)
					risp=dfs_visit(G,x,VAL)
				else c[x]=n
			else if(c[x]=g)
				risp=false
	else risp=false
	c[s]=n
return risp