在互连网络中进行通信,由网络拓扑决定的网络延迟是一个静态量,直接受到网络直径的影响。在网络有故障发生的情况下,故障直径反映了网络的容错能力,而故障直径的求解本身比较困难。网络寻径是网络通信必须考虑的一个重要方面。 本文针对以上情况研究了广度优先搜索算法在这些方面的应用。作者作出的研究成果主要体现在以下三个方面: 首先利用广度优先生成树的树高不会高于其他任何同根生成树树高的特点,对不同的网络进行了广度优先搜索分析,给出了超立方体,交叉立方体,螺旋立方体等网络的直径与故障直径。并且进一步给出了BC互连网络直径的一个界限。这为研究新的递归式网络拓扑的直径与故障直径的研究提供了一种新的途径。 其次考虑了至多可以删除多少个顶点才能保证网络的连通,给出了网络的容错能力。由Menger定理可以得到BC互连网络之间至少存在n条内部节点互不相交的路径。利用广度优先搜索的思想,本文给出了求任意两个节点之间的n条内部节点互不相交,且在两点间所有路径中是最短的n条路径的算法。该算法为网络故障直径的提供了依据。而且,在故障存在但是网络连通的情况下,可以求得网络中任意两节点间的n条最并行路径,提高了网络的容错能力。 最后,通过分布式的广度优先搜索算法给出了互连网络在正常或者有故障存在但是网络仍然连通的情况下单源广播算法,给出了给定两无故障节点间的最短路径算法的思想。 本文对提出的方法及算法的正确性进行了证明,为研究互连网络的性质提供了新的研究方法。对于直径与故障直径的算法,我们也已经在低维BC网络上通过,验证了算法的正确性。