programma

Messaggioda pippo617 » 28/01/2004, 11:43

avrei un problema a risolvere il seguente programma:

Dato un grafo, costruireun albero di ricoprimento per la visita in profondità e le visita in altezza.

Ringrazio anticipatamente chiunque possa aiutarmi.
pippo617
Starting Member
Starting Member
 
Messaggio: 1 di 3
Iscritto il: 28/01/2004, 11:40

Messaggioda pippo617 » 28/01/2004, 14:29

non ho specificato che il linguaggio è il pascal.
Non c'è proprio nessuno in grado di aiutarmi?
pippo617
Starting Member
Starting Member
 
Messaggio: 3 di 3
Iscritto il: 28/01/2004, 11:40

Messaggioda dazuco » 28/01/2004, 15:59

Posso dirti che per la visita in profondità di un grafo occorre una struttura dati appoggio tipo pila o stack.
Memorizziamo il grafo come liste di adiacenza, ossia, un vettore di puntatori a liste concatenate dove l'indice i del vettore corrisponde al nodo i del grafo e la lista legata alla posizione i rappresenta i nodi adiacenti del nodo i.
Allora comincia da un nodo (a) a scorrere il primo adiacente (b) e dopo aver aggiunto tale arco allo spanning tree passa a scorrere la lista adiacente del nodo b e cosi via. Ogni volta che visiti un nodo verifica attraverso un vettore dei visitati se tale nodo non è stato ancora visitato e se cosi è allora lo aggiungerai allo spanning tree. Ogni volta che visiti un nodo mettilo nella pila. Naturalmente se incontri un nodo già visitato passa al prossimo adiacente e solo quando ne visiti uno mai visitato prima ti sposti alla lista di adiacenza di tale nodo. Quando la lista di adiacenza del nodo termina allora tale nodo viene tolto dalla pila e la visita prosegue con il nodo xhe subito si trova in cima alla pila e tale visita riparte dalla lista di adiacenza nel punto in cui si era momentaneamente sospesa.
Spero di essere stato chiaro.
Implementarlo poi in pascal come in un altro linguaggio poui diventa più semplice.
ciao
dazuco
Junior Member
Junior Member
 
Messaggio: 56 di 196
Iscritto il: 10/08/2003, 12:58
Località: Italy


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 8 ospiti

cron