PDA

Visualizza la versione completa : [C] Alberi e grafi


Mary84
09-07-2005, 01:15
Salve a tutti!
Devo preparare un progetto di strutture dati che consiste nel trovare il diametro di un albero.Cerco disperatamente un aiuto!
Questo e' il titolo:
Il diametro di un albero T=(V,E) e' dato da max delta(u,v) con u,v appartenenti a V e con delta(u,v) la distanza del cammino minimo tra u e v, cioe' il diametro e' la piu grande di tutte le distanze di cammino minimo nell'albero .
si dia un algoritmo per calcolare il diametro di un albero e si analizzi il tempo di esecuzione dell'algoritmo proposto.

Sono riuscita a svolgerlo ma la creazione dell'albero presenta ancora
qualche problema.
Vi ringrazio per l'attenzione :D!

billybilly
15-07-2005, 19:46
sol 1 )
fai una scansione esaustiva dell'albero....cioè fai passare tutti gli elementi dell'albero... e per ogni elemento richiama ricorsivamente la stessa funzione di scansione in modo che calcoli il cammmino minimo tra un elemento e tutti gli altri...memeorizzando in una var di appoggio il valore max trovato fin'ora
cioè se hai n elementi fai per ognuno fai n ricerche.O(n^2)
e poi fai la ricera del cammino a ogni passo....
certo nn è il modo migliore per rislverlo un pò altina come complexxita.... cmq... prova cosi la risoluzione esaustiva è sempre il caso piu sempliuce...se nn riesci fammi sapere ti scrivo il codice
ByBy

Mary84
16-07-2005, 03:44
:) grazie ho già risolto utilizzando liste di adiacenza.
Esame superato :D

zarkon
09-05-2006, 14:20
Originariamente inviato da Mary84
:) grazie ho già risolto utilizzando liste di adiacenza.
Esame superato :D
ciao!

non è mi daresti il codice sui grafi?
mi servirebbe per preparare un esame e proprio non riesco a venirne a capo! :messner:

alka
09-05-2006, 14:24
Originariamente inviato da zarkon
non è mi daresti il codice sui grafi?
mi servirebbe per preparare un esame e proprio non riesco a venirne a capo! :messner:
Hai già aperto una discussione sull'argomento. Inutile sollevarne un'altra sullo stesso problema per una comunicazione privata con uno degli utenti.

Loading