广度优先搜索算法在交叉立方体中的应用  

The Breadth-First Search Algorithm on the Crossed Cube

作　　者：匡桂娟[1] 刘昕[2] 张宗云[1] 

机构地区：[1]青岛大学信息工程学院,山东青岛266071 [2]莱阳农学院计算机系,山东青岛266109

出　　处：《青岛大学学报（自然科学版）》2004年第4期80-84,共5页Journal of Qingdao University(Natural Science Edition)

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

关 键 词：并行计算系统 互连网络 广度优先搜索算法(BFS) 交叉立方体 最短路径 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]