【摘要】 给出了互连网络上的广度优先搜索算法，将其应用到交叉立方体上可以得到交叉立方体的广度优先生成树。连通图的广度优先生成树的树高不会超过该图其他同根生成树的高度。利用这一性质，通过分析交叉立方体的广度优先生成树的特征，给出了n维交叉立方体CQ_n的直径为「(n+1)／2」的另外一种证明方法；该算法可以用来求解单源节点最短路径问题。并为讨论新的互连网络拓扑结构的直径和故障直径问题以及单源广播算法提供了一条新的思路。更多还原

【Abstract】 the Breadth-First Search algorithm on the interconnection network is given and applied to the crossed cube, then the breadth-first spanning tree is gotten. A breadth-first spanning tree is the shortest one among all the spanning trees having the same node as their boot node. Using this property, we prove that the diameter of n-dimensions crossed cube is [(n+1)/2] the same as that calculated by another algorithm. Further more, we get the shortest path from the given node to all the other nodes in interconnection networks.更多还原