Passa al tema normale
Discussioni su argomenti di Informatica

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

programma

28/01/2004, 10: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.

28/01/2004, 13:29

non ho specificato che il linguaggio è il pascal.
Non c'è proprio nessuno in grado di aiutarmi?

28/01/2004, 14: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
Rispondi al messaggio


Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000— Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.