| 求有向图的所有Euler回路算法 |
| |
| 引用本文： | 牟廉明.求有向图的所有Euler回路算法[J].内江师范学院学报,2008,23(2):11-14. |
| |
| 作者姓名： | 牟廉明 |
| |
| 作者单位： | 四川省高等学校数值仿真重点实验室//内江师范学院数学系,四川,内江,641112 |
| |
| 基金项目： | 国家自然科学基金
,
四川省教育厅资助项目
,
内江师范学院校科研和教改项目 |
| |
| 摘 要： | 首先利用图的深度优先搜索方法给出了有向图为强连通图的判定算法，然后利用图的广度优先搜索方法给出了有向图是欧拉图和有向边是桥的判定算法，最后给出了求有向图的所有欧拉回路算法，并通过实例验证了算法的有效性．从而有效地解决了欧拉回路的判定、计数和求解问题．
|
| 关 键 词： | Euler回路 回溯法 深度优先搜索 广度优先搜索 |
| 文章编号： | 1671-1785(2008)02-0011-04 |
| 修稿时间： | 2007年10月22 |
An Algorithm for Finding All Euler Cycles in Digraph |
| |
| MOU Lian-ming.An Algorithm for Finding All Euler Cycles in Digraph[J].Journal of Neijiang Teachers College,2008,23(2):11-14. |
| |
| Authors: | MOU Lian-ming |
| |
| Institution: | MOU Lian-ming ( Key Laboratory of Numerical Simulation of Sichuan Province//Department of Mathematics, Neijiang Normal University, Neijiang, Sichuan 641112, China) |
| |
| Abstract: | Firstly the judge-algorithm whether a digraph is complete connected graph is designed by the depth-first-search algorithm of digraph. Secondly the judge-algorithm whether a digraph is Euler graph is designed, the judge-algorithm whether a directed edge is bridge is designed by the breadth-first-search algorithm of digraph. Lastly the algorithm to output all Euler cycles in the digraph is constructed. The algorithmic validity is validated by example. Judgment, count and output of Euler cycle are effectually solved. |
| |
| Keywords: | Euler cycle Retractable method： depth-first-search： breadth-first-search |
| 本文献已被 维普 万方数据 等数据库收录！ |
