求欧拉回路的Fleury算法(共5页).doc

精选优质文档-倾情为你奉上一、 实验内容：判断图G是否存在欧拉回路，若存在，输出其中一条欧拉回路。否则，显示无回路。二、 实验过程与结果1. 问题简介：通过图（无向图或有向图）中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图2. 算法思想（框图）：（1）任取v0V(G)，令P0=v0.（2）设Pi=v0e1v1e2eivi已经行遍，按下面方法来从E(G)-e1,e2,ei中选取ei+1：（a）ei+1与vi相关联；（b）除非无别的边可供行遍，否则ei+1不应该为Gi=G-e1,e2,ei中的桥。（3）当（2）不能再进行时，算法停止。 可以证明，当算法停止时所得简单回路Pm=v0e1v1e2emvm(vm=v0)为G中一条欧拉回路。3. 数据输入： 边数5，点数6 相关联的点1 2 1 3 2 5 4 2 3 2 4 54. 运行结果：存在欧拉回路 1，3，2，4，5，2，15.