| 基于CREW遍历图的一种并行算法 |
| |
| 引用本文： | 廖常武.基于CREW遍历图的一种并行算法[J].计算机与现代化,2006(9):12-14. |
| |
| 作者姓名： | 廖常武 |
| |
| 作者单位： | 南京工业职业技术学院,江苏,南京,210016 |
| |
| 摘 要： | 针对串行算法模型下基于顶点遍历图的情况，提出了一种在CREWPRAM并行模型下遍历无向图的算法。该算法是找出无向图的一棵最短路径生成树，由向上和向下两条有向边替换最短路径生成树的每条边形成欧拉回路，运用欧拉回路技术计算前缀和，前缀和所对应的顶点即为遍历无向图的顺序。得出了该算法时间复杂度为O（n＋logn）的结论。
|
| 关 键 词： | 遍历 无向图 并行算法 生成树 |
| 文章编号： | 1006-2475（2006）09-0012-03 |
| 收稿时间： | 2006-04-14 |
| 修稿时间： | 2006年4月14日 |
A Parallel Algorithm Based on CREW Traversing Graph |
| |
| LIAO Chang-wu.A Parallel Algorithm Based on CREW Traversing Graph[J].Computer and Modernization,2006(9):12-14. |
| |
| Authors: | LIAO Chang-wu |
| |
| Affiliation: | Nanjing Institute of Industry Technology, Nanjing 210016,China |
| |
| Abstract: | According to the algorithm based on vertex traversing graph under the serial algorithm model,a parallel algorithm of traversing undirected graph based on edge is put forward on CREW PRAM.The shortest path spanning tree of undirected graph is found.The Euler cycle is formed by upward and downward directed edges replacing each edge of the shortest path spanning tree.Using the Euler cycle,the prefix sum is calculated.The vertex corresponding the prefix sum is the order of traversing undirected graph.The conclusion that the time complexity is O(n+logn) is reached by the algorithm. |
| |
| Keywords: | traversing undirected graph parallel algorithm spanning tree |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
