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

• 作者: 刘昕 匡桂娟 张宗云
• 来源期刊: 青岛大学学报（自然科学版）
• 学科: 工学
• 关键词: 并行计算系统 互连网络 广度优先搜索算法(BFS) 交叉立方体 最短路径
• 年，卷（期）: 2004,（4）
• 所属期刊栏目: 信息工程
• 页码范围: 80-84
• 页数: 5页
• 分类号: TP301
• 字数: 4052字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-1037.2004.04.020

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	匡桂娟	青岛大学信息工程学院	2	5	1.0	2.0
5	刘昕	潍坊学院计算机科学系	7	23	3.0	4.0
6	张宗云	青岛大学信息工程学院	4	15	3.0	3.0