链路状态路由协议进行通信之前,需要完成网络拓扑结构的收敛。在开放最短路径(OpenShortPathFirst,OSPF)协议当中,使用洪泛(Flooding)算法进行网络拓扑信息的收敛,Flooding算法使用扩散方式进行信息传播,在链路较多的网络环境当中,这种方式会产生大量重复冗余的信息,造成通信资源的浪费。在目前网络向着大规模复杂化发展方向的趋势下,为了避免这种通信资源的浪费,对OSPF协议下的收敛算法的研究具有一定的实际意义。本文首先介绍了 LAP路由算法,并对LAP存在的问题和下一阶段的研究内容进行了论述;然后在LAP路由算法的基础上,针对一般性的网络的研究,提出了基于遍历树的LAP路由算法。又根据遍历方式的不同,提出了基于广度优先遍历树的LAP路由算法和基于深度优先遍历树的LAP路由算法,并给出了算法的实现步骤;接下来在理论上对算法进行了分析和证明;最后对算法进行了仿真实验证明。在NS2仿真平台当中,对本文的算法进行了仿真实验,并与LAP路由算法和Flooding算法进行了比较分析。从而得出以下结论:如果网络当中的路由结点数量为一个定值,随着结点之间链路数量的增加,广度优先遍历LAP路由算法完成网络拓扑收敛,需要进行的通信次数逐渐减少;Flooding算法完成网络拓扑收敛,需要进行的通信次数逐渐增加。当链路增加到两者相等的时候称为临界点。低于临界点的时候,Flooding算法的通信次数少于广度优先遍历树的LAP路由算法的通信次数;超过临界点的时候,广度优先遍历树LAP路由算法的通信次数少于Flooding算法的通信次数。