摘要: 提出基于单元树结构的广度优先搜索算法UTBFS。将单元树结构生成算法与广度优先算法相结合,阐述UTBFS的实现思路,对其时间复杂度、空间复杂度、可行性、优越性进行分析。实验仿真结果显示,相比于传统的广度优先搜索算法和随机广度优先搜索算法,UTBFS减少了需要转发消息的邻居节点个数和冗余消息,因此性能更优。
关键词:
点对点网络,
广度优先搜索,
单元树,
邻居节点,
随机广度优先搜索
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.
Key words:
P2P network,
breadth first search,
unit tree,
neighbor node,
random breadth first search
中图分类号:
鄢靖丰, 陶少华, 夏方玉. 基于单元树结构的广度优先P2P搜索算法[J]. 计算机工程, 2011, 37(9): 135-137.
YAN Jing-Feng, DAO Shao-Hua, JIA Fang-Yu. Breadth First P2P Search Algorithm Based on Unit Tree Structure[J]. Computer Engineering, 2011, 37(9): 135-137.