Fleury算法 设G为欧拉图,通常情况下,G中存在若干条欧拉回路。下面介 绍一种求欧拉回路的算法。 Fleury算法 (1)任取v∈v(G,令P=V0 (2)设P1=v0e1v1e2eV1已经遍历,按下面方法从 E(G)-{e1e2…,en}中选取e >e+1与v相关联 >e+1不应取G1=G一-【e1,e2;…,e1}中的桥除非无其它 边可供行遍 (3)重复步骤(2),直到步骤(2)不能再进行为止 可证明:当算法停止时,所得简单回路Pm=ve1V1e2… 11nYm(m=V)为G中一条欧拉回路11 Fleury算法 设G为欧拉图, 通常情况下, G中存在若干条欧拉回路。下面介 绍一种求欧拉回路的算法。 Fleury算法: (1) 任取v0∈V(G), 令P0=v0 (2) 设Pi = v0e1v1e2…eivi已经遍历, 按下面方法从 E(G) − { e1, e2, …, ei }中选取ei+1: ¾ ei+1与vi相关联 ¾ ei+1不应取Gi = G − { e1, e2, …, ei }中的桥, 除非无其它 边可供行遍 (3) 重复步骤(2), 直到步骤(2)不能再进行为止。 可证明: 当算法停止时, 所得简单回路Pm = v0e1v1 e2 … emvm(vm=v0)为G中一条欧拉回路