Visita di grafi

Problema [Attraversamento in ampiezza]:

**Input: $G = \lang V, E\rang$ (**non orientato e connesso) e $s \in V;$

Output: Una sequenza che contiene tutti i nodi del grafo, ordinati rispetto alla distanza da s

• G rappresentato tramite liste di adiacenza
• Utilizziamo una coda in cui salvare i nodi da visitare

public void ampiezza(s){ //s rappresenta il nodo di partenza
	Queue<Nodo> q = new Queue<Nodo>(); //contenitore di nodi non ancora visitati
	List<Lato> u = new List<Lato>(); //lati utilizzati per raggiungere nodi da visitare

	q.enqueue(s); //inseriamo il nodo di partenza
	nuovo[s] = 0; //vettore di stato: visitato/da visitare
	
	for(v in V)//V insieme dei vertici
		if(v != s)
			nuovo[v] = 1; //poniamo tutti i nodi "da visitare"

	while(!q.isEmpty(){
		v = q.front();
		q.dequeue();
		v.visita();
		for(w in lista_di_adiacenza_di_v)
			if(nuovo[w]){
				nuovo[w] = 0; //nodo "visitato"
				q.enqueue(w); //"prenotiamo" il nodo per la visita
				u.insert({v,w}, 1); //inseriamo il lato utilizzato nella lista
			}
	}
}

Complessità: Dati $G = \lang V, E \rang, \ n = |V|, \ m = |E|, \$ vale

• ogni nodo è inserito in coda una e una sola volta
• ogni lista di adiacenza è attraversata una e una sola volta
• per ogni nodo in ciascuna lista si eseguono $O(1)$ operazioni di costo $O(1)$

Di conseguenza:

• Complessità in Spazio: $\Theta(n)$
  • (coda di dimensione $O(n)$, vettore vecchi/nuovi di lunghezza n)
• Complessità in Tempo: $\Theta(n+m)$
  • (inserimento / estrazione di n nodi in coda, attraversamento di 2m nodi nelle lista di adiacenza)

Problema [Attraversamento in profondità]:

Idea: ad ogni passo si cerca di prolungare il cammino corrente andando a visitare un nodo non ancora visitato. Se tutti i nodi adiacenti sono già stati visitati si torna indietro di un passo (e si prova a prolungare il cammino)

Rappresentiamo G tramite liste di adiacenza e

• facciamo uso della ricorsione
  • OPPURE
• utilizziamo una pila in cui salvare i nodi da visitare

//VERSIONE RICORSIVA
public void profondRic(v){ //v: nodo di partenza
	List<Lato> u = new List<Lato>(); //lati che ci portano al nuovo nodo da visitare
	v.visita(); 
	nuovo[v] = 0; //vettore di stato: visitato (0) / da visitare (1)
	for(w in lista_di_adiacenza_di_v){
		if(nuovo[w]){ //cerchiamo il primo nodo adiacente a v da visitare
			u.insert({v,w},1);
			profondRic(w); //chiamata ricorsiva ponendo w come nodo di partenza
		}
	}
}

//VERSIONE ITERATIVA
public void profondIt(v){
	Stack<Nodo> s = new Stack<Nodo>();//nodi la cui lista di adiacenza non è stata del tutto scandita
	List<Lato> u = new List<Lato>(); //salviamo i lati che formeranno l'albero di copertura
	
for(x in V) //inizializziamo il vettore
		nuovo[x] = 1; //1: nuovo, 0: visitato

	v.visita(); //visitiamo il primo nodo
	nuovo[v] = 0; //lo segnamo come visitato
	s.push(v); //lo immettiamo nello stack

	do{
		while(esiste w in lista_di_adiacenza_di_v && nuovo[w]){ //cerchiamo un nodo nuovo nella lista di adiacenza di v
			w.visita(); //visitiamo
			nuovo[w] = 0; //segnamo il nodo come visitato
			u.insert({v,w}, 1); //carichiamo il lato
			s.push(w); //immettiamo nello stack il nodo w
			v = w; //avanziamo
		}
		s.pop(); //in cima allo stack c'è il nodo che deve essere scartato perchè nella sua lista di adiacenza non c'è nessuno da visitare
		if(!s.isEmpty()) //se lo stack non è vuoto
			v = s.top(); //leggiamo il nodo 
	}while(!s.isEmpty());
}