[C] Alberi n-ari: quale implementazione?

[fero86]

Originariamente inviato da BlackAuron

d è la distanza tra due nodi.

e cos'é la distanza tra due nodi in un albero N-ario?

Originariamente inviato da Red_Knight

Allora, per "albero generico" intendo un albero coi rami non pesati (il costo è unitario) e dove ogni nodo può avere un numero qualsiasi di figli. Il diametro che devo trovare - chiedo scusa ancora per l'eventuale uso inappropriato del termine - è la distanza, espressa in numero di archi, tra i due nodi più lontani che si possono trovare nell'albero.

ok, adesso é chiaro: dato un albero N-ario (V, E), cioé un grafo connesso aciclico i cui vertici sono gli elementi dell'insieme V e gli archi quelli dell'insieme E, diciamo "cammino" un insieme ordinato di elementi di V tali che per ogni vertice v avente successore succ(v) nel cammino esiste in E un elemento (v, succ(v)). questa definizione non ammette cammini che passano piu volte per gli stessi nodi perché i cammini sono stati definiti come insiemi e non multinsiemi. dato un albero N-ario si vuole trovare la cardinalitá massima dei cammini. giusto?

[wingman87]

Originariamente inviato da BlackAuron

Non ho sorvolato
mi resta comunque il dubbio che l'altro algoritmo non sia lineare nel tempo, ma piuttosto quadratico quantomeno nel caso pessimo, dal momento che per ogni nodo grossomodo c'è da fare una ricerca su tutti i figli per il massimo...

No, è sicuramente lineare: è uguale all'algoritmo per ricavare l'altezza (a meno di una costante)

EDIT: mi sono sbagliato, è a meno del coefficiente, non di una costante

[Red_Knight]

ok, adesso é chiaro: dato un albero N-ario (V, E), cioé un grafo connesso aciclico i cui vertici sono gli elementi dell'insieme V e gli archi quelli dell'insieme E, diciamo "cammino" un insieme ordinato di elementi di V tali che per ogni vertice v avente successore succ(v) nel cammino esiste in E un elemento (v, succ(v)). questa definizione non ammette cammini che passano piu volte per gli stessi nodi perché i cammini sono stati definiti come insiemi e non multinsiemi. dato un albero N-ario si vuole trovare la cardinalitá massima dei cammini. giusto?

Giusto!

Vedo che mi è stata data la soluzione in pseudocodice (grazie!), ma - ehm - non credo di averla capita.
Perché devo sfruttare le due altezze maggiori?

[BlackAuron]

perchè il più lungo cammino passante per un padre sarà uguale alla somma della prima e della seconda maggiore altezza dei figli. Guarda l'esempio che hai dato tu e capirlo è praticamente immediato.

[Red_Knight]

Scusa, la mia domanda era legata al fatto che il diametro potrebbe essere contenuto in un sottoalbero, ma ho realizzato adesso che la funzione suggeritami restituisce due valori e consente di verificare se il diametro è già stato trovato in un sottoalbero.
Ora però come faccio a far restituire due valori a una funzione in C?

[marco.r]

Direttamente non puoi.
Hai due alternative. La prima e' quella di ritornare un struttura con due campi, che contengono i due valori che vuoi. La seconda e' di passare due argomenti per puntatore, e modificarli.