PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Mercatanti A. Un algoritmo non backtrack per la visita di un albero. Contratto di collaborazione tecnico-scientifica Alenia-IEI-CNR. Internal note IEI-B4-39, 1993.
 
 
Abstract
(English)
No abstract available
Abstract
(Italiano)
Negli algoritmi per la ricerca di una catena in un albero, di tipo backtrack, la variazione dei vertici radice e terminale comporta la conversione dell'albero in arborescenza e conseguentemente la riallocazione dei dati del problema e dei relativi puntatori. Lo scopo di questo lavoro è la definizione di un algoritmo che non comporti la riallocazione dei dati specificativi dell'albero e dei relativi puntatori, ove si varino i vertici radice e terminale. Il principio su cui si basa è la trasformazione dell'albero in un grafo, mediante l'aggiunta dell'arco che connette i vertici radice e terminale, e la progressiva individuazione dei vertici pendenti e di quel1i ad essi adiacenti. Questi sono ipoteticamente pendenti, ove si supponga eliminato il vertice pendente. Il procedimento è ripetuto fino a quando non è più possibile individuare vertici pendenti, essendo gli altri appartenenti al ciclo. L'albero è rappresentato mediante liste di adiacenze dei vertici. Nato l'indice di un ipotetico vertice pendente, l'algoritmo verifica se è tale. In caso affermativo, mediante appropriati puntatori, è individuato in dette liste l'indice del vertice ad esso adiacente, e quindi ipoteticamente pendente. L'algoritmo è ripetuto fino a quando non è possibile individuarne altri. Quelli che non sono vertici pendenti, od ipoteticamente tali, appartengono al ciclo, ossia alla catena che collega il vertice radice con quello terminale. L'algoritmo che qui si descrive è deterministico e lineare, di tipo non backtrack, la cui complessità in tempo è O(n -m), dove n è il numero dei vertici dell'albero ed m, quello dei vertici che formano la catena. La complessità in spazio è lineare. L'efficienza dell'algoritmo è tanto maggiore quanto più l'a1bero è degenere.
Subject Algorithm
F.2.1 Numerical Algorithms and Problems


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional