Abstract: A novel Unit Tree-based Breadth First Search(UTBFS) algorithm is proposed. The characteristic of the algorithm are as follows: puting forward the idea of unit tree spanning algorithm, integrating unit tree spanning algorithm with breath first search, and making an analysis of its performance in terms of time complexity degree, space complexity degree, feasibility and superiority. Experimental results demonstrate that UTBFS reduces the number of neighbor nodes and redundant message and is of higher searching efficiency as compared with traditional breath first search algorithm and random breath first search algorithm.
breadth first search,
random breadth first search