基于CREW遍历图的一种并行算法

• 作者: 廖常武
• 来源期刊: 计算机与现代化
• 学科: 工学
• 关键词: 遍历 无向图 并行算法 生成树
• 年，卷（期）: 2006,（9）
• 页码范围: 12-14
• 页数: 3页
• 分类号: TP301.6
• 字数: 2416字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-2475.2006.09.005

摘要

针对串行算法模型下基于顶点遍历图的情况,提出了一种在 CREW PRAM并行模型下遍历无向图的算法.该算法是找出无向图的一棵最短路径生成树,由向上和向下两条有向边替换最短路径生成树的每条边形成欧拉回路,运用欧拉回路技术计算前缀和,前缀和所对应的顶点即为遍历无向图的顺序.得出了该算法时间复杂度为O(n+logn) 的结论.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	廖常武		27	38	4.0	4.0