求有向图的所有Euler回路算法

An Algorithm for Finding All Euler Cycles in Digraph

首先利用图的深度优先搜索方法给出了有向图为强连通图的判定算法,然后利用图的广度优先搜索方法给出了有向图是欧拉图和有向边是桥的判定算法,最后给出了求有向图的所有欧拉回路算法,并通过实例验证了算法的有效性.从而有效地解决了欧拉回路的判定、计数和求解问题.

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.