View difference between Paste ID: 8BrZKwfs and a8exxhrr

 -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