[C] Diametro di un albero

[Red_Knight]

Salve, ho da fare un'esercitazione in C... ovviamente non chiedo il codice completo ma solo un suggerimento. La consegna è questa:

Il diametro di un albero T=(V,E) è dato da

max delta(u,v)
con u,v appartenenti a V

con delta(u,v) la distanza del cammino minimo tra u e v, cioè il diametro è la più 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.

Mi conviene salvarmi un elenco di tutti i cammini minimi e poi cercare il più grande? Quale algoritmo (tra i classici) dovrei usare secondo voi per trovare i cammini? Qualsiasi dritta è ben accetta.

[Mesh89]

C'è una soluzione di complessità lineare nel numero di vertici (o degli archi, che ovviamente sono vertici-1). Innanzitutto semplifica l'albero e rendilo binario (estenderlo al caso ennario diventa poi ovvio).

Presa una radice, essa ha due sottoalberi. Il diametro può comprendere la radice oppure no. Nel secondo caso, è ovviamente contenuto tutto all'interno di uno dei due sottoalberi. E se invece suppongo il diametro passi per questa radice, quale sarà?
Una volta trovata la risposta, estendi il ragionamento in modo ricorsivo a tutto l'albero, e il gioco è fatto.

Siccome hai chiesto solo uno spunto non vado avanti, dimmi se ti serve altro.

[Red_Knight]

Grazie mille per la dritta, dovrebbe bastarmi. A buon rendere!

[Red_Knight]

A ripensarci, forse mi sarebbe utile un'ulteriore dritta (o anche più di una dritta), non mi interessa più arrivarci da solo perché ho già risolto altri problemi e mi manca solo questo, quindi voglio solo liberarmene.

[masciapep]

Originariamente inviato da Red_Knight

Salve, ho da fare un'esercitazione in C... ovviamente non chiedo il codice completo ma solo un suggerimento. La consegna è questa:

Il diametro di un albero T=(V,E) è dato da

max delta(u,v)
con u,v appartenenti a V

con delta(u,v) la distanza del cammino minimo tra u e v, cioè il diametro è la più 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.

Mi conviene salvarmi un elenco di tutti i cammini minimi e poi cercare il più grande? Quale algoritmo (tra i classici) dovrei usare secondo voi per trovare i cammini? Qualsiasi dritta è ben accetta.

Ciao Red_Knight, ti ho inviato una mail. Anche a me servirebbe il tuo progetto svolto, appena puoi contattami, grazie!

edit: risolto !

[:.Blizzard.:]

Originariamente inviato da masciapep

Ciao Red_Knight, ti ho inviato una mail. Anche a me servirebbe il tuo progetto svolto, appena puoi contattami, grazie!

Non sarebbe meglio sforzarsi un minimo e farlo da se' ?


Comunque, due osservazioni:

1- Se l'albero è radicato, il diametro è dato dalla massima profondità del sottoalbero sinistro più la massima profondità del sottoalbero destro della radice.
Nel caso peggiore si ha una complessità lineare al numero dei nodi.

Basta quindi effettuare una visita dell'albero (indifferentemente in order, pre order o post order) e salvare entrambe le profondità massime per poi sommarla al termine della visita, con una complessità totale di O(n).

Questa quindi potrebbe essere un'idea.

2- Se l'albero è perfettamente bilanciato, ovvero le foglie dell'albero sono tutte allo stesso livello, basta scorrere soltanto un sottoalbero muovendosi in un'unica direzione fino a raggiungere una foglia. In questo particolare caso è possibile risolvere il problema in O(log n), cioè l'altezza dell'albero.

[gugoXX]

Originariamente inviato da :.Blizzard.:

Non sarebbe meglio sforzarsi un minimo e farlo da se' ?


Comunque, due osservazioni:

1- Se l'albero è radicato, il diametro è dato dalla massima profondità del sottoalbero sinistro più la massima profondità del sottoalbero destro della radice.
Nel caso peggiore si ha una complessità lineare al numero dei nodi.

Basta quindi effettuare una visita dell'albero (indifferentemente in order, pre order o post order) e salvare entrambe le profondità massime per poi sommarla al termine della visita, con una complessità totale di O(n).

Questa quindi potrebbe essere un'idea.

Secondo me non funziona.

Un albero con il ramo di destra con un solo figlio, e il ramo di sinistra con 2 sottorami ciascuno lungo 1000 (ogni padre con un figlio solo), risulterebbe avere poco piu' di 1000 come diametro, quando invece sarebbe circa 2000

[:.Blizzard.:]

Hai ragione gugo, ho detto una cavolata. E pensare che ci avevo pensato a un caso "limite" come il tuo e non sò perché mi era proprio sfuggito. Grazie della correzione