文献类型：期刊文章

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

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

出　　处：《青岛大学学报（自然科学版）》

年　　份：2004

卷　　号：17

期　　号：4

起止页码：80-84

语　　种：中文

收录情况：AJ、CAS、CSA、CSA-PROQEUST、INSPEC、MR、普通刊

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

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

分 类 号：TP301]