构造最小生成树的量子算法

• 作者: 伍红 刘晓明 江贝 陈莘萌 黄传河
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 量子计算机 量子并行性 量子算法 量子搜索 最小生成树
• 年，卷（期）: 2003,（11）
• 所属期刊栏目: 学术探讨
• 页码范围: 96-99
• 页数: 4页
• 分类号: TP301.6
• 字数: 5467字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2003.11.032

摘要

图的最小生成树问题是网络优化中的一类基本问题.目前构造最小生成树的算法都是基于传统计算机的算法如Prim算法和Kruskal算法.该文提出了一个用于构造图的最小生成树的量子算法,它结合量子搜索的方法和经典Kruskal算法的思想,对于n个节点m条边的图,依次搜索出n-1条边使它们构成一棵最小生成树.这一算法的时间复杂性为O(n√m).与经典Kruskal算法相比,在同等条件下,该文的算法有较快的加速.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄传河	武汉大学计算机学院	90	740	14.0	23.0
2	陈莘萌	武汉大学计算机学院	75	780	13.0	26.0
3	江贝	武汉大学计算机学院	4	9	2.0	3.0
4	刘晓明	武汉大学计算机学院	5	11	2.0	3.0
5	伍红	武汉大学计算机学院	2	9	2.0	2.0