欧拉通路(回路):通过图(无向图或有向图)中所有边一次且仅一次行遍图中所有顶点的通路(回路)称为欧拉通路(回路)。
欧拉回路的Fleury算法:
设G为欧拉图,一般说来G中存在若干条欧拉回路,下面是求欧拉回路的Fleury算法:
Fleury算法:
(1)任取v0∈V(G),令P0=v0;
(2)设Pi=v0e1v1e2...eivi已经行遍,按下面方法来从E(G)-{e1,e2,...,ei}中选
取ei+1:
(a)ei+1与vi想关联;
(b)除非无别的边可供行遍,否则ei+1不应该为Gi=G-{e1,e2,...,ei}中的桥.
(3)当(2)不能再进行时,算法停止。
可以证明,当算法停止时所得简单回路Pm=v0e1v1e2...emvm(vm=v0)为G中的一条欧拉回路。